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.
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
- 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.