[Home]
QuickSort

| CodeRaptors | Projects | Tips and Scripts | Guides | Links |


Each colored bar represents a list element. The height and color correspond to the value of the element. The green bar signals a read operation, the blue one a write operation and the white one the currently selected pivot element.

Virtual time is a rough estimate of the algorithm speed. It can be used to compare the different algorithms on this website, but it's not really a good benchmark. The actual running time of the applet is not related to the virtual time and says nothing about the speed of the algorithm, it is trimmed to make the slower ones bearable to watch and the faster ones possible to see.

The Quicksort algorithm has complexity O(n * log(n)) where n is the number of elements. If one knows nothing about the lists to be sorted it is generally a very good choice but if the lists are almost always sorted (or nearly sorted) there are other algorithms which are faster. It's also worth noting that it has a worst case running time of O(n^2). If one knows enough about the implementation one can manufacture lists which will take that long to sort which is a potential security risk.

For each partition being sorted, the pivot element is selected as the median of the first, middle and last element of the partition. This is done primarily to prevent the Quicksort worst case scenario of already sorted lists (or reverse sorted lists).

More on Quicksort here.

<< Go back to the sorting algorithms



Search: