Структуры и алгоритмы данных Python: сортировка списка элементов с использованием гребенки

Поиск и сортировка Python: упражнение 15 с решением

Напишите программу на Python для сортировки списка элементов с использованием Comb sort.
Расческа - это разновидность пузырчатой сортировки. Подобно сортировке «Шелл», сортировка «Гребень» увеличивает разрыв, используемый в сравнениях и обменах. Некоторые реализации используют сортировку вставкой, когда зазор меньше определенной величины. Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка не представляют проблемы при пузырьковой сортировке. В пузырьковой сортировке, когда сравниваются любые два элемента, они всегда имеют разрыв 1. Основная идея гребенчатой сортировки состоит в том, что разрыв может быть намного больше 1.

Визуализация гребенчатой сортировки:

Анимационные кредиты: Jerejesse

Пример решения :

Код Python:

def comb_sort(nums):
    shrink_fact = 1.3
    gaps = len(nums)
    swapped = True
    i = 0
    while gaps > 1 or swapped:
        gaps = int(float(gaps) / shrink_fact)
        swapped = False
        i = 0
        while gaps + i < len(nums):
            if nums[i] > nums[i+gaps]:
                nums[i], nums[i+gaps] = nums[i+gaps], nums[i]
                swapped = True
            i += 1
    return nums
num1 = input('Input comma separated numbers:\n').strip()
nums = [int(item) for item in num1.split(',')]
print(comb_sort(nums))

Пример вывода:

 Введите числа через запятую:
 5, 15, 37, 25, 79
[5, 15, 25, 37, 79]

Блок - схема:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущая: Напишите программу на Python для сортировки списка элементов, используя сортировку Cocktail shaker.
Далее: Напишите программу на Python для сортировки списка элементов с помощью Cycle sort.