Sorting algorithms differ in efficiency, performance, and suitability for various data types and cases, and they can sort data in ascending or descending order.

In this answer, we’ll compare some of the best and worst sorting algorithms based on their efficiency and performance. Let’s take a few examples from stable and unstable algorithms:

Bubble sort is easy to implement but not efficient for large datasets. It repeatedly swaps adjacent elements if they are in the wrong order until the array is sorted.

#include <iostream>using namespace std;// Function to perform bubble sortvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap arr[j] and arr[j+1]int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}// Function to print an arrayvoid printArray(int arr[], int size) {for (int i = 0; i < size; i++) {cout << arr[i] << " ";}cout << endl;}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);cout << "Unsorted array: ";printArray(arr, n);bubbleSort(arr, n);cout << "Sorted array: ";printArray(arr, n);return 0;}

**Lines 5–16:**We start with the nested loops. The outer loop iterates through the array from the beginning to the second-to-last element. The inner loop iterates through the array from the beginning to the element just before the sorted portion of the array.**Lines 8–13:**Inside the inner loop, we compare adjacent elements. If the current element is greater than the next element, we swap them. This process continues until the array is sorted.

**Best case:** It performs best when the dataset is already nearly sorted because it requires fewer swaps.

**Worst case:** It’s not suitable for large datasets or when efficiency is crucial because its time complexity is

Selection sort is also simple but slightly more efficient than bubble sort. It repeatedly selects the minimum element from the unsorted portion of the array and swaps it with the first unsorted element.

#include <iostream>using namespace std;// Function to perform selection sortvoid selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int minIndex = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// Swap the found minimum element with the first elementint temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}// Function to print an arrayvoid printArray(int arr[], int size) {for (int 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]);cout << "Unsorted array: ";printArray(arr, n);selectionSort(arr, n);cout << "Sorted array: ";printArray(arr, n);return 0;}

**Lines 5–18:**We start with the nested loops. Inside the outer loop, we initialize a`minIndex`

variable to keep track of the index of the smallest element. Inside the inner loop, we iterate through the array from the element after the current element (`i+1`

) to the end of the array.**Lines 8–12:**Inside the inner loop, we compare each element with the current minimum element (`arr[minIndex]`

). If we find a smaller element, we update`minIndex`

to point to that element.**Lines 14–16:**After finding the smallest element in the unsorted portion of the array, we swap it with the element at index`i`

, effectively placing the smallest element in its correct sorted position. This process continues until the entire array is sorted.

**Best case:** It performs best when memory space is limited because it only requires a constant amount of additional memory.

**Worst case:** It is not efficient for large datasets due to its time complexity of

Insertion sort builds the final sorted array one element at a time by repeatedly taking the next element from the unsorted part and inserting it into its correct position in the sorted part.

#include <iostream>using namespace std;// Function to perform insertion sortvoid insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// Move elements of arr[0..i-1], that are greater than key,// to one position ahead of their current positionwhile (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}}// Function to print an arrayvoid printArray(int arr[], int size) {for (int i = 0; i < size; i++) {cout << arr[i] << " ";}cout << endl;}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);cout << "Unsorted array: ";printArray(arr, n);insertionSort(arr, n);cout << "Sorted array: ";printArray(arr, n);return 0;}

**Lines 5–17:**We start with an outer loop that iterates through the array from the second element (`i = 1`

) to the last element.**Lines 6–8:**Inside the outer loop, we store the current element in a variable`key`

. We also initialize a variable`j`

to`i - 1`

, which points to the element just before the current element.**Lines 11–14:**We then enter a while loop that iterates backward from the current element (`i`

) to the beginning of the array (`j >= 0`

) as long as the current element is smaller than the key.**Lines 12–13:**Inside the while loop, we shift elements to the right to make space for the key in its correct sorted position.

**Line 15:**After finding the correct position for the key, we insert it into the sorted portion of the array. This process continues until the entire array is sorted.

**Best case:** It performs best when the dataset is nearly sorted or when the array size is small.

**Worst case: **Its time complexity makes it inefficient for large datasets compared to more advanced algorithms like merge sort or quick sort.

Merge sort divides the array into two halves, sorts each half separately, and then merges them back together in sorted order.

