Оптимизация пузырьковой сортировки в C, которая уменьшит количество перестановок, необходимых для сортировки списка чисел в порядке возрастания

Question

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

2 3 8 6 23 14 16 1 123 90  (10 elements)

1. Сравнить элемент [0] и элемент [1]
2. Если [0] больше [1], то своп завершен.
3. Если [1] больше [0], то обмен не завершен.

Затем сортировка пузырьков перейдет к сравнению элементов [1] и [2] и т. Д., В результате чего будет получено 9 перестановок.

Однако, может ли быть способ гарантировать, что на первом проходе наибольшее число будет на своем месте в [9], а на втором проходе два наибольших числа будут на своих местах в [7] и [8]?

Answer 1

Bubble sort - это особый алгоритм - на самом деле не имеет смысла спрашивать, можно ли его оптимизировать, чтобы получить желаемое свойство.Он также имеет сложность O (n ^ 2), поэтому его редко используют.

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

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

Answer 2

Не используйте пузырьковую сортировку. Рассмотрим лучшие алгоритмы, такие как

• Timsort
• Сортировка слиянием
• Быстрая сортировка (что в пессимистическом случае оказывается хуже, чем два выше)

Встреча с вопросом Как оптимизировать пузырьковую сортировку Мой ответ - оптимизировать его, пока это еще не Timsort.

Answer 3

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

Оптимизация просто идетна один шаг меньше в конце второго прохода:

let n equal top_element - 1
while n is greater than or equal to zero
  for i = 0 to n
    if element i is greater than element i+1 then swap
  subtract 1 from n

Answer 4

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