AlgoDaily

A Sorting Algorithms Cheat Sheet

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Sorting Algorithms

A Sorting Algorithms Cheat Sheet

Today, we're diving into the fascinating world of sorting algorithms. A sorting algorithm is like a recipe for arranging a collection of elements (think Arrays, Hashes, and more) in a specific order.

Two Families of Sorting Algorithms

When it comes to sorting algorithms, they generally fall into one of two camps:

Comparison-Based Sorting Algorithms
  • What They Do: These algorithms rely on comparing elements with each other to figure out their correct order.
  • Complexity Bound: These are limited by a complexity of $$O(n \log n)$$.
Non-Comparison-Based Sorting Algorithms
  • What They Do: These smart algorithms use extra information and tactics, bypassing element-to-element comparisons to achieve sorting.
  • Complexity Bound: These are not restricted to the $$O(n \log n)$$ complexity.

For further reading, check out this guide.

Criteria for Evaluating Sorting Algorithms

Before we dive into the specifics, let's establish the criteria we'll use to evaluate each sorting algorithm:

  1. Time Complexity: How long does the algorithm take to give you a sorted collection?
  2. Space Complexity: What's the memory footprint for executing the sort?
  3. Best Use Cases: This is about understanding the context—what type of data structure are you sorting, and what's the scenario?

Algorithms on the Examination Table

In this tutorial, we'll take a closer look at four different sorting algorithms and dissect their inner workings. We'll even throw in some simulations for good measure. Here's the list of algorithms up for discussion:

  1. Selection Sort
  2. Insertion Sort
  3. Merge Sort
  4. Bubble Sort

Selection Sort

Selection Sort:

This algorithm is an in-place comparison-based algorithm that divided the list into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

The working of the selection sort algorithm is simulated in the below-mentioned figure:

Here's some pseudo-code to follow:

procedure selection sort
   arr  : array of items
   N    : size of list

   for i = 1 to N - 1
   /* set current element as minimum*/
      min = i      
      /* check the element to be minimum */
      for j = i+1 to N
         if arr[j] < arr[min] then
            min = j;
         end if
      end for
      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap arr[min] and arr[i]
      end if
   end for

end procedure

Time Complexity: O(N2)

Space Complexity: O(1)

Best Suited Scenario:

The selection sort algorithm is best suited with Array data structures and the given collection is in completely unsorted order. This algorithm is not feasible for a very large number of data set and this is likely due to its time complexity.

```js
const selectionSort = function(array) {
    let temp;

    for (let i = 0; i < array.length; i++){
        let minimum = i;
        
        for (let j = i + 1; j<array.length; j++) {
            if (array[j] < array[minimum])
                minimum = j;
        }

        temp = array[i];
        array[i] = array[minimum];
        array[minimum] = temp;
    }

    return array;
};

console.log(selectionSort([1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7]));
```
```py
def selection_sort(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            if array[j] < array[i]:
                temp = array[j]
                array[j] = array[i]
                array[i] = temp
    return array

print(selection_sort([1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7]));
```
```java
public class Main {
    public static void selectionSort(int[] array) {
        int temp;

        for(int i = 0; i < array.length; i++) {
            int minimum = i;

            for(int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minimum]) 
                    minimum = j;
            }

            temp = array[i];
            array[i] = array[minimum];
            array[minimum] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
        selectionSort(arr);
        for(int i : arr) 
            System.out.println(i);
    }
}
```
```cpp
#include<iostream>
#include<vector>

void selectionSort(std::vector<int>& array) {
    int temp;

    for(int i = 0; i < array.size(); i++) {
        int minimum = i;

        for(int j = i + 1; j < array.size(); j++) {
            if(array[j] < array[minimum]) 
                minimum = j;
        }

        temp = array[i];
        array[i] = array[minimum];
        array[minimum] = temp;
    }
}

int main() {
    std::vector<int> arr = {1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
    selectionSort(arr);
    for(int i : arr) 
        std::cout << i << std::endl;

    return 0;
}
```
```csharp
public class Program {
    public static void SelectionSort(int[] array) {
        int temp;

        for(int i = 0; i < array.Length; i++) {
            int minimum = i;

            for(int j = i + 1; j < array.Length; j++) {
                if(array[j] < array[minimum]) 
                    minimum = j;
            }

            temp = array[i];
            array[i] = array[minimum];
            array[minimum] = temp;
        }
    }

    public static void Main() {
        int[] arr = new int[]{1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
        SelectionSort(arr);
        foreach(var i in arr) 
            System.Console.WriteLine(i);
    }
}
```
```go
package main

import "fmt"

func selectionSort(array []int) {
    
    for i := 0; i < len(array); i++ {
        minimum := i

        for j := i + 1; j < len(array); j++ {
            if array[j] < array[minimum] {
                minimum = j
            }
        }
        
        array[i], array[minimum] = array[minimum], array[i]
    }
}

func main() {
    array := []int{1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7}
    selectionSort(array)
    for _, i := range array {
        fmt.Println(i)
    }
}
```

