Sorting

Sorting

1. Count Sort

Time: O(n), Space: O(n)

public static void countSort(int[] nums) {
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

    for (int num : nums) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    int[] count = new int[max - min + 1];
    for (int num : nums) {
        ++count[num - min];
    }

    int index = 0;
    for (int i = min; i <= max; i++) {
        while (count[i - min] > 0) {
        nums[index] = i;
        ++index;
        --count[i - min];
        }
    }
}

2. Bucket Sort

Time: O(n + k), Space: O(n)

// To be continued

3. Quick Sort

Time: O(nlogn), Space: O(logn)

    public static void quickSort(int[] nums) {
        recQuickSort(nums, 0, nums.length - 1);
    }

    public static void recQuickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(nums, start, end);
        recQuickSort(nums, start, pivot - 1);
        recQuickSort(nums, pivot + 1, end );
    }

    public static int partition(int[] nums, int start, int end) {
        // Use the middle element as pivot
        int pivot = (start + end) >> 1;
        // Put the pivot to the end
        swap(nums, pivot, end);

        // Put element smaller than the pivot to the first half of array
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                swap(nums, i, start);
                ++start;
            }
        }
        // Put the pivot back to position it should be in after partition
        swap(nums, start, end);
        return start;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

• Quick Select (Find the Kth Largest/Smallest Number)

   public int quickSelect(int[] nums, int k, int start, int end) {
        int pivot = partition(nums, start, end);

        if (pivot < k) {
            return quickSelect(nums, k, pivot + 1, end);
        }
        else if (pivot > k) {
            return quickSelect(nums, k, start, pivot);
        }
        else {
            return nums[pivot];
        }
    }

    public int partition(int[] nums, int start, int end) {
        int mid = (start + end) >> 1;
        swap(nums, mid, end);

        for (int i = start; i < end; i++) {
            // To get the Kth largest number, put element larger than the pivot to the left 
            if (nums[i] > nums[end]) {
                swap(nums, start, i);
                ++start;
            }
        }
        swap(nums, start, end);
        return start;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

4. Merge Sort

Time: O(nlogn), Space: O(n)

    public void mergeSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        mergeSort(nums, 0, nums.length - 1);
    }

    public void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;

        while (i <= mid || j <= end) {
            if (i > mid || (j <= end && nums[j] < nums[i])) {
                temp[k++] = nums[j++];
            }
            else {
                temp[k++] = nums[i++];
            }
        }

        for (int index = 0; index < k; index++) {
            nums[start + index] = temp[index];
        }
    }

5. Questions

• Merge Sort: Reverse Pairs,

• Quick Sort: Kth Largest Element in an Array, Wiggle Sort II

• Count Sort: Sort Colors, H-Index

• Bucket Sort: Sort Characters By Frequency, Top K Frequent Elements, Maximum Gap