Quick Sort — JavaScript implementation

The idea of quick sort is

• Given an array, recursively splitting the array by a pivot, that is,
  – all values less than the pivot value are moved to the left of pivot
  – all values greater than the pivot are moved to the right of pivot
  – until the array to be split has less than 2 elements
• The left and right subarray are not sorted.
• The elements rearrange is done in place, that is, there is no need to create new array.

Helper function

First, we create a helper function.

Given an array, this helper function should rearrange the array such that

• Pick up any element as the pivot (In the example code, we use the element at index 0)
• Split the array by the pivot
• Return the pivot index

Driver function

• Call the helper function
• When the helper return the pivot index, recursively call the helper on the left subarray and right subarray
• The helper will rearrange the given array in place.
• The base case occurs when the given array has less than 2 elements.

Problem can be solved

• LeetCode 912. Sort an Array
• LeetCode 215. Kth Largest Element in an Array
• LeetCode 283. Move Zeroes