Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 278

We note, in passing, that our code would be more flexible if the increments are stored in an array ( incr , say)
and hsort is called with each element of the array in turn. For example, suppose incr[0] contains the number of
increments ( m , say), and incr[1] to incr[m] contain the increments in decreasing order with incr[m] = 1 . We could
call hsort with each increment as follows:

for (int i = 1; i <= incr[0]; i++) hsort(num, n, incr[i]);

One question that arises is how do we decide which increments to use for a given n ? Many methods have been
proposed; the following gives reasonable results:

let h 1 = 1
generate h s+1 = 3h s + 1, for s = 1, 2, 3,...
stop when h t+2 ³ n; use h 1 to h t as the increments for the sort

In other words, we generate terms of the sequence until a term is greater than or equal to n . Discard the last two
and use the others as the increments for the sort.
For example, if n = 100, we generate h 1 = 1, h 2 = 4, h 3 = 13, h 4 = 40, h 5 = 121. Since h 5 > 100, we use h 1 , h 2 , and h 3 as
the increments to sort 100 items.
The performance of Shell sort lies somewhere between the simple O( n 2 ) methods (insertion, selection) and
the O( n log 2 n ) methods (heapsort, quicksort, mergesort). Its order is approximately O( n 1.3 ) for n in a practical range
tending to O( n (log 2 n ) 2 ) as n tends to infinity.
As an exercise, write a program to sort a list using Shell sort, counting the number of comparisons and
assignments made in sorting the list.

eXerCISeS 9

1. Write a program to compare the performance of the sorting methods discussed in this

chapter with respect to “number of comparisons” and “number of assignments”. For
quicksort, compare the performance of choosing the first element as the pivot with choosing
a random element.

run the program to (i) sort 10, 100, 1000, 10000 and 100000 elements supplied in random
order and (ii) sort 10, 100, 1000, 10000 and 100000 elements that are already sorted.

2. a function makeHeap is passed an integer array A . if A[0] contains n , then A[1] to A[n]

contain numbers in arbitrary order. Write makeHeap such that A[1] to A[n] contain a
max-heap ( largest value at the root). Your function must create the heap by processing the
elements in the order A[2] , A[3] ,..., A[n] .

3. a heap is stored in a one-dimensional integer array num[1..n] with the largest value in

position 1. give an efficient algorithm that deletes the root and rearranges the other elements
so that the heap now occupies num[1] to num[n-1] .

4. a heap is stored in a one-dimensional integer array A[0..max] with the largest value in

position 1. A[0] specifies the number of elements in the heap at any time. Write a function
to add a new value v to the heap. Your function should work if the heap is initially empty and
should print a message if there is no room to store v .