Common Sorting Algorithms

A sorting algorithm is an algorithm that puts elements of a list into an order. Most frequently we’re required to sort data structures such as arrays, linked lists etc having numerical values.

There’re various algorithms to sort a container or a data structure. In this post, we’ll discuss most popular or commonly used algorithms except Merge sort and Quick sort, as these two have already been discussed here.

Consider the given Array: {5, 3, 2, 4, 1}

Bubble Sort

// arr[] = {5, 3, 2, 4, 1}
int* BubbleSort (int arr[], int n) {

  for (int i=0; i<n; i++) {
    for (int j=0; j<n-i-1; j++) {

      if (arr[j+1] < arr[j]) {
         swap (arr[j], arr[j+1]);
      }
    }
  }

  return arr;
}

Output

Bubble Sort:
Array after 1 iteration: 
3 2 4 1 5 
Array after 2 iteration: 
2 3 1 4 5 
Array after 3 iteration: 
2 1 3 4 5 
Array after 4 iteration: 
1 2 3 4 5 
Array after 5 iteration: 
1 2 3 4 5 

Bubble sort is the simplest of sorting algorithms and that is why it is often used to introduce sorting to students. Notice, how after each iteration the largest element ‘bubble’ up to the last.

Time complexity: O(n²)
Auxiliary Space: O(1)

Insertion Sort

// arr[] = {5, 3, 2, 4, 1}
int* InsertionSort (int arr[], int n) {

  for (int i=1; i<n; i++) {
    int j = i;

    while (j>0 && arr[j-1] > arr[j]) {
      swap (arr[j-1], arr[j]);
      j--;
    }
  }

  return arr;
}

Output

Insertion Sort:
Array after 1 iteration: 
3 5 2 4 1 
Array after 2 iteration: 
2 3 5 4 1 
Array after 3 iteration: 
2 3 4 5 1 
Array after 4 iteration: 
1 2 3 4 5 

Insertion sort works similar to the way you sort playing cards. The array is virtually split into a sorted and an unsorted part. At each iteration, Insertion sort removes one element from the unsorted part, and inserts it at its appropriate location in the sorted part. It repeats until no input elements remain.

Time Complexity: O(n²) 
Auxiliary Space: O(1)

Selection Sort

// arr[] = {5, 3, 2, 4, 1}
int* SelectionSort (int arr[], int n) {
  for (int i=0; i<n; i++) {
      int indexMin = i;

      for (int j = i+1; j<n; j++) {
         if (arr[j] < arr[indexMin]) {
            indexMin = j;
         }
      }

      if (indexMin != i) {
         swap (arr[indexMin], arr[i]);
      }
  }

  return arr;
}

Output

Selection Sort:
Array after 1 iteration: 
1 3 2 4 5 
Array after 2 iteration: 
1 2 3 4 5 
Array after 3 iteration: 
1 2 3 4 5 
Array after 4 iteration: 
1 2 3 4 5 
Array after 5 iteration: 
1 2 3 4 5 

At the end of the each ith iteration of the first for loop, ith (smallest) number is placed at the ith place. One advantage that Selection sort has over other sorting algorithms is that it makes the minimum possible number of swaps.

Time Complexity: O(n²) 
Auxiliary Space: O(1)

Read more here:

Here’s a working example: Sorting Algorithms