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 GeeksforGeeksQuick 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.