Insertion Sort

Insertion Sort:

This algorithm lies in the category of in-place comparison-based sorting algorithms. In this algorithm, a sub-collection is maintained which is always in order(sorted). For example, the lower part of an array is maintained to be ordered. An element that is to be added in this sorted collection has to find its correct place, and then it has to be inserted there. That’s why the algorithm is named ‘Insertion Sort’.

This sorting algorithm is basically a simple sorting algorithm that works similar to the way you sort the playing cards. The collection is virtually split into an ordered and an unordered part. Elements from the unordered portion are picked and placed at the correct index in the ordered part.

The working of the insertion sort algorithm is simulated in the below-mentioned figure:

Here's the pseudocode:

procedure insertionSort( A : collection of items )
   int holePosition
   int valueToInsert

   for i = 1 to length(A) inclusive do:
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      /*locate hole position for the element to be inserted */
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
   end for
end procedure

Time Complexity: O(N2)

Space Complexity: O(1)

Best Suited Scenario:

Insertion sort algorithm is best suited with Array and Linked list data structures and the given collection is in partially unsorted order. This algorithm is not feasible for a very large number of data set and this is likely due to its time complexity.

```js
function insertionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let temp = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        arr[j + 1] = temp;
    }

    return arr;
}

console.log(insertionSort([1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7]));
```
```py
def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = temp
    return arr

print(insertion_sort([1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7]))
```
```java
public static int[] insertionSort(int arr[]) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        arr[j + 1] = temp;
    }

    return arr;
}

public static void main(String args[]) {
    int arr[] = {1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
    arr = insertionSort(arr);
    for(int i: arr){
        System.out.print(i + " ");
    }
}
```
```cpp
#include <iostream>
#include <vector>

std::vector<int> insertionSort(std::vector<int> arr) {
    for (int i = 1; i < arr.size(); i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        arr[j + 1] = temp;
    }

    return arr;
}

int main() {
    std::vector<int> arr = {1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
    arr = insertionSort(arr);
    for(int i: arr){
        std::cout << i << " ";
    }
}
```
```csharp
public static int[] InsertionSort(int[] arr) {
    for (int i = 1; i < arr.Length; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        arr[j + 1] = temp;
    }

    return arr;
}

public static void Main() {
    int[] arr = {1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7};
    arr = InsertionSort(arr);
    foreach (int i in arr) {
        Console.Write(i + " ");
    }
}
```
```go
package main

import (
	"fmt"
)

func insertionSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		temp := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > temp {
			arr[j+1] = arr[j]
			j = j - 1
		}

		arr[j+1] = temp
	}

	return arr
}

func main() {
	arr := []int{1, 3, 6, 7, 4, 8, 9, 1, 4, 6, 7}
	arr = insertionSort(arr)
	for _, i := range arr {
		fmt.Print(i, " ")
	}
}
```

Bubble Sort

Bubble Sort:

Bubble sort, also categorized as a “comparison-based” sorting algorithm, is a simple sorting algorithm that repeatedly goes through the collection, compares adjacent elements, and swaps them if they are not in sorted order. This is the simplest algorithm and inefficient at the same time. Yet, it is very important to learn about it as it represents the basic foundations of sorting. To perform sorting by this algorithm, the adjacent elements in the collection are compared and the positions are swapped if the first element is greater than the second one. In this way, the largest valued element "bubbles" to the top. Usually, after each loop, the elements furthest to the right are in sorted order. The process is continued until all the elements are in sorted order.

The working of bubble sort algorithm is simulated in below mentioned figure:

Here's the pseudocode:

procedure bubbleSort( arr[]: collection of elements, N: size of collection)
   for i = 0 to N - 1 do:
      swapped = false   
      for j = 0 to N - i - 2 do:
         if arr[j] > arr[j+1] then
            swap(arr[j], arr[j+1])      
            swapped = true
         end if
      end for
      if(not swapped) then
         break
      end if
   end for
end

Time Complexity: O(N2)

Space Complexity: O(1)

Best Suited Scenario:

Bubble sort algorithm is best suited with most of the data structures and the given collection is in completely unsorted order. This algorithm is not feasible for very large number of data set and this is likely due to its time complexity.

