**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