13. Алгоритм сортировки. Сортировка вставками, пузырьковая сортировка, быстрая сортировка

Меню

Лекция 13. Алгоритм сортировки. Сортировка вставками, пузырьковая сортировка, быстрая сортировка

13.1. Алгоритмы
Сортировка данных — это фундаментальная операция в информатике и программировании, важная для эффективной работы множества алгоритмов и структур данных. Существуют различные алгоритмы сортировки, каждый из которых имеет свои достоинства и недостатки, применимые в зависимости от конкретной задачи и требований к производительности. В этом тексте мы рассмотрим три классических алгоритма сортировки: сортировка вставками, пузырьковая сортировка и быстрая сортировка.

13.2. Сортировка вставками
Начнем с сортировки вставками. Этот алгоритм прост в реализации и хорошо работает на небольших наборах данных. Идея сортировки вставками заключается в том, чтобы разделить массив на две части: отсортированную и неотсортированную. На каждом шаге алгоритма берется следующий элемент из неотсортированной части и вставляется в нужное место в отсортированной части. Это продолжается до тех пор, пока все элементы не будут отсортированы.

Рассмотрим подробнее, как работает сортировка вставками. Изначально считается, что первый элемент массива уже отсортирован. Затем берем второй элемент и сравниваем его с первым. Если второй элемент меньше первого, меняем их местами. Далее берем третий элемент и вставляем его в нужное место среди первых двух, чтобы сохранить порядок. Этот процесс повторяется для каждого следующего элемента, пока весь массив не будет отсортирован.

Сортировка вставками имеет временную сложность O(n^2) в худшем случае, где n — количество элементов в массиве. Это происходит потому, что в худшем случае каждый элемент должен быть сравнен с каждым другим элементом. Однако в лучшем случае, когда массив уже отсортирован, временная сложность составляет O(n), так как нет необходимости в перестановках. Среднее время выполнения также составляет O(n^2).

13.3. Пузырьковая сортировка
Теперь перейдем к пузырьковой сортировке. Это еще один простой в реализации алгоритм сортировки, который также имеет временную сложность O(n^2) в худшем случае. Идея пузырьковой сортировки заключается в том, чтобы многократно проходить через массив, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Каждый проход по массиву перемещает наибольший элемент в его окончательную позицию, как если бы он "всплывал" на поверхность, отсюда и название алгоритма.

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

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

13.4. Быстрая сортировка
Наконец, рассмотрим быструю сортировку, также известную как быстрая сортировка (QuickSort). Это один из самых эффективных алгоритмов сортировки общего назначения, особенно для больших наборов данных. Быстрая сортировка использует стратегию "разделяй и властвуй". Идея заключается в том, чтобы выбрать опорный элемент (так называемый pivot) и разделить массив на две части: элементы, меньшие опорного, и элементы, большие опорного. Затем эти две части рекурсивно сортируются тем же методом.

Процесс быстрой сортировки начинается с выбора опорного элемента. Существует несколько стратегий выбора опорного элемента, такие как выбор первого элемента, последнего элемента, среднего элемента или случайного элемента. После выбора опорного элемента массив переставляется таким образом, чтобы все элементы, меньшие опорного, находились слева от него, а все элементы, большие опорного, находились справа. Этот процесс называется разделением (partitioning).

После разделения быстрая сортировка рекурсивно применяется к подмассивам слева и справа от опорного элемента. Рекурсия продолжается до тех пор, пока подмассивы не станут настолько маленькими, что их можно считать отсортированными (например, когда они содержат один или два элемента).

Быстрая сортировка имеет среднюю временную сложность O(n log n), что делает ее одной из самых быстрых сортировок для больших массивов. Однако в худшем случае временная сложность может достигать O(n^2), если опорные элементы выбираются неудачно, например, если массив уже отсортирован или содержит одинаковые элементы. Для уменьшения вероятности худшего случая часто используются стратегии выбора опорного элемента, такие как медиана из трех (median-of-three) или случайный выбор.

13.5. Примеры реализации и сравнение алгоритмов
Теперь рассмотрим детальнее каждый из этих алгоритмов и приведем примеры их реализации на языке программирования Python.

Сортировка вставками
Алгоритм сортировки вставками можно реализовать следующим образом:


```python
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
    return arr

# Пример использования:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Отсортированный массив:", sorted_arr)
```

В этом примере мы сначала инициализируем внешний цикл, который начинается со второго элемента массива (индекс 1). Затем сохраняем текущий элемент (key) и сравниваем его с предыдущими элементами массива в внутреннем цикле. Если текущий элемент меньше предыдущего, мы сдвигаем предыдущий элемент вправо и продолжаем сравнение, пока не найдем правильное место для текущего элемента.

Пузырьковая сортировка
Пузырьковая сортировка может быть реализована следующим образом:


```python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Пример использования:
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Отсортированный массив:", sorted_arr)
```

В этом примере мы начинаем с первого элемента массива и сравниваем его с соседним элементом. Если текущий элемент больше соседнего, меняем их местами. Этот процесс продолжается до конца массива. После каждого прохода наибольший элемент оказывается в конце массива. Внешний цикл повторяется, пока не произойдет ни одной перестановки в ходе очередного прохода, что означает, что массив отсортирован.

Быстрая сортировка
Быстрая сортировка может быть реализована следующим образом:


```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# Пример использования:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Отсортированный массив:", sorted_arr)
```

В этом примере мы начинаем с выбора опорного элемента, которым является средний элемент массива. Затем создаем три подмассива: left, содержащий элементы, меньшие опорного; middle, содержащий элементы, равные опорному; и right, содержащий элементы, большие опорного. Затем рекурсивно применяем быструю сортировку к подмассивам left и right и объединяем результаты с middle.

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

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

Сортировка вставками проста в реализации и хорошо работает на небольших массивах или частично отсортированных данных. Ее временная сложность составляет O(n^2) в худшем случае, но она может работать быстрее на почти отсортированных массивах с временной сложностью O(n).

Пузырьковая сортировка также проста в реализации, но она менее эффективна, чем сортировка вставками. Временная сложность пузырьковой сортировки в худшем и среднем случае составляет O(n^2), что делает ее непригодной для больших массивов. Однако она может быть полезна

13.6. Тест