Question

# Implement the Bubble Sort algorithm to this code. Add output statements to the code to verify that it is working properly. Then, add code that will short circuit the sort process if at any time an intermediate pass through the list identifies that the entire list is already sorted.

def bubbleSort(theSeq):

n = len(theSeq)

#perform n - 1 bubble operations on the sequence

for i in range(n - 1):

#bubble largest item to end

for j in range(i + n - 1):

if theSeq[j] > theSeq[j + 1]: # swap the j and j + 1 items

tmp = theSeq[j]

theSeq[j] = theSeq[j + 1]

theSeq[j + 1] = tmp

Answer 1

def bubbleSort(theSeq):
    n = len(theSeq)
    # perform n - 1 bubble operations on the sequence
    for i in range(n - 1):
        # bubble largest item to end
        num_swaps = 0
        for j in range(0, n - i - 1):
            if theSeq[j] > theSeq[j + 1]:  # swap the j and j + 1 items
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                num_swaps += 1
        if num_swaps == 0:
            break


lst = [4, 9, 1, 6, 0, 2]
print("Original list is", lst)
bubbleSort(lst)
print("Sorted list is", lst)