13th April, 2017

Bubble sort in Python

A bubble sort algorithm in Python 3.5.

This is a simple script that sorts lists (of arbitrary lengths) of unsorted numbers from lowest to highest. https://en.wikipedia.org/wiki/Bubble_sort.

Bubble sort is a very simple sorting algorithm that works by iterating over all elements in an unsorted list and comparing the current element to the element to its immediate right - if the element to the right is greater than the current element, swap both elements. This process continues until no more swaps occur - meaning all elements must be sorted. Sorting numbers in this way causes the largest numbers to be sorted first; bubble sort causes the largest numbers to all “bubble” up the top of the list - which is where the name comes from.

The worst-case performance and complexity of the bubble sort algorithm can be described by the following Big O notation equation: O(n^2).
Bubble sort requires nested loops - meaning it must (at worst) perform n^2 comparisons - n representing the number of elements in the unsorted list. Although bubble sort works well with small unsorted lists, its performance decreases significantly as the length of the unsorted list grows - as the number of comparisons increases exponentially.

Speed tests

I have tested this bubble sort algorithm to time how long it takes to sort 100, 1000, and 10,000 unsorted random numbers between 0 and 1000.
Each test was run 3 times (to find the average) using a 2016 MacBook air with a 1.6GHz CPU and 4GB of RAM.
All results are recorded in milliseconds, and averages are rounded to 1 decimal place.

  
100 elements:
    test 1: 7ms
    test 2: 6ms
    test 3: 10ms
    average: 7.7ms
1,000 elements:
    test 1: 436ms
    test 2: 427ms
    test 3: 452ms
    average: 438.3ms
10,000 elements:
    test 1: 59,405ms
    test 2: 58,321ms
    test 3: 59,839ms
    average: 59,188.3ms
  

Source code

  
def sort(list):
    # by default assume the list is not sorted
    is_sorted = False
    # repeat until is_sorted is true
    while not is_sorted:
        # assume the list is sorted
        is_sorted = True
        # for each element and its index in the list
        for pos, value in enumerate(list):
            # keep moving the number until it is greater than the number to its right
            while pos != len(list) -1 and value > list[pos +1]:
                # swap elements
                list[pos +1], list[pos] = list[pos], list[pos +1]
                # if a swap occurred then the list might still be unsorted, so assume the list is not sorted
                is_sorted = False
                # increment the current position
                pos +=1
    # return sorted list
    return list

print(sort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))
  

Example usage

  
…
print(sort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))
# Returns [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  

Thank you for reading.

🐝🐝🐝


Leave a comment

Invalid or missing field(s).
Comment sent successfully, please wait for it to be approved.

This post has no comments