Какой это тип сортировки?

Question

Книга C ++, которую я читаю, описала своего рода алгоритм, говоря, что это Bubblesort, но я не могу найти ни одного варианта Bubblesort, подобного этому. Я понимаю, что различия незначительны, но настолько ли она эффективна, как обычная пузырьковая сортировка?

BubbleSort(int A[], int length)
for (j=0; j < length-1; j++)
  for (i=j+1; i < length; i++)
    if (A[i] < A[j])
      Swap()

По сути, вместо сравнения двух смежных значений он сравнивает первый A [0] с каждой записью, на следующем проходе сравнивает A [1] с оставшимися записями, затем A [2] и т. Д.

Это действительно обычная пузырьковая сортировка, характеристики и производительность точно такие же?

Answer 1

Эта сортировка аналогична сортировке выбора в том, что каждый проход через внешний цикл идентифицирует лучший элемент и удаляет его из дальнейшего рассмотрения. Однако в традиционной сортировке выбора лучший элемент заменяется на удаляемый элемент, а другие элементы остаются одни. В списке, который вы перечисляете (найден, IIRC, в «Базовом подходе к базовому» среди других мест), некоторые другие элементы также будут обмениваться. Я не думаю, что дополнительные свопы приносят что-то особенно полезное, и сортировка теряет практически единственное преимущество, которое имеет пузырьковая сортировка (пригодность для реализации на носителях с чисто последовательным доступом)

Answer 2

Это выбор сортировки . На каждом проходе вы находите самый маленький элемент i и помещаете его в положение i. После первого прохода больше не нужно смотреть на A [0] и так далее. Сортировка выбора - наихудший O (n ² ) и наибольший O (n), как и в случае с пузырьковой сортировкой, но она имеет меньший постоянный коэффициент, чем пузырьковая сортировка. Вставка сортировки , дополнительное уточнение, еще лучше, до такой степени, что это быстрее, чем большинство алгоритмов O (n log n) для очень маленьких массивов (менее десяти элементов или около того) и столь серьезных примитивов сортировки библиотеки остановится на нем для небольших подзадач.

Answer 3

Похоже, Выбор сортировки для меня. Алгоритм работает следующим образом (как описано на странице вики):

1. Найдите минимальное значение в списке
2. Поменяйте местами со значением в первой позиции
3. Повторите шаги выше для остальной части списка (начиная со второй позиции и продвигаясь каждый раз)

Answer 4

Алгоритм больше похож на сортировку вставки, поскольку они совместно используют один и тот же (внешний) инвариант цикла - после j -ой итерации внешнего цикла самые маленькие элементы j находятся в своих правильных положениях.

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

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