Selection Sorts

Straight Sort-

Comparison based Algorithm that swaps minimum element in place to achieve a
T(C) = O(n^2) _ and a _S(C) = O(1) as the swapping occurs in place.

Steps-

1. Start with the first element as the minimum.
2. Compare this element to the rest of the elements to find the smallest.
3. Swap the smallest element with the first element.
4. Move to the next element and repeat until the list is sorted.

Code-

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Special Points-

1. Simplicity
2. Unstable
3. Inplace Sorting
4. Might be beneficial for small number of cases

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It's efficient and consistent.

Steps

1. Build a Heap
2. Sorting 1.Build a max heap from the input data. 2.The largest element is swapped with the last element of the heap and removed from the heap.
   1. Heapify the root of the heap.
   2. Repeat the process until all elements are sorted.

Code-

#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
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements from heap one by one
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

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

    heapSort(arr, n);

    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Special Points:

1. Binary Heap is used
2. Non Stable Algorithm
3. T(C) - O(nlogn)
4. Sort in Place S(C) - O(1) {Constant}