Ошибка с установкой Сортировка Python

Question

Я пытаюсь реализовать сортировку вставки с помощью python. Это мой код:

def insertionSort(lst): 
    lstSorted = [lst[0]] 
    for i in range(1,len(lst)): 
     index = len(lstSorted)-1 
     while index >= 0: 
      if lst[i] > lstSorted[index]: 
       lstSorted.insert((index+1),lst[i]) 
      else: 
       lstSorted.insert(index,lst[i]) 
      index -= 1 
    return lstSorted 



def main(): 
    lst = [100,10,10000,1000,1000000,10000] 
    sortedLst = insertionSort(lst) 
    print(sortedLst) 

main() 

Это выход:

[10, 10000, 10000, 1000000, 1000, 10000, 10000, 1000000, 1000, 10000, 10000, 1000000, 10000, 10000, 10000, 1000000, 100, 10000, 10000, 1000000, 1000, 10000, 10000, 1000000, 1000, 10000, 10000, 1000000, 10000, 10000, 10000, 1000000] 

Я понимаю, что есть ошибка с моей «index- = 1», но я не уверен, как это исправить , Это проблема, когда он получает:

10, 100, 10000 

петля в то время как никогда не нарушается из потому, что индекс равен 0, так что цикл, пока работает снова, так что становится:

10, 10000, 100, 10000 

Как я почини это?

Answer 1

Что происходит, каждый раз, когда вы делаете if, и он проходит, он будет вставлять элемент перед ним. Попробуйте это,

def insertionSort(lst): 
    for i in range(1,len(lst)): 
     j = i 
     while j > 0: 
      if lst[j-1] > lst[j]: 
       t=lst[j] 
       lst[j]=lst[j-1] 
       lst[j-1]=t 
      j-= 1 
    return lst 

def main(): 
    lst = [100,10,10000,1000,1000000,10000] 
    sortedLst = insertionSort(lst) 
    print(sortedLst) 

main() 

Что вы делаете, если элемент в LST больше, чем элемент в lstSorted вы вставляли LST элемент после lstSorted element.But если меньше вы добавить его перед элементом в lstSorted и затем уменьшая индекс и снова сравнивая. Так, если список [5,4,3] Первый цикл lstSorted становится [4,5] Но вторая петля становится [3,4,3,5] Что вы должны сделать, это выбрать подходящее место, чтобы положить в lst[i] и только затем вставьте его там.

Так что если вы хотите отдельный список, то вы можете изменить ваш скрипт для

def insertionSort(lst): 
    lstSorted = [lst[0]] 
    for i in range(1,len(lst)): 
     index = i-1 
     while index >= 0: 
      if lst[i] > lstSorted[index]: 
       lstSorted.insert((index+1),lst[i]) 
       break 
      index -= 1 
     if index==-1: 
       lstSorted.insert(0,lst[i]) 
    return lstSorted 

def main(): 
    lst = [100,10,10000,1000,1000000,10000] 
    sortedLst = insertionSort(lst) 
    print(sortedLst) 

main() 

Answer 2

Проблема у вас есть то, что вы повторно вставить то же значение в ваш отсортированный список в вашем while цикле. Вы хотите только вставить один раз (за цикл цикла for), поэтому вам нужно немного изменить свою логику.

Самое простое изменение было бы добавить break после первого insert вызова, а затем переместить else блок из if к петле while (и изменить индекс вставки в 0). Это использует относительно необычную особенность Python, что петли могут иметь блоки else, которые запускаются только в том случае, если цикл завершался без указания break.

def insertionSort(lst): 
    lstSorted = [lst[0]] 
    for i in range(1,len(lst)): 
     index = len(lstSorted)-1 
     while index >= 0: 
      if lst[i] > lstSorted[index]: 
       lstSorted.insert(index + 1, lst[i]) 
       break  # stop the while loop after inserting 
      index -= 1 
     else:    # if we reached index -1 without breaking, insert at the start 
      lstSorted.insert(0, lst[i]) 
    return lstSorted 

Вы могли заметить, однако, что insert по индексу 0 на самом деле еще index+1, так же как и другие вставки вызова, чтобы мы могли на самом деле объединить оба случая в один. Я думаю, что это довольно немного элегантно:

def insertionSort(lst): 
    lstSorted = [lst[0]] 
    for i in range(1,len(lst)): 
     index = len(lstSorted)-1 
     while True: # loop until a break is reached 
      if index < 0 or lst[i] > lstSorted[index]: # combine both insert cases 
       lstSorted.insert(index + 1, lst[i]) 
       break 
    return lstSorted