Core Concepts of Sorting

Definition of Sorting Arranging a sequence of objects based on a specific key.

Terminology

• Stable: If element a is originally before b and a equals b, after sorting a remains before b.
• Unstable: If a is originally before b and a equals b, after sorting a may appear after b.
• Internal Sort: All sorting operations are performed in memory.
• External Sort: Data is too large for memory, requiring disk storage and data transfer during sorting.
• Time Complexity: The computational time required by an algorithm.
• Space Complexity: The memory required to execute a program.

Algorithm Summary Notes

• n: Data size.
• k: Number of "buckets".
• In-place: Uses constant memory, no extra space.
• Out-place: Requires additional memory.

Comparison vs. Non-Comparison Sorts Common algorithms like Quicksort, Merge Sort, Heap Sort, and Bubble Sort are comparison sorts. The final order depends on direct comparisons between elements. Each element must be compared to others to determine its position.

Non-comparision sorts, such as Counting Sort, Radix Sort, and Bucket Sort, determine an element's position by counting how many elements precede it. They can often be completed in a single pass with time complexity O(n), but they require extra space and have specific data requirements.

---

1. Bubble Sort

Bubble Sort repeatedly steps through a list, comparing adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed.

Algorithm Description

1. Compare each pair of adjacent elements from the start.
2. If the first element is greater than the second, swap them.
3. Repeat for every pair up to the last unsorted element.
4. Continue passes until the list is fully sorted.

Java Implementation

public class SortingAlgorithms {
    public static int[] bubbleSort(int[] arr) {
        if (arr.length <= 1) return arr;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
        return arr;
    }
}

Complexity Analysis

• Best Case: O(n)
• Worst Case: O(n²)
• Average Case: O(n²)

---

2. Selection Sort

Selection Sort divides the input into a sorted and an unsorted region. It repeatedly finds the minimum element from the unsorted region and moves it to the end of the sorted region.

Algorithm Description

1. The sorted region starts empty; the unsorted region is the entire list.
2. Find the smallest element in the unsorted region.
3. Swap it with the first element of the unsorted region, expanding the sorted region.
4. Repeat until the unsorted region is empty.

Java Implementation

public static int[] selectionSort(int[] arr) {
    if (arr.length <= 1) return arr;
    for (int i = 0; i < arr.length - 1; i++) {
        int minPos = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minPos]) {
                minPos = j;
            }
        }
        if (minPos != i) {
            int temp = arr[i];
            arr[i] = arr[minPos];
            arr[minPos] = temp;
        }
    }
    return arr;
}

Complexity Analysis

• Best, Worst, Average Cases: O(n²)

---

3. Insertion Sort

Insertion Sort builds the final sorted array one item at a time by repeatedly taking the next element and inserting it into its correct position within the sorted portion.

Algorithm Description

1. Start with the first element as sorted.
2. Pick the next element.
3. Scan backward through the sorted portion to find its correct position.
4. Shift larger elements one position to the right.
5. Insert the element into the correct spot.
6. Repeat for all elements.

Java Implementation

public static int[] insertionSort(int[] arr) {
    if (arr.length <= 1) return arr;
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Complexity Analysis

• Best Case: O(n)
• Worst Case: O(n²)
• Average Case: O(n²)

---

4. Shell Sort

Shell Sort is an optimization of Insertion Sort that allows the exchange of items that are far apart. It sorts elements that are a certain gap apart, then reduces the gap untill it becomes 1.

Algorithm Description

1. Choose a gap sequence (e.g., starting at n/2 and halving).
2. Perform a gapped insertion sort for each gap size.
3. Continue until the gap is 1, performing a final standard insertion sort.

Java Implementation

public static int[] shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > current) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

Complexity Analysis

• Best, Worst, Average Cases (for chosen gap): O(n log² n)

---

5. Merge Sort

Merge Sort is a divide-and-conquer algorithm that recursively splits the array into halves, sorts them, and then merges the sorted halves.

Algorithm Description

1. Divide the unsorted list into n sublists, each containing one element.
2. Repeatedly merge sublists to produce new sorted sublists until only one sublist remains.

Java Implementation

public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int mid = arr.length / 2;
    int[] leftHalf = Arrays.copyOfRange(arr, 0, mid);
    int[] rightHalf = Arrays.copyOfRange(arr, mid, arr.length);
    return combine(mergeSort(leftHalf), mergeSort(rightHalf));
}

private static int[] combine(int[] left, int[] right) {
    int[] merged = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            merged[k++] = left[i++];
        } else {
            merged[k++] = right[j++];
        }
    }
    while (i < left.length) merged[k++] = left[i++];
    while (j < right.length) merged[k++] = right[j++];
    return merged;
}

Complexity Analysis

• Best, Worst, Average Cases: O(n log n)

---

6. Quick Sort

Quick Sort selects a 'pivot' element and partitions the array so that elements less than the pivot are on the left and greater elements are on the right. It then recursively sorts the sub-arrays.

Algorithm Description

1. Choose a pivot element from the array.
2. Partition: Rearrange elements so that all elements less than the pivot come before it, and all greater elements come after.
3. Recursively apply the above steps to the left and right sub-arrays.

Java Implementation

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int partitionIdx = partitionArray(arr, low, high);
        quickSort(arr, low, partitionIdx - 1);
        quickSort(arr, partitionIdx + 1, high);
    }
}

private static int partitionArray(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Complexity Analysis

• Best Case: O(n log n)
• Worst Case: O(n²)
• Average Case: O(n log n)

---

7. Heap Sort

Heap Sort uses a binary heap data structure. It first builds a max-heap from the input data, then repeatedly extracts the maximum element and rebuilds the heap.

Algorithm Description

1. Build a max-heap from the input array.
2. Swap the root (maximum value) with the last element of the heap.
3. Reduce the heap size by one and heapify the root.
4. Repeat until the heap size is one.

Java Implementation

public static void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int heapSize, int rootIdx) {
    int largest = rootIdx;
    int leftChild = 2 * rootIdx + 1;
    int rightChild = 2 * rootIdx + 2;
    if (leftChild < heapSize && arr[leftChild] > arr[largest]) largest = leftChild;
    if (rightChild < heapSize && arr[rightChild] > arr[largest]) largest = rightChild;
    if (largest != rootIdx) {
        int swap = arr[rootIdx];
        arr[rootIdx] = arr[largest];
        arr[largest] = swap;
        heapify(arr, heapSize, largest);
    }
}

Complexity Analysis

• Best, Worst, Average Cases: O(n log n)

---

8. Counting Sort

Counting Sort counts the number of objects that have each distinct key value, then uses arithmetic to determine the positions of each key in the output sequence.

Algorithm Description

1. Find the minimum and maximum values in the array.
2. Create a count array to store the frequency of each value.
3. Modify the count array to store cumulative counts.
4. Build the output array using the count array to place elements in sorted order.

Java Implementation

public static int[] countingSort(int[] arr) {
    if (arr.length == 0) return arr;
    int minVal = arr[0], maxVal = arr[0];
    for (int num : arr) {
        if (num < minVal) minVal = num;
        if (num > maxVal) maxVal = num;
    }
    int range = maxVal - minVal + 1;
    int[] count = new int[range];
    for (int num : arr) count[num - minVal]++;
    for (int i = 1; i < range; i++) count[i] += count[i - 1];
    int[] sorted = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        sorted[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    return sorted;
}

Complexity Analysis

• Best, Worst, Average Cases: O(n + k), where k is the range of input.

---

9. Bucket Sort

Bucket Sort distributes elements into a number of buckets. Each bucket is then sorted individually, either using a different algorithm or recursively applying bucket sort.

Algorithm Description

1. Set up an array of empty buckets.
2. Scatter: Place each element into its corresponding bucket.
3. Sort each non-empty buckeet.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Java Implementation

public static float[] bucketSort(float[] arr) {
    if (arr.length <= 1) return arr;
    int bucketCount = arr.length;
    ArrayList<Float>[] buckets = new ArrayList[bucketCount];
    for (int i = 0; i < bucketCount; i++) buckets[i] = new ArrayList<>();
    for (float val : arr) {
        int bucketIndex = (int) (val * bucketCount);
        buckets[bucketIndex].add(val);
    }
    for (ArrayList<Float> bucket : buckets) Collections.sort(bucket);
    int index = 0;
    for (ArrayList<Float> bucket : buckets) {
        for (float val : bucket) {
            arr[index++] = val;
        }
    }
    return arr;
}

Complexity Analysis

• Best Case: O(n + k)
• Worst Case: O(n²)
• Average Case: O(n + k)

---

10. Radix Sort

Radix Sort processes integer digits by grouping numbers by each individual digit, from the least significant to the most significant, using a stable sorting subroutine (often counting sort).

Algorithm Description

1. Find the maximum number to know the number of digits.
2. Perform counting sort for each digit, starting from the least significant digit (LSD).
3. Repeat the process for each subsequent digit.

Java Implementation

public static int[] radixSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
    return arr;
}

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    for (int num : arr) count[(num / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
}

Complexity Analysis

• Best, Worst, Average Cases: O(n * k), where k is the number of digits.