```js
const bubbleSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            };
        };
    };
    return arr;
}

console.log(bubbleSort([5, 4, 3, 2, 1]));
```
```py
def bubble_sort(arr):
    size = len(arr)
    for i in range(size - 1):
        for j in range(size - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

print(bubble_sort([5, 4, 3, 2, 1]));
```
```java
public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
```
```cpp
#include <iostream>
#include <algorithm>

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    int size = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, size);
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}
```
```csharp
using System;

class Program {
    static void Main() {
        int[] arr = {5, 4, 3, 2, 1};
        BubbleSort(arr);
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
    }

    static void BubbleSort(int[] arr) {
        int size = arr.Length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
```
```go
package main

import (
	"fmt"
)

func main() {
	arr := []int{5, 4, 3, 2, 1}
	bubbleSort(arr)
	for _, num := range arr {
		fmt.Print(num, " ")
	}
}

func bubbleSort(arr []int) {
	size := len(arr)
	for i := 0; i < size-1; i++ {
		for j := 0; j < size-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}
```

Merge Sort

Merge Sort:

This is a Divide and Conquer algorithm. It divides the input collection into two portions, recursively calls itself for the two divided portions, and then merges the two sorted portions. This is one of the most efficient algorithms. Merge Sort Algorithm works in three parts:

  1. Divide: At first, it divides the given collection of elements into two equal halves and then recursively passes these halves to itself.
  2. Sorting: Unless, there is only one element left in each half, the division continues, after that, those two end elements (leaf nodes) are sorted.
  3. Merging: Finally, the sorted arrays from the top step are merged in order to form the sorted collection of elements

The working of the merge sort algorithm is simulated in below-mentioned figure:

Here's the pseudocode:

procedure mergesort( var a as array )
   if ( n == 1 ) return a
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while



   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c
end procedure

Time Complexity: O(NlogN)

Space Complexity: O(N)

Best Suited Scenario:

The merge sort algorithm is best suited with most of the data structures and the given collection is in completely unsorted order. This algorithm is feasible for a very large number of data set and this is likely due to its time complexity.

