Sorting Algorithms

Sorting Algorithms in C++

Sorting algorithms are cool. But, every time I learn or refer to any algorithm in my head or watch a YouTube video, I can understand and recall how it works but, my brain starts yelling – write the code! write the code! If you are trying to learn or understand how the sorting algorithms work try VisuAlgo to visualize and play with some examples. Coming to the point the purpose of this post is to refer some websites with good explanation of various sorting algorithms and to act as a bookmark for my simplified code.

Table of Contents

Bubble Sort

Bubble sort is easy to understand and code, I’ve written an article in detail explaining everything step-by-step you can read it here, Bubble Sort Algorithm

Complexity
Space Complexity: O(1)

Time Complexity:
Best Case [Big-omega]: O(N)
Worst Case [ Big-O ]: O(N^2)
Average [Big-theta]: O(N^2)

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size)
{
  for (int step = 0; step < size; ++step)
  {
    for (int i = 0; i < size - step; ++i)
    {
      if (array[i] > array[i + 1])
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

void display(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    cout << " " << array[i];
  cout << " \n";
}

int main()
{
  int data[] = {5, 1, 0, 4, 3, 2};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size - 1);
  cout << "Sorted Array in Ascending Order:\n";
  display(data, size);
  return 0;
}

Insertion Sort

Insertion Sort is also an easy-to-understand sorting algorithm. You can read this Wikipedia article and perform a dry run once on the below code using a pen and paper for better understanding.

Complexity

Space Complexity: O(1)

Time Complexity:
Best Case [Big-omega]: O(N)
Worst Case [Big-O]: O(N^2)
Average [Big-theta]: O(N^2)

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

Merge Sort

Merge Sort is a classic, I feel it’s easier to visualize the algorithm first and then write the code. This article at GeeksforGeeks explains MergeSort very well.

Complexity

Space Complexity: O(N)

Time Complexity:
Worst Case [Big-O]: O(N log N)
Best Case [Big-omega]: O(N log N)
Average [Big-theta]: O(N* log N)

#include <iostream>
using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temp arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temp arrays back into arr[l..r]

    // Initial index of first subarray
    int i = 0;

    // Initial index of second subarray
    int j = 0;

    // Initial index of merged subarray
    int k = l;

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int m = (l + r - 1) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

void printArray(int A[], int size)
{
    for (int i = 0; i < size; i++)
        cout << A[i] << " ";
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, arr_size - 1);
    cout << "Sorted array :\n";
    printArray(arr, arr_size);
    return 0;
}
// This code is contributed by Mayank Tyagi
//Code from GeeksforGeeks

Quick Sort

The name says it all, one of the fastest sorting algorithm.

Complexity

Space Complexity: O(N*log N)

Time Complexity:
Worst Case [Big-O]: O(N^2)
Best Case [Big-omega]: O(Nlog N)
Average [Big-theta]: O(Nlog N)

#include <iostream>
using namespace std;

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int A[], int l, int h)
{
    int pivot = A[l];
    int i = l, j = h;

    do
    {
        do
        {
            i++;
        } while (A[i] <= pivot);
        do
        {
            j--;
        } while (A[j] > pivot);

        if (i < j)
            swap(&A[i], &A[j]);
    } while (i < j);

    swap(&A[l], &A[j]);
    return j;
}

void QuickSort(int A[], int l, int h)
{
    int j;

    if (l < h)
    {
        j = partition(A, l, h);
        QuickSort(A, l, j);
        QuickSort(A, j + 1, h);
    }
}

int main()
{
    int A[] = {11, 13, 7, 12, 16, 9, 24, 5, 10, 3};
    int n = sizeof(A) / sizeof(A[0]);
    QuickSort(A,0,n);
    for (int i = 0; i < 10; i++)
        cout<<A[i]<<" ";
    return 0;
}

Selection Sort

Complexity
Space Complexity: O(1)

Time Complexity:
Worst Case [Big-O]: O(N^2)
Best Case [Big-omega]: O(N^2)
Average [Big-theta]: O(N^2)

#include <iostream>
using namespace std;

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void selectionSort(int arr[], int n)
{
    int i, j, min;
    for (i = 0; i < n - 1; i++)
    {
        min = i;
        for (j = i; j < n; j++)
            if (arr[j] < arr[min])
                min = j;
        swap(&arr[min], &arr[i]);
    }
}

void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Conclusion on Sorting Algorithms

I feel understanding and visualizing the algorithm is the key to write better code and which sorting algorithm is to be used entirely depends on the project use case and the type of data. I’ve also come across many unique sorting algorithms which I’ve never heard of before each specialized for a particular case.

2 thoughts on “Sorting Algorithms in C++”

  1. Usually I never comment on blogs but your article is so convincing that I never stop myself to say something about it. You’re doing a great job Man, Keep it up. Love you

Leave a Reply

Your email address will not be published. Required fields are marked *