Sorting algorithms with examples in C++

Sorting algorithms are procedures or sets of instructions used to arrange a set of elements in a specific order. These algorithms are widely used in computer science and programming because of their importance for efficiency and process optimization.

There are numerous sorting algorithms, each with its own characteristics and complexities. In the following, we will mention some of the main sorting algorithms and implement them in the C++ language:

info The original list for all sorting algorithms will be as follows: 54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42

Bubble Sort

Bubble sort compares pairs of adjacent elements and swaps them if they are in the wrong order. Repeat this process until all elements are sorted.

IMPLEMENTATION IN C++

#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]) {
                // Intercambiar los elementos
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printArray(arr, size);

    bubbleSort(arr, size);

    cout << "Lista ordenada: ";
    printArray(arr, size);

    return 0;
}

Insertion Sort

The Insertion Sort divides the set of elements into an ordered and an unordered part. It takes an element from the unsorted part and inserts it into the correct position in the sorted part. Repeat this process until all elements are sorted.

IMPLEMENTATION IN C++

#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 = j - 1;
        }

        arr[j + 1] = key;
    }
}

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

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printArray(arr, size);

    insertionSort(arr, size);

    cout << "Lista ordenada: ";
    printArray(arr, size);

    return 0;
}

Selection Sort

Selection Sort finds the smallest element in the set of elements and places it in the correct position. Then, it finds the next smallest element and places it in the next correct position. Repeat this process until all the elements are sorted.

IMPLEMENTATION IN C++

#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;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

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

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printArray(arr, size);

    selectionSort(arr, size);

    cout << "Lista ordenada: ";
    printArray(arr, size);

    return 0;
}

Merge Sort

Merge Sort divides the set of elements into smaller subsets, sorts them separately, and then merges them into a larger sorted set. This algorithm uses a divide and conquer strategy.

IMPLEMENTATION IN C++

#include <iostream>
using namespace std;

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

    int L[n1], R[n2];

    for (i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    k = left;

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

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

    while (j < n2) {
        arr[k] = R[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);
    }
}

void printList(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printList(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "Lista ordenada: ";
    printList(arr, size);

    return 0;
}

Quick Sort

Quick Sort chooses an element called the "pivot" and divides the set into two subsets, one with elements smaller than the pivot and one with elements larger than the pivot. It then applies the same process recursively to each of the subsets. This algorithm also uses the divide and conquer strategy.

IMPLEMENTATION IN C++

#include <iostream>
using namespace std;

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

    for (int j = low; j < high; ++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 pi = partition(arr, low, high);

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

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

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    cout << "Lista ordenada: ";
    printArray(arr, size);

    return 0;
}

Heap Sort

Heap Sort builds a heap from the elements and then successively extracts the maximum (or minimum) element from the heap, readjusting the heap after each extraction. The final result is a set of sorted elements.

IMPLEMENTATION IN C++

#include <iostream>
using namespace std;

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

    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }

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

void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; --i) {
        heapify(arr, size, i);
    }

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

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

int main() {
    int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista original: ";
    printArray(arr, size);

    heapSort(arr, size);

    cout << "Lista ordenada: ";
    printArray(arr, size);

    return 0;
}

These are just a few examples of the most common sorting algorithms. Each of them has different characteristics in terms of time complexity, stability, memory consumption and adaptability to different scenarios. The choice of the appropriate algorithm will depend on the context and the specific requirements of the problem to be solved.