2016-01-19 5 views
0

Я проходил процедуру вставки Sort algo в CLRS. Я не уверен, что право реализация -CLRS Insertion Sort Implmentation

Algo из КСПСА - CLRS pseudocode

Осуществления 1:

def Insertion_sort(): 
list = [3,5,1,7,2,4] 
for j in xrange(1,len(list)): 
    i = j-1 
    while i>=0 and list[i] > list[j]: 
     swap(list, i, j) 
     j = i 
     i = i-1 

реализация 2:

def Insertion_sort2(): 
list = [3,5,1,7,2,4] 
for j in range(1,len(list)): 
    i = j-1; 
    while i>=0 and list[i]>list[j]: 
     i = i-1; 
    swap(list, i+1, j) 

Благодаря

+0

Вы их пробовали? (И где вы видите 'swap' в алгоритме CLRS?) – rici

+0

Оба они работают для меня. – user3813674

+0

@ user3886450: Для ясности, чтобы функция сортировки работала, она должна работать на всех входах. Попробуйте второй вариант на разных префиксах '[3, 5, 1, 7, 2, 4]' (и, если хотите, измените '4' на' 6'), и вы увидите, что факт что это привело к тому, что отсортированный список в этом конкретном случае был просто случайным. (Или, возможно, inopportune, поскольку результат заключается в том, чтобы скрыть очевидную ошибку.) – rici

ответ

1

Ни одна из предлагаемых функций фактически не воспроизводит алгоритм, представленный в CLRS.

Код в строках с 5 по 8 в алгоритме CLRS делает поворот подпоследовательности списка, заканчивающегося на индекс j. Это введет значение в индекс j в правильной точке префикса списка.

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

Ваша вторая функция выполняет только один обмен, который перемещает значение в элементе j в нужное место, но не сохраняет порядок остальной части префикса списка. Так что это намного быстрее, но приводит к некорректному результату. (То, что это привело к сортировке вывода с вашим тестовым вектором, забавно, но если вы посмотрите на последовательные префиксы в каждой точке вставки, вы увидите, что это действительно не работает. Попробуйте отсортировать только [2, 3, 1], например .)

-1

Оба правильны и оба выполняются в O (n^2) но вторая реализация лучше, потому что для каждого элемента списка используется только 1 своп, тогда как для первой реализации вы выполняете O (n^2) свопы. Первая реализация заменяет номер вне места с следующим номером до тех пор, пока номер не будет в правильном месте, тогда как вторая реализация найдет правильный индекс для номера вне места, прежде чем подставить номер в его окончательную правильную позицию. Хотя свопы - это время O (1), они занимают больше времени, чем просто уменьшают число.

+0

Возможно, вам стоит попробовать второй вариант с более широким выбором входов. Должно быть очевидно, что он не работает, потому что одного свопа недостаточно для вставки значения в отсортированный список. – rici

+0

О чем ты говоришь? Он работает. И одного свопа определенно достаточно. – ghui

+0

Попробуйте использовать входной вектор '[3,5,1,7,2,6]'. Или просто '[3, 5, 1]'. Тот факт, что он работал с '[3, 5, 1, 7, 2, 4]', был чистой удачей. (И как бы вы конвертировали '[3, 5, 1]' в '[1, 3, 5]' с одним свопом? Кажется очевидным, что одного свопа недостаточно, достаточно одного * вращения *). – rici

 Смежные вопросы

  • Нет связанных вопросов^_^