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

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)  

Leave a comment

Your email address will not be published. Required fields are marked *