Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Сортировка расческой на языке Python
И опять перед нами разновидность пузырьковой сортировки. В чём основная идея сортировки расчёской? Мы знаем, что в пузырьковой сортировке шаг прохода всегда равен 1. А что если взять максимально возможный шаг, а потом каждый раз уменьшать его на единицу.
А в чём вся идея этой сортировки? В сортировке расчёской сделана попытка уменьшить количество перестановок. Другими словами часть больших элементов может оказаться в конце массива за одну перестановку, а не за множество перестановок, когда он продвигается по всей длине последовательности.
Размер шага мы каждый раз уменьшаем на единицу. Но это не факт, что это оптимальное уменьшение. Экспериментально показано, что оптимально каждый раз делить шаг на значение 1.247331. Т.е. вместо
step -= 1
нужно написать
step = int(step / 1.247331)
Многое зависит от экспериментальных проверок!
Предыдущая статья по сортировке...
Следующая статья по сортировке...
Отличного программирования, друзья. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
