Sorting arrays in C++: A comparison

#include <iostream>
using namespace std;
// Function to perform bubble sort
void 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 array
void 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;
}

Code explanation

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 $O(n^2)$ .

Selection sort

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.

Code implementation

#include <iostream>
using namespace std;
// Function to perform selection sort
void 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 element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}
// Function to print an array
void 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;
}

Code explanation

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 $O(n^2)$ .

Insertion sort

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.

Code implementation

#include <iostream>
using namespace std;
// Function to perform insertion sort
void 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 position
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}
// Function to print an array
void 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;
}

Code explanation

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

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

Code implementation

#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 arrays
    int 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 subarray
    int i = 0;
    // Initial index of the second subarray
    int j = 0;
    // Initial index of the 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++;
    }
}
// Function to implement merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}
// Utility function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
// Main function to test the mergeSort function
int 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;
}

Code explanation

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 $O(n \: log \: n)$ , where $n$ is the number of elements in the array.

Quick sort

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

Code implementation

#include <iostream>
using namespace std;
// Function to partition the array using the last element as pivot
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // pivot
    int i = (low - 1);  // Index of smaller element
    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++;    // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}
// Function to implement quick sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);
        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// Utility function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
// Main function to test the quickSort function
int 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;
}

Code explanation

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 $O(n^2)$ can occur if the pivot selection is poor, leading to unbalanced partitioning. However, with proper pivot selection strategies, this can be mitigated.

Conclusion

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.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Sorting arrays in C++: A comparison

Bubble sort

Code implementation

Code explanation

Selection sort

Code implementation

Code explanation

Insertion sort

Code implementation

Code explanation

Merge sort

Code implementation

Code explanation

Quick sort

Code implementation

Code explanation

Conclusion