Heap Sort Implementation

Heap sort utilizes a binary heap structure to sort elements. A heap is a complete binary tree where each node satisfies the heap property - either being a max-heap (parent >= children) or min-heap (parent <= children). The algorithm consists of two phases: heap construction and element exrtaction.

Heap Construction

The heapify operation maintains the heap property for a subtree:

void maintainHeap(int[] data, int size, int root) {
    int max = root;
    int leftChild = 2 * root + 1;
    int rightChild = 2 * root + 2;
    
    if (leftChild < size && data[leftChild] > data[max]) 
        max = leftChild;
    if (rightChild < size && data[rightChild] > data[max])
        max = rightChild;
    
    if (max != root) {
        swap(data, root, max);
        maintainHeap(data, size, max);
    }
}

void buildHeap(int[] data, int size) {
    for (int i = size/2 - 1; i >= 0; i--) {
        maintainHeap(data, size, i);
    }
}

Sorting Process

After building the heap, elements are extracted one by one:

void heapSort(int[] data, int size) {
    buildHeap(data, size);
    
    for (int i = size - 1; i > 0; i--) {
        swap(data, 0, i);
        maintainHeap(data, i, 0);
    }
}

Time complexity is O(n log n) with O(1) space complexity.

Quick Sort Implementation

Quick sort employs a divide-and-conquer strategy by selecting a pivot element and partitioning the array:

int partition(int[] data, int start, int end) {
    int pivot = data[start];
    while (start < end) {
        while (start < end && data[end] >= pivot) end--;
        data[start] = data[end];
        
        while (start < end && data[start] <= pivot) start++;
        data[end] = data[start];
    }
    data[start] = pivot;
    return start;
}

void quickSort(int[] data, int start, int end) {
    if (start < end) {
        int pivotPos = partition(data, start, end);
        quickSort(data, start, pivotPos - 1);
        quickSort(data, pivotPos + 1, end);
    }
}

Average case time complexity is O(n log n), though worst case is O(n²). Pivot selection strategies include:

• First/last element
• Random element
• Median-of-three

Quick sort performs well in practice and is often used in standard libraries.