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

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

Предположим, что массив для сортировки равен (8, 4, 3, 9, 1). На следующей диаграмме показано, как пузырьковая сортировка выполняет несколько итераций, пока массив не будет полностью отсортирован.

В первой итерации мы начинаем со сравнения первых двух элементов 8 и 4. Поскольку 8 › 4, мы меняем их местами. Затем сравниваем второй и третий элементы, 8 и 3. Поскольку 8 › 3, меняем их местами. Однако, когда мы сравниваем следующие два элемента 8 и 9, они находятся в правильном порядке (8 ‹ 9). Поэтому мы не меняем их местами. Мы продолжаем этот процесс до тех пор, пока не будут сравнены последние два элемента. В конце первой итерации самый большой элемент 9 помещается в конец массива. Точно так же второй по величине элемент 8 приводится в правильное положение в конце второй итерации. Также обратите внимание, что в итерации iᵗʰ мы должны сравнивать до элемента (n - i)ᵗʰ, где n — общее количество элементов в массиве, а i ≥ 0. Например, во второй итерации приведенного выше примера мы не учитываем 9 (последний элемент); в третьей итерации мы не учитываем два последних элемента.

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

После m итераций последние mэлементы массива будут отсортированы.

Реализация на C

Анализ пузырьковой сортировки

  • Пузырьковая сортировка — это алгоритм на месте, который означает, что для выполнения сортировки не требуется дополнительное пространство памяти.
  • Временная сложность пузырьковой сортировки в лучшем случае составляет O(n). Когда массив уже отсортирован (что является лучшим случаем), пузырьковая сортировка может обнаружить его за одну итерацию и завершится. Если на итерации не выполняется никаких обменов, это означает, что массив был отсортирован (см. рисунок ниже). Логическая переменная swapped в приведенной выше реализации служит этой цели.

  • Пузырьковая сортировка имеет временную сложность в наихудшем и среднем случае O (n²). Предположим размер массива в n, он должен выполнить (n-1) сравнений на первой итерации, (n-2) сравнений на следующей итерации, и этот шаблон продолжается до последней итерации (см. рисунок ниже). Таким образом, общее количество сравнений будет (n - 1) + (n - 2) + …… + 1 = n (n - 1)/2, следовательно, O (n²).

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

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

  • Все эти три алгоритма сортировки имеют наихудшую и среднюю временную сложность O(n²). Сортировка вставками и пузырьковая сортировка имеют наилучшую временную сложность O (n), а сортировка выбором - O (n²).
  • Все алгоритмы на месте (пространственная сложность O (1)).
  • Предположим, что элементы должны быть отсортированы в порядке возрастания, после iитераций пузырьковой сортировки последние i элементы в массиве будут самыми большими i элементы в отсортированном порядке. Аналогично для сортировки выбором первые iэлементы массива будут наименьшими iэлементами в порядке сортировки. Однако сортировка вставками отсортировала бы только первые элементы i. Следующая диаграмма даст лучшее понимание. (Обратите внимание, что это может измениться в зависимости от того, как реализованы алгоритмы. Например, массив также можно перемещать справа налево)

Надеюсь, вы найдете эту статью полезной!