One of the most common operations in programming is sorting a collection. Generally, this is a costly operation for most algorithms, as sorting has the notion of comparing every element with each other. We will see which algorithms overcome this with divide and conquer techniques, and how the simpler linear sorting algorithms are implemented. We will also discuss the complexity of each algorithm.
Table of Contents
Bubble Sort
Bubble sort is a very simply sorting algorithm. This algorithm doesn't have particular use cases other than have an introduction to the sorting algorithms for education purposes.
Bubble Sort algorithm loops through an array and compares two adjacent elements. Depending a condition, we determine if we require to switch the elements. In this way it is bubbling up the maximum value to the end of the array.
For each pair, we compare if the first element is greater than the second then the two elements are swapped. Otherwise, we continue with the next pair of elements.
Pseudocode
Look at each adjacent pair If two adjacent elements are not in order Swap them and set swap counter to falsy value
Time complexity
Bubble sort is not an ideal sorting algorithm. From the pseudocode, we see that we have to compare pairs. This leads us to think we will have one nested loop! A nested loop makes our time complexity O(n²).
In the best-case scenario, the array is already sorted. With a small optimisation in the algorithm, we can reach a best-case of O(n) (if the array is already sorted.).
Implementation
const bubbleSort = (arr) => {
if (!arr) return;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Optimization
const bubbleSort = (arr) => {
let swapped;
for (let i = 0; i < arr.length; i++) {
swapped = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
}
return arr;
}
Selection Sort
One more algorithm that is used for educational purposes is Selection sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element (or maximum, depending the order) from the unsorted part and putting it at the beginning. In every iteration, the minimum (or maximum) element from the unsorted subarray is picked and moved to the sorted subarray.
Pseudocode
Repeat in the unsorted array:
Search the unsorted data to find the smallest value
Swap the smallest value with the first unsorted element
Time Complexity
This search algorithm compares elements in an array to the first element. When it finds the smaller of the two elements, it swaps it to the first position. The algorithm repeats this pattern until the array is sorted. We can see again that we will need two nested loops to achieve that as we require comparison of pairs. That makes our complexity O(n²).
Implementation
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (arr[min] < arr[i]) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}
Insertion Sort
Insertion sort is a sorting algorithm that works similar to how you sort playing cards in your hands. Weird eh?
The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Insertion sort is efficient for small data values or almost sorted arrays.
The algorithm is simple. We iterate through the array, we pick an element from the unsorted part and we insert it to the correct place.
Pseudocode
The first element of the array is 'sorted'
Repeat to the unsorted part of the array
Find the position of the next unsorted item
Insert into the 'sorted' position by shifting elements
Time complexity
In worst case the array is sorted with the opposite order. And we have to compare and insert in the appropriate position all the elements. That will be a O(n²).
Implementation
const insertionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[0]) {
arr.unshift(arr.splice(i, 1)[0])
} else {
for (let j = 1; j < i; j++) {
if (arr[i] > arr[j - 1] && arr[i] < arr[j]) {
arr.splice(j, 0, arr.splice(i, 1)[0])
}
}
}
}
return arr
}
Merge Sort
Merge sort is using the divide and conquer technique. We will have a mergeSort function that partitions the array and a merge function that merge the partitions.
The main algorithm of merge sort divides the input array into two halves and calls itself with the two halves. This recursion continues until we reach granular components that are sorted. Then we proceed with merging these individual pieces into one result array.
Pseudocode
• Find the mid element of the array. mid = Math.floor((array.length)/2)
• Splice the array in left and right parts
• Call merge sort on (left,mid)
• Call merge sort on (mid+1,right)
• Continue until left is less than right
• Then call merge function to perform a merge of the arrays.
Time Complexity
Merge sort is a complicated algorithm. Dividing the algorithm into halves gives us a great time complexity of O(nlogn). We need an auxiliary result array, and this results in a space complexity of O(n)
Implementation
const mergeSort = (arr) => {
if (arr.length === 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle)
const right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
return [...arr, ...left, ...right]
}
Quick Sort
QuickSort is a Divide and Conquer sorting algorithm. It's much faster than linear sorting algorithms. Quick-sort is a comparison sorting algorithm, meaning that the sorting occurs by iterating through the array and comparing two defined values to a pivot. This pivot determines how to partition the collection. We have different ways to pick the pivot value, and this can affect the complexity of the algorithm.
Pseudocode
While the collection is unsorted
Pick a pivot
Partition the array
All values smaller than pivot to the left and larger to the right
Perform pivot and partition on the left and the right partition
Time complexity
The performance of this algorithm heavily depends on the pivot. If you always choose the first element as a pivot and we have an already sorted array, the quicksort will try to sort it. Choosing the first element as a pivot will make the call stack really long. This worst-case can reach a complexity of O(n²). The average case though, with a performant pivot is O(nlogn)
const quickSort = (arr, low, high) => {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
const partition = (arr, low, high) => {
const pivot = arr[high];
let i = (low - 1);
for (let j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Other sorting algorithms
Other famous sorting algorithms are:
- Heap Sort
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort algorithm where we first find the minimum element and place it at the beginning. We repeat the same process for the remaining elements. Time complexity: O(N log N).
- Counting Sort
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that are having distinct key-values. Then do arithmetic to calculate the position of each object in the output sequence. Time complexity: O(n)
- Radix Sort
The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.
- Bucket Sort
Bucket sort is mainly useful when input is uniformly distributed over a range. For example, when we want to sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.
Oldest comments (0)