NC Note: Quick sort, merge sort and quick select

1. Quick Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        int pivot = A[(start + end) / 2];

        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left++;
            }
            
            while (left <= right && A[right] > pivot) {
                right--;
            }
            
            if (left <= right) {
                swap(A, left, right);
                left++;
                right--;
            }
        }
        
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

2. Merge Sort

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }

        int[] temp = new int[A.length];

        sortIntegers2Helper(A, temp, 0, A.length - 1);
    }

    private void sortIntegers2Helper(int[] A, int[] temp, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        sortIntegers2Helper(A, temp, start, mid);
        sortIntegers2Helper(A, temp, mid + 1, end);

        // merge
        //
        merge(A, temp, start, end);
    }

    private void merge(int[] A, int[] temp, int start, int end) {
        int mid = start + (end - start) / 2;
        int i = start;
        int j = mid + 1;
        int k = start;

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

        for (i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}

3. Quick Select

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n);
    }
    
    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        
        if (k <= j) {
            return kthLargestElementHelper(nums, start, j, k);
        } else if (k >= i) {
            return kthLargestElementHelper(nums, i, end, k);
        } else {
            return nums[k];
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Another version:

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0 || n > nums.length) {
            return -1;
        }

        return kthLargestElementHelper(nums, 0, nums.length - 1, n);
    }

    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }

        int i = start;
        int j = end;

        int pivot = nums[(i + j) / 2];

        while (i <= j) {
            while (i <= j && nums[i] > pivot) {
                i++;
            }

            while (i <=j && nums[j] < pivot) {
                j--;
            }

            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
                j--;
            }
        }

        if (j - start + 1 >= k) {
            return kthLargestElementHelper(nums, start, j, k);
        }

        if (i - start + 1 <= k) {
            return kthLargestElementHelper(nums, i, end, k - i + start);
        }

        return nums[j + 1];
    }
}

Another version:

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n + 1);
    }
    
    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            
            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                
                i++;
                j--;
            }
        }
        
        if (j - start + 1 >= k) {
            return kthLargestElementHelper(nums, start, j, k);
        }
        
        if (i - start + 1 <= k) {
            return kthLargestElementHelper(nums, i, end, k - i + start);
        }
        
        return nums[j + 1];
    }
}