Разница между пузырьковой сортировкой и сортировкой гномов

Question

Bubble sort и gnome sort, они имеют одинаковую сложность в худшем, лучшем и среднем случаях.В чем разница между пузырьковой сортировкой и сортировкой гномов (а не их именами ...)?

Answer 1

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

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

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

Для алгоритма сортировки вставками: http://codingmash.com/2012/07/the-insertion-sort-algorithm/

Длясортировка гномов: http://codingmash.com/2012/07/gnome-sort-a-variant-of-insertion-sort/

Надеюсь, это помогло:)

Answer 2

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

Answer 3

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

Answer 4

Bubble sort выполняется во вложенном цикле, а gnome sort - в одном цикле. Кроме того, пузырьковая сортировка сравнивает соседние элементы в последовательных проходах по всему списку, тогда как сортировка gnome сравнивает соседние элементы назад и перемещает индекс вперед и назад. Это всего лишь два отличия. Остальные объясняются в приведенной ссылке.