Advanced Sorts

From

Current revision as of 18:54, 9 April 2009

We will consider 4 advanced sorting algorithms: Merge Sort, Shell’s Sort, Heap Sort, and Quick Sort.

Merge Sort

The basis Merge Sort algorithm is to divide the array in half. Sort each half separately, and merge the two halves back into one array. Does this actually work? Consider using a basic bubble sort on an array of 1,000 items (a really dumb idea!). Basic Bubble Sort takes N² – 2N + 1 comparisons. When N is 1,000, this is 998,001 comparisons. If the array is divided into two arrays of 500, each array would take 249,001 comparison and it would take 1,000 (i.e. N ) steps to perform the merge. Thus, a total of 2 × 249,001 + 1,000 steps are required, and this is a total of 499,002 steps versus 998,001 steps.

The next question is, “Is Bubble Sort a good choice to use for sorting each side?” Why not just use Merge Sort? So now we have a recursive sorting algorithm.

If the array has size 1 then 
	it is sorted 
else 
	Divide the array in half 
	Merge Sort each half 
	Merge the two halves.

Analyzing the run-time performance of a recursive algorithm requires the use of a mathematical technique called a recurrence relation. If we apply this technique to the Merge Sort algorithm, we find that it is O( N log N ). This is better than the simple sorts, which were O( N² ).

The mathematical analysis, however, hides certain details about Merge Sort. First, the recursion takes time because of the overhead of making recursive calls. Part of this overhead is the creation of many activation records, since each recursive call to a method required a new activation record be pushed onto the run-time stack. Secondly, the merge process requires the use of a temporary array, so Merge Sort has a high memory requirement. Remember the trade-off between time and space? To make something use less time often requires using more space.

Shell’s Sort

This sort, sometimes called Shell Sort, was developed by Donald Shell and published in 1959 (CACM). This sort is an extension of Insertion Sort. It uses the idea that Insertion Sort runs quickly given two conditions: (1) The array being sorted is small, and (2) the array being sorted is almost in order.

The basic algorithm for Shell’s Sort is the following:

Divide the array to be sorted into n subarrays, 
where the distance (or the stride) between the elements of the subarrays is n.

Use Insertion Sort to sort each subarray.

Choose a smaller value for n and repeat this process

Example: 81, 94, 11, 96, 12, 35, 17, 95, 28, 54, 41, 75, 15 with a stride of 3.

The sequence of value used for n is called the increment sequence and the performance of Shell’s Sort is very dependent upon the increment sequence. There are three rules that the increment sequence must follow. Let I¹, I², …, I^k be the increment sequence.

The original sequence proposed by Shell is

(...need to use the math editor here...)

However, we can generate a particular set of values and show that this sequence can take O( N² ) time. That is, a problem with Shell’s original sequence is that, while it is easy to implement, there are too many overlaps.

A better sequence was proposed by T. H. Hibbard in 1963, where

I_k = 2^k – 1, for k = 1, 2, 3, …

This gives the sequence: 1, 3, 7, 15, 31, ….

Another increment sequence was given by Donald Knuth. His sequence has the form

I_k = ½( 3^k + 1 ), for k = 1, 2, 3, ….

This gives the sequence: 1, 2, 5, 14, 41, 122, 365, 1094, …

In practice, however, the best increment sequence seems to be one given by Robert Sedgewick. In his sequence, increments have one of two forms:

I_k = either 9 × 4^k - 9×2^k + 1 or 4^k - 3×2^k + 1

This gives the sequence: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, ….

Using Sedgewick’s sequence, it has been shown that the average running time for Shell’s Sort is O( N^7/6 ).

Heap Sort

We have already seen what is a heap data structure. Heap Sort is an extension of Selection Sort. However, in place of running a method to find the minimum or maximum value in the unsorted area of the array, we “heapify” the unsorted area and then remove the minimum or maximum value—depending on whether it is a min-heap or a max-heap—and swap this value with the next open slot in the sorted portion of the array. Since we can embed a binary tree in an array, heap sort can be implemented using an array. And, if the array is of size N, Heap Sort can be shown to have an upper bound of O( N log N ).

While Heap Sort is not the fastest of the advanced sorts, it does have some good points. First, Heap Sort is very space efficient. That is, an array can be sorted in place with only one extra array slot needed: this is the temporary space needed as part of a swap routine. Secondly, as is the case with Selection Sort, Heap Sort does not have a best or worst case. It takes about the same time regardless of the initial order of the array.

Quick Sort

We now look at what is generally considered the fastest of the advanced sorts: Quick Sort, published by C. A. R. Hoare in 1962. It, like Merge Sort, is an example of a Divide-And- Conquer algorithm. Unlike Merge Sort—which divides the array in half, sorts each half, and then merges the results—Quick Sort basically merges the results first and then sorts each side.

Partitioning

Quick Sort first partitions an array by choosing a value called the pivot. The partition component of the sorting algorithm locates the pivot in it proper location in the array. That is, in the position it should be in when the array is correctly sorted. In the process of finding the correct location of the pivot, however, the partition procedure also rearranges the elements of the array to be on the correct side of the pivot. This means that values that are smaller than the pivot are moved to positions before the pivot, while values that are greater than the pivot are moved to positions after the pivot. While these values are not necessarily moved to their correct places in sorted order, they are at least on the correct side of the pivot. Therefore, when the left and right sides—with respect to the pivot—of the array are sorted, the entire array is sorted.

How the pivot is chosen, is the most crucial component of the Quick Sort algorithm. If the pivot consistently divides the array almost in half, then Quick Sort lives up to its name. However, if the pivot consistently divides the array so that one side is empty — that is, the pivot is an end point of the array—then Quick Sort becomes an O( N² ) algorithm and is not much better than Bubble Sort.

There are several ways to choose the pivot. Among them are: choose the value on the left edge of the array, choose the value on the right edge of the array, choose the value in the middle of the array, or choose a value at random. Perhaps one of the best methods of choosing the pivot, however, is called the median-of-three algorithm. This algorithm, along with the partition algorithm, will be demonstrated with the following example.

(..need picture here..)

8 1 4 9 6 3 5 2 7 0

0 1 2 3 4 5 6 7 8 9

The median-of-three algorithm will compare three values. In this example the three values are 8 (location 0), 6 (location 4), and 0 (location 9). Sorting these three values into the proper order, the array now becomes.

(..need picture here..)

0 1 4 9 6 3 5 2 7 8

0 1 2 3 4 5 6 7 8 9

And 6 is the pivot. Next, we “hide” the pivot, swapping it with the next to last value in the array. Note, we already know that the last value is larger than the pivot, so we do not swap the pivot with that value. The array now is.

(..need picture here..)

0 1 4 9 7 3 5 2 0 8

0 1 2 3 4 5 6 7 8 9

Now, we start a pointer, i, and a pointer, j, from opposite ends of the array and allow the pointers to move towards each other. When the pointer i finds a value that is larger than the pivot, it stops, and when pointer j finds a value that is smaller than the pivot, it stops. When both pointers have stopped and if they have not crossed, the two values pointed to by i and j are swapped. This pattern is continued until the two pointers cross. Then, the value pointed to by i is the proper location for the pivot value, so it is swapped with the “hidden” pivot. This ends the partition procedure. In the example, the array at the end of the partition procedure looks like

(..need picture here..)

0 1 4 2 5 3 6 9 7 8

0 1 2 3 4 5 6 7 8 9

Basic Quick Sort Algorithm

1. Partition the array.
2. Quick Sort the left side of the array.
3. Quick Sort the right side of the array.

Variations
Some of the variations on the algorithm involve the use of a cutoff value. This value generally ranges between 10 and 30.

1. When the size of an array gets smaller than the cutoff value, do not Quick Sort the array, rather use a simple sort.
2. When the size of an array get smaller than a cutoff value, leave the array unsorted. When the Quick Sort algorithm has finished, the entire array is processed by Insertion Sort.

At its best, when the pivot consistently splits the array in half, Quick Sort is O( N log N ).