Sorting Algorithms You Should Know
When looking at sorting algorithms, there are three simple approaches that you should know; the bubble sort, the insertion sort, and the selection sort. All three approaches have the same worst case time complexity, O(n²), and space complexity, O(1). However, having knowledge of these basic sorting algorithms can serve as a foundation to master the more advanced sorting algorithms (quick sort, merge sort, radix sort). In the next couple of sections we will go through what each algorithm does and implement each one.
Bubble Sort
So first up, we have bubble sort. Bubble sort continuously looks at adjacent elements and swaps them if needed. This is done in-place, meaning the operations are performed on the original input. At the n-th pass in a bubble sort, the last (n-1) numbers in the array are already sorted. This may seem a bit confusing so let’s look at an example.
let array = [3,4,1,2]//First 3 and 4 are compared, no swap is necessary since 3 < 4[3,4,1,2]//Next 4 and 1 are compared, we swap these values since 4 > 1[3,1,4,2]//Next 4 and 2 are compared, we swap these values since 4 > 2[3,1,2,4]//Now that we are done with the first pass, we know the last element
//in the array is in it's correct "sorted" position//We keep making passes on the array until we reach a pass where no
//swaps are necessary, then we know the array is sorted.
As its name suggest, elements continuously “bubble” to the end of the array until it becomes sorted. Below is an implementation of bubble sort in Javascript.
Insertion Sort
Up next we have the insertion sort! As its name suggest, insertion sort takes each element in the array and “inserts” it into its correct position. Insertion sort is also done in-place. Let’s look at an example.
let array = [3,4,1,2]//In an insertion sort, we start at the second element and compare it to the previous element, if it is less, then swap
//In this case, 4 > 3, so no swap necessary[3,4,1,2]//We move on to the next element, 1 is compared to all previous elements
//In this case, 1 < 4, so we perform a swap[3,1,4,2]//Next we see also see 1 < 3, so we perform a swap[1,3,4,2]//We reach the last element in the array
//Next, 2 is compared to all previous elements
//In this case, 2 < 4, so we perform a swap[1,3,2,4]//Next we see also see 1 < 3, so we perform a swap[1,2,3,4]//After "inserting" the final element, the resulting array should be sorted
Below is an implementation of insertion sort in Javascript.
Selection Sort
Last but not least, we have the selection sort! In a selection sort, we essentially “select” the nth smallest element and place it the nth position. This algorithm separates the array into a sorted section (left) and an unsorted section (right). Elements are continuously taken out of the unsorted section and placed in the sorted section. Let’s look at an example.
let array = [3,4,1,2]//In an selection sort, we start at the second element and move along the array until we have found the smallest element//We are looking for the smallest element to place in the 1st position of the "sorted" array section, where 3 is currently//In this case we start at 4 and move along until we find the smallest element, 1//We then swap 1 with 3 and 1 is now in its sort position[1,4,3,2]//Next we move on to 3 and we find the smallest element onward, 2//We then swap the 4 and 2[1,2,3,4]//Lastly we move to the 4, but it is not less than 3 so it stays as is//Our array is now sorted!
Below is an implementation of selection sort in Javascript.
Closing Remarks
Knowing these three basic sorting algorithms will serve as a foundation to learning the more advanced sorting algorithms such as quick sort, merge sort or radix sort. Check out this article on the Merge Sorting algorithm if you think you have these down!