```js
function merge(leftArr, rightArr) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;

  // Sort parts
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      resultArray.push(leftArr[leftIndex]);
      leftIndex++; // move left array cursor
    } else {
      resultArray.push(rightArr[rightIndex]);
      rightIndex++; // move right array cursor
    }
  }

  // There will be one element remaining from either left or the right
  // Concat to account for it
  return resultArray
          .concat(leftArr.slice(leftIndex))
          .concat(rightArr.slice(rightIndex));
}

function mergeSort(unsortedArr) {
  // Only one element base case
  if (unsortedArr.length <= 1) {
    return unsortedArr;
  }

  // Determine midpoint
  const midIdx = Math.floor(unsortedArr.length / 2);

  // Divide the array into left and right
  const leftArr = unsortedArr.slice(0, midIdx);
  const rightArr = unsortedArr.slice(midIdx);

  // Recursively merge
  return merge(
    mergeSort(leftArr), mergeSort(rightArr)
  );
}

console.log(mergeSort([5, 4, 3, 2, 1]));
```
```py
def merge(a, b, c=[]):
    if len(a) == 0:
        return c + b
    elif len(b) == 0:
        return c + a
    else:
        a_first = a[0]
        b_first = b[0]
        if a_first <= b_first:
            return merge(a[1:], b, c + [a_first])
        else:
            return merge(a, b[1:], c + [b_first])

def merge_sort(arr):
    length = len(arr)
    if length < 2:
        return arr
    else:
        mid = length // 2   
        return merge(merge_sort(arr[0:mid]), merge_sort(arr[mid:]))

print(merge_sort([5, 4, 3, 2, 1]));
```
```java
void merge(int leftArr[], int rightArr[], int resultArray[], int left, int mid, int right) {
	int leftIndex = 0, rightIndex = 0, resultArrayIndex = left;

	while (leftIndex < mid - left + 1 && rightIndex < right - mid) {
		if (leftArr[leftIndex] <= rightArr[rightIndex]) {
			resultArray[resultArrayIndex] = leftArr[leftIndex];
			leftIndex++;
		} else {
			resultArray[resultArrayIndex] = rightArr[rightIndex];
			rightIndex++;
		}
		resultArrayIndex++;
	}

	while (leftIndex < mid - left + 1) {
		resultArray[resultArrayIndex] = leftArr[leftIndex];
		leftIndex++;
		resultArrayIndex++;
	}

	while (rightIndex < right - mid) {
		resultArray[resultArrayIndex] = rightArr[rightIndex];
		rightIndex++;
		resultArrayIndex++;
	}
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
		int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);

		mergeSort(leftArr, 0, mid - left);
		mergeSort(rightArr, 0, right - mid - 1);

		merge(leftArr, rightArr, arr, left, mid, right);
	}
}

void printArray(int arr[]) {
	for (int num : arr) {
		System.out.print(num + " ");
	}
	System.out.println();
}

public static void main(String args[]) {
	int arr[] = {5, 4, 3, 2, 1};

	mergeSort(arr, 0, arr.length - 1);

	printArray(arr);
}
```
```csharp
static void Merge(int[] left, int[] right, int[] arr, int leftLen, int rightLen) {
	int i = 0, j = 0, k = 0;

	while (i < leftLen && j < rightLen) {
		if (left[i] <= right[j]) {
			arr[k] = left[i];
			i++;
		} else {
			arr[k] = right[j];
			j++;
		}
		k++;
	}

	while (i < leftLen) {
		arr[k] = left[i];
		i++;
		k++;
	}

	while (j < rightLen) {
		arr[k] = right[j];
		j++;
		k++;
	}
}

static void MergeSort(int[] arr, int n) {
	if (n < 2)
		return;

	int mid = n / 2;
	int[] left = new int[mid];
	int[] right = new int[n - mid];

	for (int i = 0; i < mid; i++)
		left[i] = arr[i];
	for (int i = mid; i < n; i++)
		right[i - mid] = arr[i];

	MergeSort(left, mid);
	MergeSort(right, n - mid);

	Merge(left, right, arr, mid, n-mid);
}

public static void Main() {
	int[] arr = {5, 4, 3, 2, 1};
	MergeSort(arr, arr.Length);
	Console.WriteLine(string.Join(" ", arr));
}
```
```cpp
void merge(int left[], int right[], int arr[], int leftLen, int rightLen) {
	int i = 0, j = 0, k = 0;
	while (i < leftLen && j < rightLen) {
		if (left[i] <= right[j]) {
			arr[k] = left[i];
			i++;
		} else {
			arr[k] = right[j];
			j++;
		}
		k++;
	}
	while (i < leftLen) {
		arr[k] = left[i];
		i++;
		k++;
	}
	while (j < rightLen) {
		arr[k] = right[j];
		j++;
		k++;
	}
}

void mergeSort(int arr[], int n) {
	if (n < 2)
		return;

	int mid = n / 2;
	int left[mid], right[n - mid];

	for (int i = 0; i < mid; i++)
		left[i] = arr[i];
	for (int i = mid; i < n; i++)
		right[i - mid] = arr[i];

	mergeSort(left, mid);
	mergeSort(right, n - mid);

	merge(left, right, arr, mid, n - mid);
}

int main() {
	int arr[] = {5, 4, 3, 2, 1};
	int len = sizeof(arr) / sizeof(arr[0]);

	mergeSort(arr, len);

	for(int i = 0; i < len; i++)
		std::cout << arr[i] << " ";
	std::cout << std::endl;

	return 0;
}
```
```go
package main

import "fmt"

func merge(left, right []int) []int {
	size, i, j := len(left)+len(right), 0, 0
	result := make([]int, size)

	for k := 0; k < size; k++ {
		if i > len(left)-1 && j <= len(right)-1 {
			result[k] = right[j]
			j++
		} else if j > len(right)-1 && i <= len(left)-1 {
			result[k] = left[i]
			i++
		} else if left[i] < right[j] {
			result[k] = left[i]
			i++
		} else {
			result[k] = right[j]
			j++
		}
	}
	return result
}

func mergeSort(items []int) []int {
	if len(items) < 2 {
		return items
	}

	mid := len(items) / 2
	return merge(mergeSort(items[:mid]), mergeSort(items[mid:]))
}

func main() {
	items := []int{5, 4, 3, 2, 1}
	fmt.Println(mergeSort(items))
}
```

One Pager Cheat Sheet

One Pager Cheat Sheet

  • In this tutorial, we'll be discussing some important aspects of the sorting algorithms, namely Time Complexity, Space Complexity, and Best Suited Scenarios and Data Structures, as well as providing a simulation of Selection Sort, Insertion Sort, Merge Sort and Bubble Sort.
  • The selection sort algorithm is a comparison-based approach with a time complexity of O(N2), making it best suited for an array data structure with a small, completely unsorted collection.
  • Insertion sort is an in-place comparison-based sorting algorithm that works best with partially unsorted collections and has a time complexity of O(N2).
  • Bubble sort is an inefficient comparison-based sorting algorithm that iterates through a collection and swaps adjacent elements, allowing the largest value to "bubble" up to the top, with Time Complexity O(N2) and Space Complexity O(1).
  • Merge Sort is a Divide and Conquer algorithm that divides an input collection into two portions, recursively calls itself to sort them, and then merges the two sorted portions, with Time Complexity O(NlogN) and Space Complexity O(N), best suited for large, unsorted collections of data.
Open interactive view →