A Comprehensive Guide to Various Sorting Algorithms in C++

Introduction

Sorting algorithms are fundamental tools in computer science and programming. They allow us to efficiently organize data in a specific order, enabling faster search and retrieval. In this blog post, we will explore a variety of sorting algorithms, including greedy and dynamic approaches, implemented in C++. Each algorithm will be accompanied by a well-commented code snippet and a detailed explanation. Let's dive into the world of sorting!

Bubble Sort:

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order until the entire array is sorted. The name "Bubble Sort" comes from the way smaller (or larger) elements "bubble" to their correct positions in each iteration. Let's break down the steps involved in Bubble Sort:

1. Compare adjacent elements:
   The first step of Bubble Sort is to compare adjacent elements in the array. Starting from the beginning, compare the first element with the second element, then the second element with the third element, and so on. If the adjacent elements are in the wrong order (based on the desired sorting order), swap them.

2. Repeat the process:
   After the first pass, the largest (or smallest) element is guaranteed to be at the end of the array. In each subsequent pass, the comparison and swapping process is repeated for the remaining unsorted elements. The number of passes required is equal to the number of elements in the array minus one.

3. Optimization: Early termination
   To optimize Bubble Sort, we can introduce a flag variable to track whether any swaps were made during a pass. If no swaps were made in a pass, it means the array is already sorted, and the algorithm can terminate early.

4. Repeat until fully sorted:
   The process of comparing and swapping adjacent elements is repeated until the array is fully sorted. Each pass moves the next largest (or smallest) element to its correct position, gradually building the sorted portion of the array.

The time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. In the worst case, when the array is in reverse order, Bubble Sort requires the maximum number of comparisons and swaps. However, if the array is already sorted, Bubble Sort has a best-case time complexity of O(n) due to the early termination optimization.

Bubble Sort is not suitable for large data sets due to its quadratic time complexity. It is primarily used for educational purposes or when simplicity is preferred over performance.

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, size);

    cout << "Sorted array using Bubble Sort:\n ";
    for (int i = 0; i < size; ++i)
        cout << arr[i] << "\t";

    return 0;
}

Selection Sort:

Selection Sort is a simple in-place comparison-based sorting algorithm. It works by dividing the input array into two parts: the sorted portion and the unsorted portion. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted part and swaps it with the leftmost element of the unsorted part. This process continues until the entire array is sorted. Let's break down the steps involved in Selection Sort:

1. Find the minimum (or maximum) element:
   The first step of Selection Sort is to find the minimum (or maximum) element from the unsorted part of the array. This is done by iterating through the unsorted portion and keeping track of the index of the smallest (or largest) element found.

2. Swap with the leftmost element of the unsorted part:
   Once the minimum (or maximum) element is identified, it is swapped with the leftmost element of the unsorted part. This brings the smallest (or largest) element to its correct position in the sorted portion of the array.

3. Expand the sorted portion:
   After the swap, the sorted portion is expanded by considering the next element of the unsorted part. The previously swapped element now becomes a part of the sorted portion, and the process is repeated until the entire array is sorted.

To better understand Selection Sort, let's walk through an example using the following array: [64, 34, 25, 12, 22, 11, 90].

1. Initial array: [64, 34, 25, 12, 22, 11, 90]

2. Find the minimum element:
   The minimum element in the entire array is 11, found at index 5.

3. Swap with the leftmost element of the unsorted part:
   Swap the minimum element (11) with the leftmost element of the unsorted part (64).
   Array after the first swap: [11, 34, 25, 12, 22, 64, 90]

4. Expand the sorted portion:
   The sorted portion now includes the leftmost element (11), and the unsorted portion becomes [34, 25, 12, 22, 64, 90].

5. Find the minimum element:
   The minimum element in the unsorted part is 12, found at index 3.

6. Swap with the leftmost element of the unsorted part:
   Swap the minimum element (12) with the leftmost element of the unsorted part (34).
   Array after the second swap: [11, 12, 25, 34, 22, 64, 90]

7. Expand the sorted portion:
   The sorted portion now includes the first two elements (11, 12), and the unsorted portion becomes [25, 34, 22, 64, 90].

8. Repeat the steps:
   Continue the process of finding the minimum element, swapping, and expanding the sorted portion until the entire array is sorted.

9. Sorted array:
   The final sorted array using Selection Sort is [11, 12, 22, 25, 34, 64, 90].

The time complexity of Selection Sort is O(n^2), where n is the number of elements in the array. Selection Sort performs the same number of comparisons and swaps regardless of the order of the elements in the input array. However, it is not suitable for large data sets due to its quadratic time complexity. Selection Sort is an in-place sorting algorithm, meaning it does not require additional memory for sorting.

Selection Sort is primarily used for educational purposes or when simplicity is preferred over performance. It is not as efficient as more advanced sorting algorithms like Merge Sort or Quick Sort but can still be useful

