Quicksort

ARRAY
SORTING

Problem

Implement the quicksort algorithm to sort an array of integers in ascending order. The function quickSort should take an array of integers as input and return a new array containing the sorted integers.

This is how it works:

  1. Select a pivot element from the array. You can choose the pivot in various ways, such as picking the first element, the last element, or a random element.
  2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
  3. Recursively apply the above steps to the sub-arrays.
  4. Combine the results of the sub-arrays and the pivot to form the sorted array.

Examples:

quickSort([9,4,7,3,5,8,1,6,2])
// returns [1,2,3,4,5,6,7,8,9]

Time Complexity

Average Case: O(n log n)

Worst Case: O(n^2), occurs when the smallest or largest element is always chosen as the pivot.

Loading...