Problem scenario
You want to use BubbleSort in Python that runs in O(n) time when the list to be sorted is already in perfect order.  How do you write such a program?

Solution
Use this code for BubbleSort with a refinement:

def refinedBubbleSort(coollist):
needtoswap = True
x = len(coollist)-1 # x is now the index value of last item in list
while x 0 and needtoswap:
needtoswap = False
for i in range(x): # start with leftmost number and iterate to the xth position one space at a time
if coollist[i] coollist[i+1]: # swap if left item in pair is greater than right item
needtoswap = True
coollist[i],coollist[i+1] = coollist[i+1],coollist[i]
x = x-1 # Go through the list from rightmost item until the leftmost item
coollist = [1,2,3,4,5,6,7,8,9,10]
refinedBubbleSort(coollist)
print(coollist) …

Continue reading “How Do You Write a BubbleSort Algorithm in Python That Runs in O(n) in a Best Case Scenario?”