FANDOM


Quicksort is a popular sorting algorithm for sorting arrays and lists. It is a comparison sort, meaning it sorts by comparing two elements at a time. It has a O(n log n) running time on average, but may have a quadratic running time for some inputs.

Algorithm Edit

Quicksort works by recursively partitioning the array into ordered partitions.

  1. Given a list of values arr, pick an element i out of the list, order all the elements smaller than of equal to i before it, and all the elements larger that i after it.
  2. Apply (1) to all elements before i and all elements after i.
  3. Finish when all lists are one or zero elements in size.

The element i is called the pivot, and it's selection is important for the performance of the algorithm.

Pivot Selection Edit

One way to select the pivot is to get the middle value. There techniques however will cause the sorting to have a quadratic running time for some inputs. To avoid these situations some implementations randomize the pivot selection, making the quadratic running time improbable.

PseudocodeEdit

Input: a list of values, arr.

quicksort(arr):
    if arr is empty:
	return arr
    p = pickPivotFrom(arr)
    lesser = arr.elementsSmallerOrEqual(p)
    greater = arr.elemetsGreater(p)
    return concatenate(quicksort(lesser), pivot, quicksort(greater))

Criticism Edit

Quicksort is not a stable sort. Which means that equal objects can have their order changed within the sorted list. It's complexity can sometimes be quadratic due to bad pivot selection, but despite these problems,it often outperforms it's main competitors - mergesort and heapsort.

 See Also Edit

Sorting algorithms
Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.