This is not a tutorial nor am I an expert in anything here. I am learning and documenting as I learn. Things here may be wrong, feel free to point them out and reach out to me :)
Introduction
Since exiting university I haven’t really kept up with my algorithms and data structures, so here I am writing up this post to dump all I can remember. This post will cover the most basic sorting algorithms. Subsequent posts will cover additional sorting algorithms such as binary tree sorts, heap sort, and the like.
Algorithms
Bubble Sort
Bubble sort is the easiest to implement sorting algorithm, as it’s very intuitive since it seems to be based on how we as humans sort objects naturally. Simplicity often requires compromise and in this case, the compromise is in the runtime complexity. The algorithm requires 2 nested loops that will in worst case require a $O(n^2)$ and on average be $O(n^2)$
- Worst Case Time Complexity: $O(n^2)$
- Average Case Time Complexity: $O(n^2)$
- Best Case Time Complexity: $O(n)$
1
2
3
4
5
def bubbleSort(arr):
for i in range(len(arr)):
for j in range(i+1,len(arr)):
if (arr[j] < arr[i]):
swap(arr, i, j)
Selection Sort
Selection sort similar to bubble sort uilitizes two loops except the second loop only identifies the smallest value and upon exiting the second loop the smallest value is moved to the front. While slightly faster then bubble sort the worst and average runtime complexity is still $O(n^2)$.
- Worst Case Time Complexity: $O(n^2)$
- Average Case Time Complexity: $O(n^2)$
- Best Case Time Complexity: $O(n^2)$
1
2
3
4
5
6
7
def selectionSort(arr):
for i in range(len(arr)):
minIndex = i
for j in range(i+1, len(arr)):
if (arr[j] < arr[minIndex]):
minIndex = j
swap(rects, i, minIndex)
Insertion Sort
Following the theme of following the bubble sort, structure insertion sort uses two loops with the alteration that the second loop counts down and stops at the previous loop’s current index and on each iteration swaps the previous and current value essentially pushing the smallest value to the front. This is on average and the worst case is still just as bad as bubble and selection sort except in the best case it falls into the $O(n)$ although it should be noted this only occurs when the array is already or mostly sorted.
- Worst Case Time Complexity: $O(n^2)$
- Average Case Time Complexity: $O(n^2)$
- Best Case Time Complexity: $O(n)$
1
2
3
4
5
def insertionSort(arr):
for i in range(1,len(arr)):
for j in range(i, 0, -1):
if (arr[j] < arr[j-1]):
swap(arr, j, j-1)
Quick Sort
Moving on to my sorting algorithm of all time, Quick Sort is the bee’s knees. Quick sort uses a recusive process that divides the array into sections sorted off a pviot that was selected randomly or predetermined. The process “divide and conquer” is repeated until the sections is small enough and sorted before backing out. This algorithm is much more complicated and requires more setup before being implemented, this additional complexity yeilds faster runtimes on average with a average of $O(n*log(n))$ and a worst case of $O(n^2)$
- Worst Case Time Complexity: $O(n^2)$
- Average Case Time Complexity: $O(n*log(n))$
- Best Case Time Complexity: $O(n*log(n))$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def quickSort(rects):
qsort(rects, 0, len(rects)-1)
def qsort(rects, lo, hi):
if (hi <= lo):
return
piv = partition(rects, lo, hi)
qsort(rects, lo, piv-1)
qsort(rects, piv+1, hi)
def partition(rects, lo, hi):
pivot = rects[lo]
i = lo
j = hi + 1
while True:
i += 1
while (rects[i] < pivot):
if (i == hi):
break
i += 1
j -= 1
while (pivot < rects[j]):
if (j == lo):
break
j -= 1
if (i >= j):
break
swap(rects, i, j)
swap(rects, lo, j)
return j
Merge Sort
I have not completed the code for this algorithm yet.
Lastly, merge sort is the last of these basic sorting algorithms. This is the most complex out of all these algorithms, the process this algorithm uses to sort arrays is similar to quick sort except once the division reaches the smallest possible number of elements (1). The algorithm merges resulting subarrays and sorts them while doing so. This creates the fastest worst-case time complexity thus far, with a big O of $O(n*log(n))$
- Worst Case Time Complexity: $O(n*log(n))$
- Average Case Time Complexity: $O(n*log(n))$
- Best Case Time Complexity: $O(n*log(n))$
Algorithm Visualization
So to help visualize how these algorithms I have created a basic python script that renders n number of rectangles of various heights and uses these sorting algorithms to sort them from shortest to tallest. To use this script simply clone this git repo and navigate to the Algorithms directory and simply execute the following command in the terminal. The main script takes two arguments the first being the size of the array and the second is the name of the desired algorithm to visualize.
1
python .\main.py 115 bubblesort
