Sort Algorithm

Sorting is the process of arranging elements in a specific order. There are many sorting algorithms available, each with its own advantages and disadvantages. In this section, we will discuss some of the common sorting algorithms in C++.

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Here is an example of implementing bubble sort in C++:

main.cpp

#include <iostream>

using namespace std;

void bubbleSort(int numbers[], int count) {
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            if (numbers[j] > numbers[j + 1]) {
                swap(numbers[j], numbers[j + 1]);
            }
        }
    }
}

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

    bubbleSort(numbers, count);

    cout << "Sorted array: ";
    for (int i = 0; i < count; i++) {
        cout << numbers[i] << " ";
    }

    return 0;
}

The output of the program will be:

Sorted array: 11 12 22 25 34 64 90

Here is a GIF that demonstrates how bubble sort works:

Quick Sort

Quick sort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array around the pivot such that elements smaller than the pivot are on the left and elements larger than the pivot are on the right. The process is repeated recursively on the left and right subarrays until the entire array is sorted.

Here is an example of implementing quick sort in C++:

main.cpp

#include <iostream>

using namespace std;

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

    for (int j = low; j < high; j++) {
        if (numbers[j] < pivot) {
            i++;
            swap(numbers[i], numbers[j]);
        }
    }

    swap(numbers[i + 1], numbers[high]);

    return i + 1;
}

void quickSort(int numbers[], int low, int high) {
    if (low < high) {
        int pi = partition(numbers, low, high);

        quickSort(numbers, low, pi - 1);
        quickSort(numbers, pi + 1, high);
    }
}

int main() {
    int numbers[] = {10, 7, 8, 9, 1, 5};
    int count = sizeof(numbers) / sizeof(numbers[0]);

    quickSort(numbers, 0, count - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < count; i++) {
        cout << numbers[i] << " ";
    }

    return 0;
}

The output of the program will be:

Sorted array: 1 5 7 8 9 10

Here is a GIF that demonstrates how quick sort works:

Merge Sort

Merge sort is a divide-and-conquer algorithm that works by dividing the array into two halves, sorting the two halves independently, and then merging the sorted halves. The process is repeated recursively until the entire array is sorted.

Here is an example of implementing merge sort in C++:

main.cpp

#include <iostream>

using namespace std;

void merge(int numbers[], int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int left[n1], right[n2];

    for (int i = 0; i < n1; i++) {
        left[i] = numbers[low + i];
    }

    for (int j = 0; j < n2; j++) {
        right[j] = numbers[mid + 1 + j];
    }

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

    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            numbers[k] = left[i];
            i++;
        } else {
            numbers[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        numbers[k] = left[i];
        i++;
        k++;
    }

    while (j < n2) {
        numbers[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int numbers[], int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;

        mergeSort(numbers, low, mid);
        mergeSort(numbers, mid + 1, high);

        merge(numbers, low, mid, high);
    }
}

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

    mergeSort(numbers, 0, count - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < count; i++) {
        cout << numbers[i] << " ";
    }

    return 0;
}

The output of the program will be:

Sorted array: 5 6 7 11 12 13

Here is a GIF that demonstrates how merge sort works: