Структуры и алгоритмы данных Python: оболочка

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

Напишите программу на Python для сортировки списка элементов, используя алгоритм сортировки оболочки.
Примечание. Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки». пары элементов далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».

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

Код Python:

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
      for start_position in range(sublistcount):
        gap_InsertionSort(alist, start_position, sublistcount)
      print("After increments of size",sublistcount, "The list is",nlist)
      sublistcount = sublistcount // 2
def gap_InsertionSort(nlist,start,gap):
    for i in range(start+gap,len(nlist),gap):
        current_value = nlist[i]
        position = i
        while position>=gap and nlist[position-gap]>current_value:
            nlist[position]=nlist[position-gap]
            position = position-gap
        nlist[position]=current_value
nlist = [14,46,43,27,57,41,45,21,70]
shellSort(nlist)
print(nlist)

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

 После увеличения размера 4 Список [14, 41, 43, 21, 57, 46, 45, 27, 70]                                   
После увеличения размера 2 Список [14, 21, 43, 27, 45, 41, 57, 46, 70]                                   
После увеличения размера 1 Список [14, 21, 27, 41, 43, 45, 46, 57, 70]                                   
[14, 21, 27, 41, 43, 45, 46, 57, 70]

Блок - схема:

Визуализируйте выполнение кода Python:

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

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

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

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