Skip to main content
Lesson 26 - Quicksort
Lesson MenuPreviousNext
  
Order of Quicksort page 4 of 6

  1. Determining the order of quicksort, O (N*log2N), is a difficult process. The best way to understand it is to imagine a hypothetical situation where each call of quicksort results in sublists of the same size. (refer to the T.A.26.2, Log2N Steps diagram)

  2. If a list has 128 elements, the number of calls of quicksort required to move a value into its correct spot is log2128, which equals 7 steps. Dividing the list in half gives us the log2N aspect of quicksort.

  3. But we need to do this to 128 numbers, so the approximate number of steps to sort 128 numbers will be 128*log2128. A general expression of the order of quicksort will be:

    O(N * log2N)

    An O(N * log2N) algorithm is a more specific designation of the broader category called O(N * log N).

  4. A graph of an O(N*log2N) algorithm is very close to a linear algorithm, for large values of N. The log2N number of steps grows very slowly making quicksort a dramatic improvement over the O(N2) sorts.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.