Sorting Algorithm Tutorials - Herong's Tutorial Examples - Version 6.01, by Dr. Herong Yang
Quicksort - Performance
This section provides a tutorial on how to measure the performance of the Quicksort algorithm. My first Java implementation of Quicksort is performing somewhere between O(N*Log2(N) and O(N*N) order levels.
Now let's see how my Java implementation of the Quicksort algorithm performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:
Array size: 10000 Average sorting time: 18 milliseconds Number of tests: 1000 Performance: 1.8 O(N) nanoseconds Performance: 0.13546349804879154 O(N*Log2(N)) nanoseconds Performance: 1.8E-4 O(N*N) nanoseconds Array size: 20000 Average sorting time: 48 milliseconds Number of tests: 1000 Performance: 2.4 O(N) nanoseconds Performance: 0.16797650570256523 O(N*Log2(N)) nanoseconds Performance: 1.2E-4 O(N*N) nanoseconds Array size: 30000 Average sorting time: 82 milliseconds Number of tests: 1000 Performance: 2.7333333333333334 O(N) nanoseconds Performance: 0.18378222850546175 O(N*Log2(N)) nanoseconds Performance: 9.11111111111111E-5 O(N*N) nanoseconds
The performance of this implementation is definitely better than the insertion sort and the selection sort. The numbers tell us that it's between O(N*Log2(N) and O(N*N).
But this implementation is still not good as the JDK implementation java.util.Arras.sort(), which gives about constant performance of 0.157 O(N*Log2(N)).
Last update: 2011.
Table of Contents
Introduction of Sorting Algorithms
Java API for Sorting Algorithms
Insertion Sort Algorithm and Implementation
Selection Sort Algorithm and Implementation
Bubble Sort Algorithm and Implementation
►Quicksort Algorithm and Implementation
Quicksort - Algorithm Introduction
Quicksort - Java Implementation
Quicksort - Implementation Improvements
Merge Sort Algorithm and Implementation
Heap Sort Algorithm and Implementation
Shell Sort Algorithm and Implementation