In the above URL it is clearly written that short bubble is a modification in bubble sort to reduce the number of passes. So in my implementation of both the algorithms i have added a counter which counts the number of passes and surprisingly both are having same no. of passes. Here is my code:
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)
Also if i pass same list to both the functions the the bubble function is producing zero counts but is still giving a sorted list. So can anybody tell me what exactly is the purpose of modification when the no. of passes are same. Their maybe a chance that my implementation of counter is wrong that why i am getting wrong answers.
It really depends on the input list whether the two functions go through the same number of passes.
For example, an almost sorted list like [9,1,2,3,4,5,6,7,8] takes only two passes for the short bubble function while it always takes 8 (n-1) passes for the regular bubble function.