QuickSort

Algorithm

  • Pick a pivot from the list.
  • Reorder the list so that all the elements with values less than the pivot are arranged before the pivot and all the other elements are arranged after the pivot. Numbers equal to the pivot can go in either partitions. At this point, the pivot is in its final position.
  • Recursively apply the above steps to the left partition and to the right partition.

Performance

  • Worst case: $O(n^{2})$
  • Best case: $O(n\log{n})$
  • Average case: $O(n\log{n})$
  • Space complexity: $O(n)$ auxiliary or $O(\log{n})$ auxiliary

Implementations


fuss/algorithms/sorting/quicksort.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.