Introduction to Sorting Algorithms

Sorting is the fundamental process of rearranging a collection of data into a specific sequence, typically ascending or descending order based on the values of the elements. In computer science, various algorithms exist to achieve this, each with unique characteristics regarding efficiency and memory usage. This article focuses on the implementation and analysis of three specific comparison-based sorting algorithms: Selection Sort, Heap Sort, and Bubble Sort.

Selection Sort

Selection sort operates by dividing the input list into two parts: a sorted sublist at the left end and an unsorted sublist at the right end. Initially, the sorted sublist is empty. The algorithm proceeds by iterating through the unsorted sublist to find the minimum and maximum values. The minimum value is swapped with the leftmost unsorted element, and the maximum value is swapped with the rightmost unsorted element. This bidirectional approach reduces the number of passes required compared to the standard single-direction selection sort.

Algorithm Implementation:

#include <stdio.h>

void swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void bidirectionalSelectionSort(int* data, int size) {
    int begin = 0;
    int end = size - 1;

    while (begin < end) {
        int minIndex = begin;
        int maxIndex = begin;

        // Iterate through the unsorted range to find min and max
        for (int i = begin + 1; i <= end; i++) {
            if (data[i] > data[maxIndex]) {
                maxIndex = i;
            }
            if (data[i] < data[minIndex]) {
                minIndex = i;
            }
        }

        // Place the minimum element at the correct position
        if (minIndex != begin) {
            swap(&data[begin], &data[minIndex]);
        }

        // Special handling: if the max element was at 'begin',
        // it was moved to 'minIndex' during the previous swap
        if (maxIndex == begin) {
            maxIndex = minIndex;
        }

        // Place the maximum element at the correct position
        if (maxIndex != end) {
            swap(&data[end], &data[maxIndex]);
        }

        begin++;
        end--;
    }
}

Algorithm Analysis:

• Time Complexity: O(N²). The algorithm involves nested loops; regardless of the input order, it scans the remaining unsorted elements to find min/max values.
• Space Complexity: O(1). It performs sorting in place, requiring only a constant amount of additional memory for variables.
• Stability: Unstable. Since elements can jump long distances (e.g., swapping a non-adjacent maximum), the relative order of equal elements may change.

Heap Sort

Heap sort utilizes a binary heap data structure. To sort data in ascending order, the algorithm first constructs a Max Heap. In a Max Heap, the parent node is always greater than its children. Once the heap is built, the largest element (the root) is swapped with the last element of the array. The heap size is then reduced by one, and the "heapify" process is called on the new root to restore the heap property. This cycle repeats until the entire array is sorted.

Algorithm Implementation:

// Maintain the max-heap property for a subtree rooted at index 'root'
void heapify(int* arr, int size, int root) {
    int largest = root;
    int leftChild = 2 * root + 1;
    int rightChild = 2 * root + 2;

    // Check if left child exists and is greater than root
    if (leftChild < size && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }

    // Check if right child exists and is greater than largest so far
    if (rightChild < size && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If largest is not root, swap and continue heapifying
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        heapify(arr, size, largest);
    }
}

void heapSort(int* arr, int size) {
    // Build the max heap (rearrange array)
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, size, i);
    }

    // Extract elements from heap one by one
    for (int i = size - 1; i > 0; i--) {
        // Move current root (maximum) to end
        swap(&arr[0], &arr[i]);
        
        // Call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

Algorithm Analysis:

• Time Complexity: O(N log N). Building the heap takes O(N), and each of the N-1 extracsions takes O(log N) time.
• Space Complexity: O(1). The standard implementation works in place.
• Stability: Unstable. The swapping of elements across the heap structure during extraction disrupts the original relative order of duplicate keys.

Bubble Sort

Bubble sort is a simple comparison-based algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This pass is repeated until the list is sorted. The name "bubble sort" comes from the way smaller or larger elements "bubble" to the top of the list (depending on the order) with each iteration. An optimization is added where a flag checks if any swaps occurred; if no swaps occur during a pass, the list is already sorted, and the algorithm can terminate early.

Algorithm Implementation:

void optimizedBubbleSort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        
        // Last i elements are already in place
        for (int j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }

        // If no two elements were swapped by inner loop, break
        if (swapped == 0) {
            break;
        }
    }
}

Algorithm Analysis:

• Time Complexity: O(N²) in the worst and average cases. In the best case (already sorted array), with the optimization flag, the time complexity reduces to O(N).
• Space Complexity: O(1). It operates in place.
• Stability: Stable. Since it only swaps adjacent elements when they are strictly unequal (or strictly greater for ascending order), it preserves the relative order of equal elements.