Selection Sort

Core Concept

Selection sort operates by repeatedly finding the minimum element from the unsorted portion and moving it to the beginning. The algorithm maintains two subarrays: the sorted left portion and the unsorted right portion. In each iteration, the smallest element from the unsorted subarray is selected and swapped with the leftmost unsorted element.

The process begins with the first element considered as sorted. A pointer traverses the remaining elements to locate the smallest value. Once found, it exchanges positions with the element at the current sorted boundary. This boundary then increments by one, expanding the sorted region.

Implementation Details

public void performSelectionSort(int[] elements) {
    int length = elements.length;
    
    for (int sortedBoundary = 0; sortedBoundary < length - 1; sortedBoundary++) {
        int minimumPosition = sortedBoundary;
        
        for (int scanner = sortedBoundary + 1; scanner < length; scanner++) {
            if (elements[scanner] < elements[minimumPosition]) {
                minimumPosition = scanner;
            }
        }
        
        if (minimumPosition != sortedBoundary) {
            int temporaryValue = elements[minimumPosition];
            elements[minimumPosition] = elements[sortedBoundary];
            elements[sortedBoundary] = temporaryValue;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²) in all cases. The outer loop runs n-1 times, while the inner loop executes (n-1) + (n-2) + ... + 1 comparisons, forming an arithmetic series that simplifies to O(n²). This performance holds regardless of initial array order.

Space Complexity: O(1) as sorting occurs in-place with constant extra space.

Stability: Unstable. Equal elements may change relative positions during swapping operations.

Bidirectional Selection Sort

Core Concept

This optimization processes both ends simultaneously. Each pass identifies both the smallest and largest elements in the unsorted region, placing them at their correct positions at the left and right boundaries respectively. The sorted region expands from both ends toward the center, reducing total iterations by half.

Special attention is required when the maximum element is positioned at the left boundary, as swapping the minimum first would overwrite this value.

Implementation Details

public void performBidirectionalSelectionSort(int[] data) {
    int start = 0;
    int end = data.length - 1;
    
    while (start < end) {
        int smallestIndex = start;
        int largestIndex = start;
        
        for (int current = start + 1; current <= end; current++) {
            if (data[current] < data[smallestIndex]) {
                smallestIndex = current;
            }
            if (data[current] > data[largestIndex]) {
                largestIndex = current;
            }
        }
        
        swapElements(data, start, smallestIndex);
        
        if (largestIndex == start) {
            largestIndex = smallestIndex;
        }
        
        swapElements(data, end, largestIndex);
        
        start++;
        end--;
    }
}

private void swapElements(int[] array, int first, int second) {
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

Heap Sort

Core Concept

Heap sort leverages the heap data structure's properties. The process involves two phases: first constructing a max-heap from the array, then repeatedly extracting the maximum element. After building the heap, the root (largest element) swaps with the last item. The heap size reduces by one, and the new root undergoes heapification to restore max-heap properties. This continues until the entire array is sorted.

Implementation Details

public void executeHeapSort(int[] values) {
    constructMaxHeap(values);
    
    for (int lastUnsorted = values.length - 1; lastUnsorted > 0; lastUnsorted--) {
        interchange(values, 0, lastUnsorted);
        maintainHeapProperty(values, 0, lastUnsorted);
    }
}

private void constructMaxHeap(int[] input) {
    int finalParent = (input.length - 2) / 2;
    for (int node = finalParent; node >= 0; node--) {
        maintainHeapProperty(input, node, input.length);
    }
}

private void maintainHeapProperty(int[] heap, int root, int heapSize) {
    int largestChild = root * 2 + 1;
    
    while (largestChild < heapSize) {
        if (largestChild + 1 < heapSize && heap[largestChild + 1] > heap[largestChild]) {
            largestChild++;
        }
        
        if (heap[largestChild] > heap[root]) {
            interchange(heap, largestChild, root);
            root = largestChild;
            largestChild = root * 2 + 1;
        } else {
            break;
        }
    }
}

private void interchange(int[] arr, int i, int j) {
    int buffer = arr[i];
    arr[i] = arr[j];
    arr[j] = buffer;
}

Complexity Analysis

Time Complexity: O(n log n). Building the initial heap takes O(n) time. Each of the n-1 extraction operations requires O(log n) for heapification, resulting in O(n log n) total time.

Space Complexity: O(1) auxiliary space, as sorting occurs in-place.

Stability: Unstable. The heapification process can alter the relative order of equal elements.

Bubble Sort

Core Concept

Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. Each complete pass places the next largest element in its correct position at the end of the array. The algorithm terminates when a complete pass makes no swaps, indicating the array is sorted.

An optimization tracks whether any swaps occurred during a pass, allowing early termination for partially sorted arrays.

Implementation Details

public void conductBubbleSort(int[] sequence) {
    int itemCount = sequence.length;
    boolean swapped;
    
    for (int pass = 0; pass < itemCount - 1; pass++) {
        swapped = false;
        
        for (int position = 0; position < itemCount - pass - 1; position++) {
            if (sequence[position] > sequence[position + 1]) {
                exchange(sequence, position, position + 1);
                swapped = true;
            }
        }
        
        if (!swapped) {
            break;
        }
    }
}

private void exchange(int[] data, int firstIndex, int secondIndex) {
    int temporary = data[firstIndex];
    data[firstIndex] = data[secondIndex];
    data[secondIndex] = temporary;
}

Complexity Analysis

Time Complexity: O(n²) in the worst and average cases. The inner loop performs (n-1) + (n-2) + ... + 1 comparisons. The best case is O(n) when the array is already sorted and the algorithm terminates after one pass.

Space Complexity: O(1) as it sorts in-place.

Stability: Stable. Equal elements never swap positions, preserving their original relative order.