Какие алгоритмы сортировок есть?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

Алгоритмы сортировки — это методы упорядочивания элементов в списке или массиве. Они важны для оптимизации поиска и упрощения обработки данных. Рассмотрим основные алгоритмы сортировки:

Пузырьковая сортировка (Bubble Sort)

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            # Сравниваем соседние элементы
            if arr[j] > arr[j+1]:
                # Меняем местами, если они в неправильном порядке
                arr[j], arr[j+1] = arr[j+1], arr[j]

Сортировка вставками (Insertion Sort)

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

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        # Перемещаем элементы, которые больше ключа, на одну позицию вперед
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # Вставляем ключ в его правильное место
        arr[j + 1] = key

Сортировка выбором (Selection Sort)

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

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            # Находим минимальный элемент в оставшейся части массива
            if arr[min_idx] > arr[j]:
                min_idx = j
        # Меняем местами найденный минимальный элемент с первым элементом
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Быстрая сортировка (Quick Sort)

Быстрая сортировка выбирает опорный элемент и разделяет массив на две части: элементы меньше опорного и элементы больше опорного. Затем рекурсивно сортирует обе части.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        # Рекурсивно сортируем подмассивы и объединяем их с опорным элементом
        return quick_sort(less) + [pivot] + quick_sort(greater)

Сортировка слиянием (Merge Sort)

Сортировка слиянием также использует метод "разделяй и властвуй". Она делит массив на две половины, рекурсивно сортирует каждую половину, а затем объединяет отсортированные половины.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
​
        # Рекурсивно сортируем обе половины
        merge_sort(L)
        merge_sort(R)
​
        i = j = k = 0
​
        # Объединяем отсортированные половины
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
​
        # Проверяем, остались ли элементы
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
​
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Пирамидальная сортировка (Heap Sort)

Пирамидальная сортировка использует структуру данных "куча" для упорядочивания элементов. Она строит максимальную кучу из массива, а затем извлекает максимальный элемент и перестраивает кучу.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
​
    # Проверяем, если левый дочерний элемент больше корня
    if l < n and arr[i] < arr[l]:
        largest = l
​
    # Проверяем, если правый дочерний элемент больше, чем самый большой элемент на данный момент
    if r < n and arr[largest] < arr[r]:
        largest = r
​
    # Меняем местами и продолжаем heapify, если корень не самый большой
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
​
def heap_sort(arr):
    n = len(arr)
​
    # Построение кучи
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
​
    # Извлечение элементов из кучи
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Меняем местами
        heapify(arr, i, 0)