Home Tutorials Training Consulting Products Books Company Donate Contact us









Online Training

Quick links

Share

Quicksort with Java. This article describes how to implement Quicksort with Java.
-->

3. Complexity Analysis

The following describes the runtime complexity of quicksort.

Quicksort is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. Quicksort will in the best case divide the array into almost two identical parts. It the array contains n elements then the first run will need O(n). Sorting the remaining two sub-arrays takes 2* O(n/2). This ends up in a performance of O(n log n).

In the worst case quicksort selects only one element in each iteration. So it is O(n) + O(n-1) + (On-2).. O(1) which is equal to O(n^2).

The average case of quicksort is O(n log n).

-->

Copyright © 2012-2017 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.