QuickSort

From Real Software Documentation

Aim

In this lesson, we learn about the Quicksort, one of the fastest general-purpose sorting algorithms known. We will learn how it works, code it up in Real Studio, and then compare it to the other sorting algorithms we’ve developed.

How the Quicksort works

We begin by shuffling the first element of the list into its final place, in the same process making the elements on either side all lower (on the left) and higher (on the right). We start by comparing the first element with the element next to it, and the element at the end of the list:

We move x to the right and y to the left, until x points at an element greater than 5 and y points at an element less than 5. Then we swap the elements x and y are pointing to:

Repeat this process, moving x and y toward each other as we go:

This process continues until x y. Then switch the first element (5) with the element in the position before x:

What have we done?

5 is now in its final place, and the sub-lists on either side of 5 are all lower than 5 (to its left) or greater than 5 (to its right):

You should be able to see now that we can just recursively employ the same process to sort the two smaller lists.

The Project

Open the project 16_QuickSort. Open SortWindow in its Window Editor, double-click on the Quicksort button, put a breakpoint at the end of the Action event handler, and trace through the algorithm for a bit.

1. Run the old sort button for an interesting range: perhaps 500 to 1000 in steps of 100.
   On the author’s computer, the Quicksort algorithm is about 40 times faster than the insertion sort…
   
2. Now try it again for some much shorter numbers. Quicksort might even be noticeably slower for some shorter lists.
   

Further Exercises

The algorithm can be made faster. The Quicksort algorithm is quite inefficient for shorter lists. What would work better would be to switch to another algorithm such as insertion sort for shorter lists. Notice that a large list will eventually be reduced to many very short lists toward the end of the process, so sorting these short lists more quickly will produce a significant speed-up.

A great exercise would be to produce a program that can work out at what size of lists the algorithm should switch to a different sorting algorithm. This would be a program that timed sorting a big array repeatedly, increasing the size of list that is sorted by insertion, until the time stopped getting shorter.