Sorting Algorithms and Binary Search: A Comprehensive Guide

Bubble Sort

Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order. Each pass through the list places the next largest element in its correct position. This process continues until the entire list is sorted.

Selection Sort

Selection sort divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region.

Insertion Sort

Insertion sort builds the final sorted array one item at a time. It takes each element from the input and inserts it into its correct position in the growing sorted portion.

Shell Sort

Shell sort is an optimization of insertion sort that allows the exchange of items that are far apart. It starts by sorting elements that are distant from each other and progressively reduces the gap between elements to be compared.

Quick Sort

Quick sort is a divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot. Elements smaller then the pivot go to its left, and larger elements go to its right. The process is then applied recursively to the sub-arrays.

Merge Sort

Merge sort is another divide-and-conquer algorithm that divides the array into two halves, recursively sorts each half, and then merges the two sorted halves back together.

Heap Sort

Heap sort first transforms the array in to a max-heap, where the largest element is at the root. It repeatedly swaps the root with the last element, reduces the heap size, and heapifies the root to maintain the heap property.

Counting Sort

Counting sort works by counting the occurrences of each unique element in the input array and using those counts to compute the positions of elements in the sorted output.

Implementation of Sorting Algorithms

Bubble Sort Implementation

Time Complexity: O(n²)

public static void bubbleSort(int[] data) {
    int n = data.length;
    for (pass = 0; pass < n - 1; pass++) {
        for (current = 0; current < n - pass - 1; current++) {
            if (data[current] > data[current + 1]) {
                // Swap elements
                int temporary = data[current];
                data[current] = data[current + 1];
                data[current + 1] = temporary;
            }
        }
    }
}

Selection Sort Implementation

Time Complexity: O(n²)

public static void selectionSort(int[] array) {
    int length = array.length;
    
    for (position = 0; position < length - 1; position++) {
        int minIndex = position;
        
        // Find the minimum element in the remaining unsorted array
        for (scan = position + 1; scan < length; scan++) {
            if (array[scan] < array[minIndex]) {
                minIndex = scan;
            }
        }
        
        // Swap the found minimum element with the current position
        if (minIndex != position) {
            int swapTemp = array[position];
            array[position] = array[minIndex];
            array[minIndex] = swapTemp;
        }
    }
}

Quick Sort Implementation

Time Complexity: O(n log n) average case, O(n²) worst case

public static void quickSort(int[] values, int leftBound, int rightBound) {
    if (leftBound >= rightBound) {
        return;
    }
    
    // Select pivot element (leftmost element)
    int pivot = values[leftBound];
    int rightPointer = rightBound;
    int leftPointer = leftBound;
    
    while (leftPointer != rightPointer) {
        // Move right pointer left until finding element smaller than pivot
        while (values[rightPointer] >= pivot && leftPointer < rightPointer) {
            rightPointer--;
        }
        
        // Move left pointer right until finding element larger than pivot
        while (values[leftPointer] <= pivot && leftPointer < rightPointer) {
            leftPointer++;
        }
        
        // Swap elements at left and right pointers
        if (leftPointer < rightPointer) {
            int temp = values[leftPointer];
            values[leftPointer] = values[rightPointer];
            values[rightPointer] = temp;
        }
    }
    
    // Swap pivot with the meeting point
    values[leftBound] = values[leftPointer];
    values[leftPointer] = pivot;
    
    // Recursively sort left and right partitions
    quickSort(values, leftBound, leftPointer - 1);
    quickSort(values, leftPointer + 1, rightBound);
}

Merge Sort Implementation

Time Complexity: O(n log n)

public class MergeSort {
    public static void main(String[] args) {
        int[] numbers = { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] sortedNumbers = mergeSort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.toString(sortedNumbers));
    }

    public static int[] mergeSort(int[] numbers, int left, int right) {
        if (left == right) {
            return new int[] { numbers[left] };
        }

        // Divide the array
        int mid = left + (right - left) / 2;
        int[] leftPart = mergeSort(numbers, left, mid);
        int[] rightPart = mergeSort(numbers, mid + 1, right);
        int[] mergedArray = new int[leftPart.length + rightPart.length];

        // Merge the sorted parts
        int mergeIndex = 0, leftIndex = 0, rightIndex = 0;
        while (leftIndex < leftPart.length && rightIndex < rightPart.length) {
            mergedArray[mergeIndex++] = leftPart[leftIndex] < rightPart[rightIndex] 
                ? leftPart[leftIndex++] : rightPart[rightIndex++];
        }
        
        // Copy remaining elements
        while (leftIndex < leftPart.length) {
            mergedArray[mergeIndex++] = leftPart[leftIndex++];
        }
        while (rightIndex < rightPart.length) {
            mergedArray[mergeIndex++] = rightPart[rightIndex++];
        }
        
        return mergedArray;
    }
}

Heap Sort Implementation