На одних сайтах говорят, что челночная сортировка - это то же самое, что и шейкерная, а на других сайтах показывают, как работает челночная сортировка, и по принципу работы это похоже на сортировку вставками.
Можете, пожалуйста, объяснить, в чем разница и, если можно, дайте пример, где эта разница хорошо видна.
1 ответ
Если у нас есть массив элементов a
и нам нужно переставить элемент a[i]
влево в позицию j
(j < i
), то сделать это можно двумя способами:
Способ 1. Сохранить значение
a[i]
в сторонке. Сдвинуть все элементы с индексами[i, j)
вправо на один шаг, после чего записать исходное значениеa[i]
в "освободившуюся" ячейкуa[i]
.Способ 2. Обменять местами элементы
a[i]
иa[i - 1]
. Затем обменять местами элементыa[i - 1]
иa[i - 2]
. И т.д. и т.п. пока мы не обменяем паруa[j+1]
иa[j]
. Несложно видеть, что результат такой манипуляции совпадает с вариантом 1.
Сортировка вставками сначала выполняет просмотр левой части массива для того, чтобы найти правильное место j
для очередного элемента a[i]
. После этого при помощи метода 1 элемент a[i]
помещается на правильное место j
.
Челночная сортировка сразу же начинает выполнять манипуляции метода 2, на лету проверяя, не добрался ли уже элемент a[i]
до своего правильного места в левой части массива.
Единственной более-менее осязаемой разницей между сортировкой вставками и челночной сортировкой является то, то первая сначала выполняет проход по левой части массива для поиска места вставки, а затем выполняет перемещение нового элемента (что фактически выливается в еще дин проход по левой части массива).
А челночной сортировка объединяет и поиск места вставки, и собственно перемещение элементов в единый проход по левой части массива.
При желании, вы можете реализовать сортировку вставками, но для перемещения элемента на новое место использовать именно метод 2. В такой ситуации единственным отличием между этими сортировками будет лишь то, что сортировка вставками ищет правильное место для элемента заранее (перед выполнением метода 2), а челночной сортировка ищет правильное место для элемента на лету (в процессе выполнения метода 2).