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. We’ll discuss most popular or commonly used algorithms except Merge sort and Quick sort which 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.

Time complexity: O(n^2)
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^2) 
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.

Read more here:

Here’s a working example:

https://ideone.com/eirKCJ


Leave a Reply

Your email address will not be published.