#include <iostream>using namespace std;// Function to merge two subarrays of arr[]void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;// Create temporary arraysint L[n1], R[n2];// Copy data to temporary 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 temporary arrays back into arr[l..r]// Initial index of the first subarrayint i = 0;// Initial index of the second subarrayint j = 0;// Initial index of the merged subarrayint 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 anywhile (i < n1) {arr[k] = L[i];i++;k++;}// Copy the remaining elements of R[], if there are anywhile (j < n2) {arr[k] = R[j];j++;k++;}}// Function to implement merge sortvoid mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;// Sort first and second halvesmergeSort(arr, l, m);mergeSort(arr, m + 1, r);// Merge the sorted halvesmerge(arr, l, m, r);}}// Utility function to print an arrayvoid printArray(int arr[], int size) {for (int i = 0; i < size; i++)cout << arr[i] << " ";cout << endl;}// Main function to test the mergeSort functionint main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);cout << "Given array is \n";printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);cout << "\nSorted array is \n";printArray(arr, arr_size);return 0;}

**Line 53–64:**The`mergeSort`

function recursively divides the array into smaller subarrays until each subarray contains only one element.**Lines 54–55:**Inside the`mergeSort`

function, the base case for recursion is when the left index (`l`

) is less than the right index (`r`

) and we calculate the middle index (`m`

) of the array.**Lines 58–59:**We then recursively call`mergeSort`

on the left half of the array (`arr[l...m]`

) and the right half of the array (`arr[m+1...r]`

).**Line 62:**After dividing the array into smaller subarrays, we call the`merge`

function to merge and sort the subarrays. The`merge`

function merges two sorted subarrays into a single sorted array. This process continues recursively until the entire array is sorted.

**Best case:** It performs consistently well regardless of the initial order of elements. It’s suitable for large datasets where stable performance is required.

**Worst case:** It requires additional memory space proportional to the size of the array, which can be a limitation for large datasets. The time complexity of the merge sort algorithm is

Quick sort picks an element as a pivot and partitions the array around the pivot. It then recursively sorts the subarrays.

#include <iostream>using namespace std;// Function to partition the array using the last element as pivotint partition(int arr[], int low, int high) {int pivot = arr[high]; // pivotint i = (low - 1); // Index of smaller elementfor (int j = low; j <= high - 1; j++) {// If current element is smaller than or equal to pivotif (arr[j] <= pivot) {i++; // increment index of smaller elementswap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return (i + 1);}// Function to implement quick sortvoid quickSort(int arr[], int low, int high) {if (low < high) {// pi is partitioning index, arr[pi] is now at right placeint pi = partition(arr, low, high);// Separately sort elements before partition and after partitionquickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}// Utility function to print an arrayvoid printArray(int arr[], int size) {for (int i = 0; i < size; i++)cout << arr[i] << " ";cout << endl;}// Main function to test the quickSort functionint main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);cout << "Given array is \n";printArray(arr, n);quickSort(arr, 0, n - 1);cout << "Sorted array is \n";printArray(arr, n);return 0;}

**Lines 21–30:**The`quickSort`

function recursively divides the array into smaller subarrays until each subarray contains only one element.**Lines 22–24:**Inside the`quickSort`

function, the base case for recursion is when the`low`

index is less than the`high`

index. We call the`partition`

function to partition the array and find the pivot element (`pi`

).**Lines 27–28:**We then recursively call`quickSort`

on the subarray to the left of the pivot (`arr[low...pi-1]`

) and the subarray to the right of the pivot (`arr[pi+1...high]`

). The`partition`

function rearranges the elements of the array around a pivot element such that all elements less than the pivot are on its left and all elements greater than the pivot are on its right. This process continues recursively until the entire array is sorted.

**Best case:** It is one of the fastest sorting algorithms available and performs well on average and large datasets. It’s suitable when efficiency is critical.

**Worst case:** Its worst-case time complexity of

Sorting algorithms each have their strengths and weaknesses in terms of efficiency, performance, and suitability for different data types and scenarios. In this answer, we explored and compared a few key sorting algorithms. From the simplicity of bubble and selection sort to the more advanced quick and merge sort, each algorithm has its best use cases depending on the size of the data. Understanding these differences helps in choosing the right algorithm for a given task.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS