Какой алгоритм сортировки здесь используется

Question

В онлайн-мероприятии я должен завершить частично законченный код. Они используют структуру данных списка ссылок для хранения каждого элемента. Сложность по времени составляет O (n * n) А во внешнем (for) цикле итерация завершается, когда node-> next! = NULL (т. Е. Только n-1 проверок). Внутренний (для) цикла, есть n проверок до (ptr становится NULL)

скажем, есть 5 элементов. А также, Элементы в указанном порядке 5 -> 3 -> 1 -> 2 -> 4 -> NULL

Циклы сортировки:

1 -> 3 -> 5 -> 2 -> 4 -> NULL

1 -> 2 -> 5 -> 3 -> 4 -> NULL

1 -> 2 -> 3 -> 5 -> 4 -> NULL

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Элементы в отсортированном порядке

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Какой алгоритм сортировки здесь используется?

Answer 1

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

5 ->3 ->1 ->2 ->4 ->NULL
1 ->3 ->5 ->2 ->4 ->NULL

Обратите внимание, что 1 (самый маленький элемент) поменялся местами спереди, но остальные элементы расположены в том же порядке. Аналогично, между второй и третьей итерациями вы видите это:

1 ->3 ->5 ->2 ->4 ->NULL
1 ->2 ->5 ->3 ->4 ->NULL

Здесь 2, второй наименьший элемент, переводится во вторую позицию, но остальные элементы расположены в том же порядке.

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

Надеюсь, это поможет!

Answer 2

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