Что такое сортировка?

Сортировка — это процесс упорядочения данных в определенном порядке, обычно в порядке возрастания или убывания, на основе линейной связи между элементами данных.

Зачем нам нужна сортировка?

Сортировка имеет решающее значение при работе со структурированными данными, поскольку она обеспечивает эффективный поиск данных, упрощает анализ данных и улучшает общее управление данными.

Алгоритмы сортировки

В этом посте рассматриваются следующие алгоритмы сортировки: пузырьковая сортировка, сортировка выбором, сортировка вставками, сортировка слиянием и быстрая сортировка.

Пузырьковая сортировка

Пузырьковая сортировка неоднократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они расположены в неправильном порядке. Этот процесс продолжается до тех пор, пока массив не будет отсортирован, при этом более крупные элементы «всплывают» до конца.

Алгоритм

Шаг 1. Начало
Шаг 2: я = 0
Шаг 3: если я Шаг 4: j = 0
Шаг 5: если j Шаг 6: если массив[j] > массив[j 1], перейдите к шагу 7; иначе перейдите к шагу 8
Шаг 7. Поменяйте местами массив[j] и массив[j 1]
Шаг 8: приращение j; переходим к шагу 5
Шаг 9: увеличить i; переходим к шагу 3
Шаг 10: Завершить

Код

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Временная сложность

Лучший случай: O(n)
Средний случай: O(n^2)
Худший случай: O(n^2)

Сортировка выбором

Сортировка выбором находит наименьшее значение в неотсортированной части массива и помещает его в начало этой части.

Алгоритм

Шаг 1: Начало
Шаг 2: я = 0
Шаг 3: если я Шаг 4: минимальное_значение = я; j = я 1
Шаг 5: если j Шаг 6: если массив[минимальное_значение] > массив[j], перейдите к шагу 7; иначе перейдите к шагу 8
Шаг 7: минимальное_значение = j
Шаг 8: увеличение j; переходим к шагу 5
Шаг 9: поменяйте местами массив[минимальное_значение] и массив[i]
Шаг 10: увеличить i; переходим к шагу 3
Шаг 11: Завершить

Код

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  Временная сложность


Лучший случай: O(n^2)

Средний случай: O(n^2)

Худший случай: O(n^2) 


  
  
  Сортировка вставками


Сортировка вставками строит отсортированный массив по одному элементу, беря каждый элемент из неотсортированной части и вставляя его в правильную позицию в отсортированной части.


  
  
  Алгоритм


Шаг 1. Начало

Шаг 2: я = 1

Шаг 3: если я 
Шаг 4: ключ = arr[i]

Шаг 5: j = i - 1

Шаг 6: если j >= 0 и arr[j] > key, перейдите к шагу 7; иначе перейдите к шагу 10

Шаг 7: arr[j 1] = arr[j]

Шаг 8: уменьшите j на 1

Шаг 9: перейдите к шагу 6

Шаг 10: arr[j 1] = клавиша

Шаг 11: увеличьте i на 1; переходим к шагу 3

Шаг 12: Завершить


  
  
  Код




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  Временная сложность


Лучший случай: O(n)

Средний случай: O(n^2)

Худший случай: O(n^2) 


  
  
  Сортировка слиянием


Сортировка слиянием — это алгоритм «разделяй и властвуй», который рекурсивно делит массив на более мелкие подмассивы, сортирует их, а затем снова объединяет.


  
  
  Алгоритм


Алгоритм сортировки слиянием


Шаг 1: Начните

Шаг 2. Если длина (массив) 
Шаг 3: middle_point = длина(массив) // 2

Шаг 4: left_half = массив[:mid_point]

Шаг 5: right_half = массив[mid_point:]

Шаг 6: sorted_left = merge_sort(left_half)

Шаг 7: sorted_right = merge_sort(right_half)

Шаг 8: верните merge(sorted_left, sorted_right)

Шаг 9: Завершить

Функция слияния


Шаг 1: Начните

Шаг 2: sorted_merge = []

Шаг 3: l = 0, r = 0

Шаг 4: если l 
Шаг 5: если left[l] 
Шаг 6: добавьте left[l] в sorted_merge; увеличить l на 1

Шаг 7: добавьте right[r] к sorted_merge; увеличить r на 1

Шаг 8: перейдите к шагу 4 

Шаг 9: если l 
Шаг 10: добавьте left[l] в sorted_merge; увеличить l на 1 

Шаг 11: перейдите к шагу 9 

Шаг 12: если r 
Шаг 13: добавьте right[r] к sorted_merge; увеличить r на 1

Шаг 14: перейдите к шагу 12 

Шаг 15: Верните sorted_merge

Шаг 16: Конец


  
  
  Код




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Временная сложность


Лучший случай: O(n log n)

Средний случай: O(n log n)

Худший случай: O(n log n) 


  
  
  Быстрая сортировка


Быстрая сортировка — это эффективный алгоритм сортировки на месте, использующий подход «разделяй и властвуй». Он выбирает опорный элемент и разбивает массив вокруг опорного элемента так, чтобы элементы, меньшие, чем опорный элемент, находились слева от него, а элементы, превышающие опорный элемент, — справа. Затем этот процесс рекурсивно применяется к подмассивам.


  
  
  Алгоритм


Быстрая сортировка


Шаг 1: Начните

Шаг 2: Если низкий 
Шаг 3: Pivot_index = раздел (arr, low, high)

Шаг 4: быстрая сортировка (arr, low, Pivot_index - 1)

Шаг 5: быстрая сортировка (arr, Pivot_index 1, High)

Шаг 6: Завершите 

Функция раздела


Шаг 1: Начните

Шаг 2: пивот = arr[high]

Шаг 3: влево = низко, вправо = высоко — 1

Шаг 4: если влево 
Шаг 5: если arr[left] > Pivot и arr[right] 
Шаг 6: если arr[left] 
Шаг 7: если arr[right] >= поворот, уменьшите вправо

Шаг 8: перейдите к шагу 4 

Шаг 9: поменяйте местами arr[left] и arr[high]

Шаг 10: вернитесь влево

Шаг 11: Завершите 


  
  
  Код




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  Временная сложность


Лучший случай: O(n log n)

Средний случай: O(n log n)

Худший случай: O(n^2)