Selection Sort

Core Concept

During each iteration, the element with the smallest (or largest) key is identified from the unsorted portion and appended to the sorted sub-sequence.

Implementation

void selectionSort(int data[], int size) {
    for (int current = 0; current < size - 1; ++current) {
        int smallestIdx = current;
        for (int checker = current + 1; checker < size; ++checker) {
            if (data[checker] < data[smallestIdx]) {
                smallestIdx = checker;
            }
        }
        if (smallestIdx != current) {
            int temp = data[current];
            data[current] = data[smallestIdx];
            data[smallestIdx] = temp;
        }
    }
}

Complexity and Stability

• Space Complexity: O(1)
• Time Complexity: O(n^2)
• Stability: Unstable
• Applicability: Compatible with both arrays and linked lists.

Heap Sort

Building a Max Heap

The process involves verifying all non-terminal nodes to ensure they satisfy the max heap property. If a node violates the property (where the parent must be greater than or equal to its children), it must be adjusted by swapping it with its larger child.

In a sequentially stored complete binary tree, non-terminal nodes have indices i ≤ n/2.

Max Heap Construction Code

void constructMaxHeap(int arr[], int total) {
    for (int pos = total / 2; pos > 0; --pos) {
        heapifyDown(arr, pos, total);
    }
}

void heapifyDown(int arr[], int root, int total) {
    int temp = arr[root];
    for (int child = 2 * root; child <= total; child *= 2) {
        if (child < total && arr[child] < arr[child + 1]) {
            ++child; // Right child is larger
        }
        if (temp >= arr[child]) {
            break; // Heap property satisfied
        }
        arr[root] = arr[child];
        root = child;
    }
    arr[root] = temp;
}

Sorting via Max Heap

In each pass, the maximum element at the root is moved to the sorted sequence by swapping it with the last element of the unsorted region. The remaining unsorted elements are then reorganized into a max heap by allowing the new root element to sink down to its correct position.

Efficiency Analysis

When a node sinks one level, it requires at most two key comparisons. For a tree of height h, a node at level i can sink up to h - i levels, resulting in no more than 2(h - i) comparisons. A complete binary tree with n nodes has a height of log₂n + 1.

• Time Complexity per pass: O(h) = O(log₂n)
• Total Time Complexity: O(n) (building) + O(n log₂n) (sorting) = O(n log₂n)
• Space Complexity: O(1)
• Stability: Unstable. Even if children are equal, prioritizing the left child during a swap can alter the relative order of equal elements.

Insertion and Deletion in Heaps

Insertion

For a min-heap, the new element is placed at the end of the array. It is then compared with its parent; if the new element is smaller, they are swapped. This rising process continues until the element can no longer rise.

Deletion

The deleted node is replaced by the bottom-rightmost element of the heap. This replacement element is then allowed to sink down the tree, swapping with the smaller child (in a min-heap), until it reaches its appropriate position.