Вставка Сортировка: Неверный вывод

Question

Я пытаюсь узнать больше об алгоритме сортировки вставки, написав небольшой скрипт, однако я застрял.

Все работает отлично, за исключением того, что один номер отображается несколько раз.

Мой код:

# 
# Insertion Sort 
# 

def _ord(l): 
lst=[] 
for k in l: 
    if not lst: 
    lst.append(k) 
    continue 

    for a,b in enumerate(reversed(lst)): 
    if k <= lst[a]: 
    lst.insert(a,k) 

    if a == len(lst)-1: 
    lst.append(k) 

return lst 

if __name__ == '__main__': 
l = [3,2,4,6,5,1] 
print _ord(l) 

Выход:

[1, 1, 1, 1, 1, 2, 3, 4, 5, 6] 

Answer 1

def _ord(l): 
    lst=[] 
    for k in l: 
     print k 
     if not lst: 
      lst.append(k) 
      continue 

     for a,b in enumerate(reversed(lst)): 
      print a, b 
      if k <= lst[a]: 
       lst.insert(a,k) 
       break # <-- add this 

      if a == len(lst)-1: 
       lst.append(k) 
     print lst 
     print '-' * 80 

    return lst 


l = [3,2,4,6,5,1] 
print _ord(l) 

Вы можете использовать print или pdb для отладки кода.

Answer 2

Проблема здесь, когда k=1, k <= lst[a] составляет True для любых других целых чисел в списке, поэтому он вставлен пять раз.

Быстрое исправление для фрагмента ввести break точку:

def _ord(l): 
lst=[] 
for k in l: 
    if not lst: 
    lst.append(k) 
    continue 

    for a,b in enumerate(reversed(lst)): 
    if k <= lst[a]: 
    lst.insert(a,k) 
    break 
    if a == len(lst)-1: 
    lst.append(k) 

return lst 

if __name__ == '__main__': 
l = [3,2,4,6,5,1] 
print _ord(l) 

EDIT: Взгляните на this link для того, чтобы проверить выполнение вашего фрагмента.

Answer 3

def _old(l): 
    for i in range(1, len(l)): 
     tmp = l[i] 
     for j in reversed(range(i)): 
      if l[j] > tmp: 
       l[j+1] = l[j] 
       l[j] = tmp 
      else: 
       break 
    return l 

if __name__ == '__main__': 
    l = [3,2,4,6,5,1] 
    print(_old(l))