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



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store