Java Advanced Sorting

What is Sorting?

Sorting is the process of arranging elements in a specific order, typically in ascending or descending order. Advanced sorting techniques are designed for efficiency and are often used in scenarios involving large datasets or complex conditions.

Advanced Sorting Techniques in Java

1. Merge Sort
2. Quick Sort
3. Heap Sort
4. Counting Sort
5. Radix Sort
6. Bucket Sort

These sorting techniques are more efficient than basic algorithms like Bubble Sort or Insertion Sort, especially for large datasets.

1. Merge Sort

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

Key Characteristics:

• Time Complexity: O(nlog⁡n)
• Space Complexity: O(n)
• Stable Sort: Yes

Code Example:

import java.util.Arrays;

public class MergeSortExample {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            
            // Sort left and right halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            
            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        System.arraycopy(arr, left, leftArray, 0, n1);
        System.arraycopy(arr, mid + 1, rightArray, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k++] = leftArray[i++];
            } else {
                arr[k++] = rightArray[j++];
            }
        }

        while (i < n1) {
            arr[k++] = leftArray[i++];
        }

        while (j < n2) {
            arr[k++] = rightArray[j++];
        }
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        mergeSort(array, 0, array.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

2. Quick Sort

Quick Sort is another divide-and-conquer algorithm that selects a pivot element and partitions the array into two subarrays based on whether elements are less than or greater than the pivot.

Key Characteristics:

• Time Complexity: Best/Average Case: O(nlog⁡n), Worst Case: O(n2)
• Space Complexity: O(log⁡n)
• Stable Sort: No

Code Example:

import java.util.Arrays;

public class QuickSortExample {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(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;
    }

    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        quickSort(array, 0, array.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

Output:

Sorted array: [1, 5, 7, 8, 9, 10]

3. Heap Sort

Heap Sort uses a binary heap structure to sort an array.

Key Characteristics:

• Time Complexity: O(nlog⁡n)
• Space Complexity: O(1)
• Stable Sort: No

Code Example:

import java.util.Arrays;

public class HeapSortExample {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 10, 3, 5, 1};
        heapSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

Output:

Sorted array: [1, 3, 4, 5, 10]

4. Counting Sort

Counting Sort works well for sorting integers or elements with a fixed range. It counts the frequency of each element and uses this information to sort.

5. Radix Sort

Radix Sort processes elements digit by digit, starting from the least significant digit to the most significant digit.

6. Bucket Sort

Bucket Sort divides the array into buckets and sorts each bucket individually before merging them.