The key of quick sort is partition. Select an element randomly as a pivot, and then make all elements less than pivot moved to left, and all elements bigger than pivot moved to right, and finally make pivot at the center. Say we have an array of [2,9,4,8,5], and we pick the last element 5 as the pivot, and after partition, we shoud get [2,4,5,9,8].

As you can see, one partition cannot make the array sorted, but only can make it half sorted. What we need to do next is to do the partition process on the left and on the right recursively. In this way, after average log(n) time partition, we should have the array sorted.

Then let's see the details of partition in code.

function partition(nums: number[], low: number, high: number): number {
    // choose last element as pivot
    let pivot = nums[high]; 

    // init a pointer at the low index
    let p = low; 

    for (let i = low; i < high; i++) {

        // if new element is less than or equal to pivot
        // swap the new element with the element which the pointer points
        if (nums[i] <= pivot) {
            [nums[i], nums[p]] = [nums[p], nums[i]];
            p += 1;
        }
    }

    // now all elements before pointer should be less than pivot
    // swap the pivot with the element which current pointer points
    [nums[high], nums[p]] = [nums[p], nums[high]];

    // return the pointer, pivot(middle) element
    return p;
}

Now we know the how the partition works, next is the recursive part.

function quickSort(nums: number[], low: number, high: number) {
    if (low > high) return;
    const mid = partition(nums, low, high);
    quickSort(nums, low, mid - 1);
    quickSort(nums, mid + 1, high);
}

Now the quick sort algorithm is done. Let's use it to solve the leetcode Kth Largest Element in an Array problem.

We can use the algorithm directly to sort the array and get the result.

function findKthLargest(nums: number[], k: number): number {
    quickSort(nums, 0, nums.length-1)
    return nums[nums.length - k] // [1,2,3,4,5], k = 2, 
};

But we can make some changes and make it faster. The problem is to find kth largest element. So what we really want to do is to find a element, which the number of all elements bigger than it should be exactly k. As you can see, this is exactly what the pivot do. So actually we don't need to sort the whole array. If the pivot's index is at the right place, then the pivot should be the result.

function quickSort(nums: number[], low: number, high: number, k: number) {
    if (low > high) return;
    const mid = partition(nums, low, high);

    if (mid < k) {
        quickSort(nums, mid + 1, high, k);
    } else if (mid > k) {
        quickSort(nums, low, mid - 1, k);
    }
}

function findKthLargest(nums: number[], k: number): number {
    const i = nums.length - k;
    quickSort(nums, 0, nums.length - 1, i);
    return nums[i];
};