#include <iostream>
using namespace std;

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, size);

    cout << "Sorted array using Selection Sort: \n";
    for (int i = 0; i < size; ++i)
        cout << arr[i] << "\t";

    return 0;
}

Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that works by dividing the input array into two parts: the sorted portion and the unsorted portion. The algorithm iterates through the unsorted portion, selects an element, and inserts it into its correct position within the sorted portion. This process continues until the entire array is sorted. Let's break down the steps involved in Insertion Sort:

1. Initial setup:
   The first element of the array is considered as the sorted portion. The remaining elements are considered as the unsorted portion.

2. Select an element from the unsorted portion:
   Starting from the second element, the algorithm selects one element at a time from the unsorted portion and moves it to its correct position within the sorted portion.

3. Compare and shift:
   The selected element is compared with the elements in the sorted portion, moving larger elements one position to the right until the correct position for the selected element is found.

4. Insert the element into its correct position:
   Once the correct position for the selected element is determined, it is inserted into the sorted portion at that position.

5. Repeat until fully sorted:
   Steps 2 to 4 are repeated for each remaining element in the unsorted portion until the entire array is sorted.

The time complexity of Insertion Sort is O(n^2), where n is the number of elements in the array. In the worst case, when the array is in reverse order, each element needs to be compared and shifted to its correct position. However, if the array is already sorted, Insertion Sort has a best-case time complexity of O(n) due to the early termination optimization.

Insertion Sort is efficient for small data sets or partially sorted arrays. It is also an in-place sorting algorithm, meaning it does not require additional memory for sorting.

#include <iostream>
using namespace std;

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; ++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;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    cout << "Sorted array using Insertion Sort:\n";
    for (int i = 0; i < size; ++i)
        cout << arr[i] << "\t";

    return 0;
}

Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that works by dividing the input array into smaller halves, recursively sorting them, and then merging the sorted halves to produce the final sorted array. Let's break down the steps involved in Merge Sort:

1. Divide:
   The first step of Merge Sort is to divide the input array into two halves. This is done recursively until each subarray contains only one element or is empty. The division is performed by finding the middle index of the array and splitting it into two parts.

2. Conquer (Recursive Sort):
   After dividing the array, the next step is to sort the divided subarrays. This is done by recursively calling the Merge Sort function on each half. This recursive process continues until the base case is reached, i.e., when a subarray contains only one element. At this point, the subarray is considered sorted.

3. Merge:
   The final step of Merge Sort is the merge operation. It merges the sorted subarrays to produce the final sorted array. The merging process compares elements from the two subarrays and places them in the correct order in a temporary array. The merged elements are then copied back to the original array, resulting in a sorted sequence.

To better understand Merge Sort, let's walk through an example using the following array: [64, 34, 25, 12, 22, 11, 90].

1. Divide:
   The initial array is divided into two halves: [64, 34, 25, 12] and [22, 11, 90].
   The process continues recursively until the subarrays contain only one element.

2. Conquer (Recursive Sort):
   The recursive sorting process is applied to each subarray.
   Subarray 1: [64, 34, 25, 12]

3. Divided into [64, 34] and [25, 12]

4. Further divided into [64] [34] [25] [12]

5. The base case is reached, and the subarrays are considered sorted.

Subarray 2: [22, 11, 90]

• Divided into [22] [11] [90]
• The base case is reached, and the subarrays are considered sorted.

1. Merge: The sorted subarrays are merged back into a single sorted array.
2. [64] [34] are merged into [34, 64]
3. [25] [12] are merged into [12, 25]
4. [34, 64] and [12, 25] are merged into [12, 25, 34, 64]

• [22] [11] are merged into [11, 22]
• [11, 22] and [90] are merged into [11, 22, 90]

Finally, the two merged subarrays, [12, 25, 34, 64] and [11, 22, 90], are merged into the final sorted array: [11, 12, 22, 25, 34, 64, 90].

The time complexity of Merge Sort is O(n log n), where n is the number of elements in the array. It performs equally well for best, average, and worst-case scenarios. Merge Sort is a stable sorting algorithm, meaning it maintains the relative order of elements with equal values.

Merge Sort's key advantage is its efficiency in handling large data sets since it divides the problem into smaller subproblems. However, it requires additional memory for the temporary array used during the merging process.

Merge Sort is a widely-used sorting algorithm due to its consistent performance and stability. Its divide-and-conquer approach makes it an excellent choice for sorting large datasets efficiently.

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int leftArr[n1], rightArr[n2];

    for (int i = 0; i < n1; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

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

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array using Merge Sort:\n";
    for (int i = 0; i < size; ++i)
        cout << arr[i] << "\t";

    return 0;
}

Heap Sort:

Heap Sort is a comparison-based sorting algorithm that leverages the properties of a binary heap data structure. It works by first constructing a max-heap (in the case of sorting in ascending order) or a min-heap (in the case of sorting in descending order) from the input array. Once the heap is built, the largest (or smallest) element is repeatedly removed from the root of the heap and placed at the end of the array. This process is repeated until the entire array is sorted. Here's a step-by-step explanation of Heap Sort:

1. Build the heap:

   • The first step of Heap Sort is to construct a heap from the input array.
   • To build the heap, start from the last non-leaf node of the array (index n/2-1) and perform heapify operations on each node in reverse order.
   • The heapify operation ensures that each node satisfies the heap property, which means that the parent node is greater (for max-heap) or smaller (for min-heap) than its children.
   • By applying heapify to each node, we ensure that the entire array satisfies the heap property and can be treated as a valid heap.

2. Extract elements from the heap:

   • After the heap is constructed, the largest (or smallest) element is at the root of the heap.
   • Swap the root element with the last element of the heap (considering the remaining heap size).
   • Reduce the heap size by one to exclude the sorted element from future heapify operations.
   • Perform heapify on the root to restore the heap property.

3. Repeat until the array is sorted:

   • Repeat the extraction step until all elements are extracted from the heap.
   • After each extraction, the next largest (or smallest) element is moved to the end of the array.
   • The extracted elements are placed in the reverse order of their sorted position, resulting in a sorted array.

The time complexity of Heap Sort is O(n log n) in all cases, where n is the number of elements in the array. Building the heap takes O(n) time, and the extraction step is performed n times with a time complexity of O(log n) per extraction. The space complexity of Heap Sort is O(1) since the sorting is done in-place without requiring additional memory.

Heap Sort is an efficient and widely used sorting algorithm. It guarantees a worst-case time complexity of O(n log n), making it suitable for large data sets. Additionally, Heap Sort is an in-place sorting algorithm and can be implemented in a way that preserves the stability of equal elements in the array.

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i;       
    int left = 2 * i + 1;   
    int right = 2 * i + 2;  

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);

        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n)
{
    // Build max-heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);

        heapify(arr, i, 0);
    }
}


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

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

    cout << "Original array: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Quick Sort:

Lets walk through Quick Sort with an example. Consider the following array of integers: [7, 2, 1, 6, 8, 5, 3, 4].

Step 1: Choosing a Pivot:

• In this example, we'll choose the last element, which is 4, as the pivot.

Step 2: Partitioning:

• We initialize i to the start of the array (i = 0) and j to one position ahead of the start (j = 1).
• We compare each element from the start to the second-to-last element with the pivot (4).
• If the element is less than or equal to the pivot, we swap it with the element at index i and increment i.
• After iterating through the array, we swap the pivot (4) with the element at index i.
• The array after partitioning becomes: [2, 1, 3, 4, 8, 5, 7, 6].
• The pivot (4) is now in its correct sorted position.

Step 3: Recursive Sorting:

• The array is divided into two sub-arrays: 2, 1, 3 and 8, 5, 7, 6.
• We recursively apply the partitioning process to each sub-array.
• For the left sub-array, we choose 3 as the pivot. After partitioning, it becomes [2, 1, 3], and the pivot (3) is in its correct sorted position.
• For the right sub-array, we choose 6 as the pivot. After partitioning, it becomes [5, 6, 7, 8], and the pivot (6) is in its correct sorted position.
• Now, both sub-arrays are sorted.

Step 4: Final Sorted Array:

• Since both sub-arrays are sorted, the entire array is sorted. Concatenating the sorted sub-arrays gives us the final sorted array: [1, 2, 3, 4, 5, 6, 7, 8].

The steps of partitioning and recursive sorting are repeated until the array is completely sorted. Quick Sort has an average-case time complexity of O(n log n) and a worst-case time complexity of O(n^2), but the worst-case scenario is rare and can be mitigated by choosing a good pivot. It is an in-place sorting algorithm and does not require additional memory. Quick Sort is widely used due to its efficiency and simplicity.

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[high]; 
    int i = (low - 1);   

    for (int j = low; j <= high - 1; j++) {

        if (arr[j] <= pivot) {
            i++; 
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);                
}

void quickSort(int arr[], int low, int high)
{
    if (low < high) {
        int pivotIndex = partition(arr, low, high); 
        quickSort(arr, low, pivotIndex - 1);        
        quickSort(arr, pivotIndex + 1, high);       
    }
}

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 size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

Conclusion

In this blog post, I have explained various sorting algorithms implemented in C++, including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, heap Sort and Quick Sort. Each algorithm was accompanied by detailed explanations and well-commented code snippets. Sorting algorithms are powerful tools for organizing data efficiently, and understanding their workings can greatly enhance your programming skills. Feel free to experiment with the provided code snippets and explore more sorting algorithms to expand your knowledge further. Happy sorting!