Sorting Algorithms

Sorting Algorithms in C++

Sorting is the process of arranging elements in a specific order, typically in ascending or descending order. Sorting is a fundamental operation in computer science and is used in a variety of applications, such as organizing data for efficient searching, analysis, and visualization.

There are several sorting algorithms, each with its own approach and performance characteristics. In this explanation, we'll cover the most commonly used sorting algorithms in C++.

Types of Sorting Algorithms

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort

1. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until the list is sorted.

Algorithm Overview:

• Compare each pair of adjacent elements.
• If they are in the wrong order, swap them.
• Repeat the process until no more swaps are needed.

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (if the list is already sorted)
• Average Case: O(n²)

Code Example:

#include <iostream>
using namespace std;

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]
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; 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 << "Original Array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

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

    return 0;
}

Output:

Original Array: 64 34 25 12 22 11 90 
Sorted Array: 11 12 22 25 34 64 90

2. Selection Sort

Selection Sort works by repeatedly finding the smallest (or largest) element from the unsorted portion of the list and placing it at the beginning (or end) of the sorted portion.

Algorithm Overview:

• Divide the list into a sorted and unsorted portion.
• In each iteration, select the smallest element from the unsorted portion and swap it with the first element of the unsorted portion.
• Repeat the process until the list is sorted.

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n²)
• Average Case: O(n²)

Code Example:

#include <iostream>
using namespace std;

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

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

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

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

    selectionSort(arr, n);

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

    return 0;
}

Output:

Original Array: 64 25 12 22 11 
Sorted Array: 11 12 22 25 64

3. Insertion Sort

Insertion Sort builds the final sorted array one element at a time by picking elements from the unsorted portion and placing them in their correct position within the sorted portion.

Algorithm Overview:

• Start with the second element. Compare it with the first element and insert it into the sorted portion.
• Move through the list, inserting each new element into its correct position in the sorted portion.

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (if the list is already sorted)
• Average Case: O(n²)

Code Example:

#include <iostream>
using namespace std;

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;
    }
}

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

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

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

    insertionSort(arr, n);

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

    return 0;
}

Output:

Original Array: 12 11 13 5 6 
Sorted Array: 5 6 11 12 13

4. Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the two sorted halves.

Algorithm Overview:

• Divide the array into two halves.
• Recursively sort both halves.
• Merge the sorted halves to produce the sorted array.

Time Complexity:

• Worst Case: O(n log n)
• Best Case: O(n log n)
• Average Case: O(n log n)

Code Example:

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    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];

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

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

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

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

Output:

Original Array: 38 27 43 3 9 82 10 
Sorted Array: 3 9 10 27 38 43 82

5. Quick Sort

Quick Sort is another divide-and-conquer algorithm. It selects a "pivot" element from the array and partitions the other elements into two sub-arrays, according to whether they are smaller or greater than the pivot.

Algorithm Overview:

• Choose a pivot element.
• Partition the array into two subarrays: elements less than the pivot and elements greater than the pivot.
• Recursively sort the subarrays.

**Time Complexity