Comparing Performance of Popular Sorting Algorithms

In this post, we will compare three conventional sorting algorithms: Bubble Sort, Insertion Sort, and Selection Sort. We will discuss their time and space complexity, analyze their performance using C++, and examine their use cases.

What are Sorting Algorithms?

Sorting algorithms are methods used to rearrange elements in a list or array into a particular order, typically either ascending or descending. The goal of a sorting algorithm is to organize the data such that it becomes easier to search, process, or display the information.

Common Types of Sorting Algorithms

• Comparison-based Sorting Algorithms: These algorithms compare elements to determine their order. Examples include Bubble Sort, Selection Sort, Merge Sort, Quick Sort etc.
• Non-comparison Sorting Algorithms: These algorithms sort elements without directly comparing them, like Radix Sort and Counting Sort (beyond the scope of this post).

We’ll only be discussing three common comparison-based sorting algorithms namely, Bubble Sort, Insertion Sort, and Selection Sort in this post.

These algorithms have already been discussed in detail in a previous post – Common Sorting Algorithms

Traditional Sorting Algorithms

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, which works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues until the entire list is sorted.

For an array [5, 3, 8, 1], the algorithm will repeatedly swap elements until the array is sorted: [1, 3, 5, 8].

Insertion Sort

Insertion Sort works by building a sorted list one element at a time. It picks an element from the unsorted part of the list and places it at the correct position in the sorted part.

For an array [5, 3, 8, 1], after the first iteration, the array becomes [3, 5, 8, 1]. After the second iteration, it becomes [3, 5, 8, 1], and so on until the list is sorted: [1, 3, 5, 8].

Selection Sort

Selection Sort works by selecting the smallest (or largest) element from the unsorted part of the list and swapping it with the first unsorted element. This process is repeated until the entire list is sorted.

For an array [5, 3, 8, 1], the algorithm first finds the smallest element 1 and swaps it with the first element: [1, 3, 8, 5]. It then finds the next smallest element and swaps again until the list is sorted: [1, 3, 5, 8].

Time and Space Complexity

Let’s analyze the time and space complexity of the three sorting algorithms discussed above.

Time Complexity

• Best Case: The number of comparisons made when the input is already sorted.
• Worst Case: The number of comparisons made when the input is in the worst possible order.
• Average Case: The number of comparisons for a typical (random) input.

Space Complexity

All three algorithms have a space complexity of O(1) since they sort the array in place without requiring additional memory proportional to the input size.

Comparing Execution Time

To understand how these sorting algorithms perform, let’s implement them in C++ and compare their execution time for various types of input arrays: sorted in ascending order, reverse sorted, and randomly shuffled arrays.

Code Implementation

//
//  main.cpp
//  Sorting Algorithms Performance
//
//  Created by Himanshu on 08/10/24.
//
 
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <iomanip>  // for std::fixed and std::setprecision
using namespace std;
using namespace chrono;
 
void bubbleSort(vector<int>& arr) {
    int n = (int) arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j+1] < arr[j]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}
 
void insertionSort(vector<int>& arr) {
    int n = (int) arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
void selectionSort(vector<int>& arr) {
    int n = (int) arr.size();
    for (int i = 0; i < n; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
         
        if (minIdx != i) {
            swap(arr[minIdx], arr[i]);
        }
    }
}
 
void measureSortingTime(void (*sortFunc)(vector<int>&), vector<int> arr, const string& sortName) {
    vector<int> tempArr = arr;  // Create a copy of input vector
    auto start = high_resolution_clock::now();
    sortFunc(tempArr);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
     
    cout << fixed << setprecision(2);  // Set fixed format and precision to 2 decimal places
    cout << sortName << " took " << (duration.count()/1000.0) << "ms" << endl;
}
 
void generateTestArrays(vector<int>& ascending, vector<int>& descending, vector<int>& randomArr, int n) {
    ascending.clear();
    descending.clear();
    randomArr.clear();
     
    for (int i = 1; i <= n; i++) {
        ascending.push_back(i);
        descending.push_back(n - i + 1);
        randomArr.push_back(i);
    }
    
    default_random_engine rng(42); // 42 as the seed for reproducibility
    shuffle(randomArr.begin(), randomArr.end(), rng);
}
 
int main() {
    int n = 10000; // Larger size array for testing
    vector<int> ascending, descending, randomArr;
    generateTestArrays(ascending, descending, randomArr, n);
 
    cout << "Running tests on array size: " << n << endl;
 
    cout << "\nBubble Sort on different input types:" << endl;
    measureSortingTime(bubbleSort, ascending, "Bubble Sort (Ascending)");
    measureSortingTime(bubbleSort, descending, "Bubble Sort (Descending)");
    measureSortingTime(bubbleSort, randomArr, "Bubble Sort (Random)");
 
    cout << "\nInsertion Sort on different input types:" << endl;
    measureSortingTime(insertionSort, ascending, "Insertion Sort (Ascending)");
    measureSortingTime(insertionSort, descending, "Insertion Sort (Descending)");
    measureSortingTime(insertionSort, randomArr, "Insertion Sort (Random)");
 
    cout << "\nSelection Sort on different input types:" << endl;
    measureSortingTime(selectionSort, ascending, "Selection Sort (Ascending)");
    measureSortingTime(selectionSort, descending, "Selection Sort (Descending)");
    measureSortingTime(selectionSort, randomArr, "Selection Sort (Random)");
 
    return 0;
}

Output

Running tests on array size: 10000

Bubble Sort on different input types:
Bubble Sort (Ascending) took 251.09ms
Bubble Sort (Descending) took 593.87ms
Bubble Sort (Random) took 555.53ms

Insertion Sort on different input types:
Insertion Sort (Ascending) took 0.10ms
Insertion Sort (Descending) took 370.01ms
Insertion Sort (Random) took 180.27ms

Selection Sort on different input types:
Selection Sort (Ascending) took 222.31ms
Selection Sort (Descending) took 242.12ms
Selection Sort (Random) took 238.52ms

Explanation of the Code

• The program tests each sorting algorithm on three types of input arrays: ascending, descending, and random.
• It generates test arrays and measures the time taken by each sorting algorithm using chrono.
• Each algorithm is tested on a large array of size 10,000.

Performance Metrics

Bubble Sort

• Best Case: For already sorted arrays, Bubble Sort performs well and terminates early (thanks to its optimization). However, it’s still inefficient compared to other algorithms like Insertion Sort.
• Worst Case: For reverse sorted or randomly shuffled arrays, Bubble Sort performs poorly, taking O(n²) time.
• Use Case: Bubble Sort is mainly used for educational purposes or small datasets due to its inefficiency.

Note: In optimized Bubble Sort implementation, we exit early if no swap is required.

Insertion Sort

• Best Case: Insertion Sort is very efficient when the input array is already sorted or nearly sorted. It can handle small data sets effectively with a time complexity of O(n).
• Worst Case: For reverse sorted arrays, Insertion Sort performs poorly with O(n²) complexity.
• Use Case: Insertion Sort is commonly used in situations where the input data is already mostly sorted. It is also used in hybrid sorting algorithms like Timsort.

Selection Sort

• Best Case and Worst Case: Selection Sort has the same time complexity regardless of the input. It always takes O(n²) time because it doesn’t benefit from any existing order in the input data.
• Use Case: Selection Sort is mainly used when minimizing the number of swaps is important, such as when working with large records that are costly to move.

In this post, we compared the performance of Bubble Sort, Insertion Sort, and Selection Sort by analyzing their time and space complexities and testing them on different types of input arrays.

Key takeaways:

• Bubble Sort is simple but inefficient for most real-world tasks.
• Insertion Sort is efficient for small, nearly sorted arrays, making it useful in practice.
• Selection Sort has limited use due to its consistent O(n²) complexity. But since it minimizes the number of swaps to at most n - 1, it finds usage in scenarios where write operation is costly.

To conclude, for larger datasets or situations where efficiency is critical, these algorithms though simple are outperformed by more advanced ones like Merge Sort, Quick Sort, or Timsort. However, they are a good starting point to start learning sorting algorithms.