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.
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
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]))
… 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.🐝🐝🐝