Question

Describe the efficiency of quicksort algorithm

Answer 1

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.[contradictory]

Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting. It is very similar to selection sort, except that it does not always choose worst-case partition.

Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort nitems. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Answer 2

The space used by quicksort depends on the version used. The in-place version of quicksort has a space complexity of O(log n), even in the worst case, when it is carefully implemented using the following strategies: in-place partitioning is used. This unstable partition requires O(1) space.

Worst-case space complexity: O(n) auxiliary (naive); O(log n) auxiliary (Sedgewick 1...

Worst-case performance: O(n2)

Best-case performance: O(n log n) (simple partition); or O(n) (three-way partition and ...

Average performance: O(n log n)