SORTING - Introduction to Java Programming: Comprehensive Version - page 892

Comparator<? super E> comparator)
public static <E> boolean ordered(E[] list,
Comparator<? super E> comparator, boolean ascending)

Section 23.6
23.7 ( Min-heap ) The heap presented in the text is also known as a max-heap , in which

each node is greater than or equal to any of its children. A min-heap is a heap
in which each node is less than or equal to any of its children. Min-heaps are
often used to implement priority queues. Revise the Heap class in Listing 23.9 to
implement a min-heap.

max-heap
min-heap

*23.8

( Sort using a heap ) Implement the following sort method using a heap.

public static <E extends Comparable<E>> void sort(E[] list)

*23.9

( Generic Heap using Comparator ) Revise Heap in Listing 23.9, using a generic
parameter and a Comparator for comparing objects. Define a new constructor
with a Comparator as its argument as follows:

Heap(Comparator<? super E> comparator)
**23.10 ( Heap visualization ) Write a program that displays a heap graphically, as shown
in Figure 23.10. The program lets you insert and delete an element from the heap.
23.11 ( Heap clone and equals ) Implement the clone and equals method in the
Heap class.
Section 23.7
*23.12

( Radix sort ) Write a program that randomly generates 1,000,000 integers and
sorts them using radix sort.

*23.13

( Execution time for sorting ) Write a program that obtains the execution time of
selection sort, bubble sort, merge sort, quick sort, heap sort, and radix sort for
input size 50,000, 100,000, 150,000, 200,000, 250,000, and 300,000. Your pro-
gram should create data randomly and print a table like this:

Array
size

Selection
Sort

Bubble
Sort

Merge
Sort

Quick
Sort

Heap
Sort

Radix
Sort

50,000
100,000
150,000
200,000
250,000
300,000

( Hint : You can use the following code template to obtain the execution time.)

long startTime = System.currentTimeMillis();
perform the task;
long endTime = System.currentTimeMillis();
long executionTime = endTime - startTime;

The text gives a recursive quick sort. Write a nonrecursive version in this exercise.