實現短泡沫和冒泡排序

Question

Bubble sort

的在上述URL可清楚地寫入的短泡在冒泡排序的修改，以減少傳遞的數量。 因此，在我的兩個算法的實現中，我添加了一個計數器來計算通過次數，並且令人驚訝的是兩者都有相同的數字。的通行證。 這裏是我的代碼：

def bubbleshort(mylist): 
    flag= True 
    passnum= len(mylist) -1 
    counter = 0 
    while flag and passnum > 0: 
      flag = False 

      for element in range(passnum): 
       if mylist[element] > mylist[element + 1]: 
       flag = True 

       temp= mylist[element] 
       mylist[element]= mylist[element+1] 
       mylist[element + 1] = temp 
       counter += 1 
      passnum -= 1 
    return mylist, counter 

def bubble(yourlist): 
    count=0 
    for i in range(len(yourlist)-1, 0, -1): 
     for swap in range(i): 
      if yourlist[swap] > yourlist[swap + 1]: 
       temp=yourlist[swap] 
       yourlist[swap]=yourlist[swap + 1] 
       yourlist[swap + 1]= temp 
       count+= 1 
    return yourlist, count 

mylist = [20,30,40,90,50,60,70,80,100,110] 
mylistx = [20,30,40,90,50,60,70,80,100,110] 
sortedList, counter= bubbleshort(mylist) 
sortList, count= bubble(mylistx) 
print(sortedList,counter) 
print(sortList,count) 

而且如果我通過同一份名單，無論是泡沫的功能是生成零數，但仍給人一種排序列表的功能。 所以有人可以告訴我什麼是修改的目的，當沒有。的通行證是一樣的。他們也許有機會實施我的計數器是錯誤的，爲什麼我會得到錯誤的答案。

Answer 1

它確實取決於輸入列表兩個函數是否通過相同的遍數。

例如，像[9,1,2,3,4,5,6,7,8]這樣的幾乎排序的列表只需要兩次傳遞用於短氣泡函數，而總是需要8次（n-1）傳遞用於常規氣泡函數。