Bubble Sort.ipynb

Kernel: Python 3

The Challenge

Create a program, which, when handed an unsorted list of integer numbers, will sort it from the lowest to highest.

"*Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list. *"

Source: Wikipedia

Prep

First I need a list generated with random numbers in it:

import random
def createList(size):
    lyst = []
    for x in range(size):
        lyst.append(random.randrange(100))
    return lyst

unsortedList = createList(10)
print(unsortedList)

[55, 71, 16, 42, 74, 69, 98, 53, 92, 15]

Now I need define a single sort loop:

def singleSort(lyst):
    for i in range(len(lyst)):
        if i < len(lyst)-1:
            a, b = lyst[i], lyst[i+1]
            if a > b:
                lyst[i], lyst[i+1] = b, a
    print(lyst)
singleSort(unsortedList)

[55, 16, 42, 71, 69, 74, 53, 92, 15, 98]

Logic would dictate that after a single pass over any such list, wherein the largest of neighbouring values is moved a step to the right, the largest value in the entire list must inevitably arrive at the far right after a single loop, as it would always be the largest value in a comparison of any two neighbouring values, and thus always moved to the right. Ergo, the best way to check that the loop above is working is to make sure that the largest value is on the far right.

With the small list size I am using, it is easy to see this is working correctly at a glace, however, with a larger list, I would consider calling max as follows:

max(unsortedList)

98

This confirms that the singleSort function is working correctly.

The next step is to use the code established for the singleSort function in a manner which loops until the list if completely sorted.

My first thought was to use a count to ensure that the sort loop is run on the list once for each item in the list, thus guaranteeing that it is completely arranged:

def bubbleSort(lyst):
    count = 0
    while count != len(lyst)-1:
        for i in range(len(lyst)):
            if i < len(lyst)-1:
                a, b = lyst[i], lyst[i+1]
                if a > b:
                    lyst[i], lyst[i+1] = b, a
        count += 1

bubbleSort(unsortedList)
print(unsortedList)

[15, 16, 42, 53, 55, 69, 71, 74, 92, 98]

Okay, so we can see that it works.

The issue with this solution is that should the list already be sorted, or even finish sorting before all of the loops have been completed, then we are wasting a lot of time allowing the program to run through a sort loop for each item in the list.

This needs to be addressed by implementing a method which will stop the program if no swaps are made in a single loop (signifying that the list is/has been sorted.

I have chosen to use a recursive solution; I have added a counter at the start of the function which is equal to 1 less than the length of the list it is called upon. Each time the if statement is run in an attempt to switch values, and it fails, the counter will be reduced by one. Once the full if statement has finished, if the counter is equal to zero, i.e. no swaps have taken place, the function wil then print the resulting list, otherwise, it will call itself again upon the list.

def bubbleSort(lyst):
    count = len(lyst)-1
    for i in range(len(lyst)):
        if i < len(lyst)-1:
            a, b = lyst[i], lyst[i+1]
            if a > b:
                lyst[i], lyst[i+1] = b, a
            else:
                count -= 1
    if count==0:
        print(lyst)
    else:
        bubbleSort(lyst)

bubbleSort(unsortedList)

[15, 16, 42, 53, 55, 69, 71, 74, 92, 98]

From a quick Google it seems that the generally accepted solution is to add a boolean variable to the start of the function, set it to True, and then use this as a condition to continue running through the function. This is allegedly the next level of solution for the Bubble Sort issue, which goes by the idiomatic names 'Short Bubble', or 'Short Bubble Sort'.

def shortBubbleSort(lyst):
    complete = True
    count = len(lyst)-1
    while count > 0 and complete:
        complete = False
        for i in range(count):
            a, b = lyst[i], lyst[i+1]
            if a > b:
                complete = True
                lyst[i], lyst[i+1] = b, a
        count -= 1

newList = createList(20)
print("Original list:")
print(newList)
shortBubbleSort(newList)
print("\nSorted list:")
print(newList)

Original list:
[65, 86, 23, 3, 25, 67, 26, 97, 93, 62, 74, 7, 37, 69, 43, 16, 63, 7, 19, 60]

Sorted list:
[3, 7, 7, 16, 19, 23, 25, 26, 37, 43, 60, 62, 63, 65, 67, 69, 74, 86, 93, 97]

Some further points worth noting:

"Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position."

"The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm.", "Most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set."

Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

Source: Wikipedia

Mission complete... for now.