HEAPSORT



Java ORGANIZATION

Follow the following steps to learn the organization of the programs in the textbook.

1. Down load the sources using ftp from textbook. You are able to download from my net too at

2. Unzip the file you will have the directory adspjava. Within this directory, there is another directory named Code.

3. Double click to open Code you will see the organizations of the programs:

DataSructures

Exeptions

Supporting

Chapter08

4. Double click to open Chapter08. You will see a class named TestSort.java.

5. Copy this source code into its parent directory so that TestSort will recognize the three other directories: DataSructures, Exeptions, and Supporting.

6. Open the file TestSort.java (the one of the same level with the directory DataStructures. Here is the class:

import DataStructures.*;

import Supporting.*;

// Test all the sorting routines in package DataStructures

public class TestSort

{

private static final int NUM_ITEMS = 1000;

private static int theSeed = 1;

public static void checkSort( MyInteger [ ] a )

{

for( int i = 0; i < a.length; i++ )

if( a[ i ].intValue( ) != i )

System.out.println( "Error at " + i );

System.out.println( "Finished checksort" );

}

public static void main( String [ ] args )

{

MyInteger [ ] a = new MyInteger[ NUM_ITEMS ];

for( int i = 0; i < a.length; i++ )

a[ i ] = new MyInteger( i );

for( theSeed = 0; theSeed < 5; theSeed++ )

{

Random.permute( a );

Sort.insertionSort( a );

checkSort( a );

Random.permute( a );

Sort.heapsort( a );

checkSort( a );

Random.permute( a );

Sort.shellsort( a );

checkSort( a );

Random.permute( a );

Sort.mergeSort( a );

checkSort( a );

Random.permute( a );

Sort.quicksort( a );

checkSort( a );

Random.permute( a );

Sort.quickSelect( a, NUM_ITEMS / 2 );

System.out.println( a[ NUM_ITEMS / 2 - 1 ].intValue( ) + " is " +

NUM_ITEMS / 2 +"th smallest" );

}

}

}

7. Analyze the TestSort.java

a. It imports two packages: DataStructures.* and Supporting.*;

b. In the beginning, it declares two variables:

i. int NUM_ITEMS = 1000;

ii. int theSeed = 1;

The first variable for the length of the array to be sorted and the second is used for the loop to indicate the number of testing. We modify 1000 to be 10 and remove theSeed.

c. In the main program, the array is defined by MyInteger, a class in the package Supporting. It is int in a convenient way. Then the array is a[i] initialized by integer I for i=0 to length-1. In other words we have the sequence 0,1,2,…, Here is the code:

MyInteger [ ] a = new MyInteger[ NUM_ITEMS ];

for( int i = 0; i < a.length; i++ )

a[ i ] = new MyInteger( i );

d. Witihin the for (theSeed) we have 6 blocks for 6 different tests on different sorts. We remove them all and keep only heapSort. We also remove the routine checkSort and replace it by printArray, which is used to print the array before and after sort. Therefore we have the following complete code:

import DataStructures.*;

import Supporting.*;

// Test all the sorting routines in package DataStructures

public class TestSort

{

private static final int NUM_ITEMS = 1000;

public static void print( MyInteger [ ] a )

{

for( int i = 0; i < a.length; i++ ) System.out.print( i: a[ i ] + “|”);

}

public static void main( String [ ] args )

{

MyInteger [ ] a = new MyInteger[ NUM_ITEMS ];

for( int i = 0; i < a.length; i++ )

a[ i ] = new MyInteger( i );

Random.permute( a ); printArray(a);

Sort.heapsort( a ); printArray(a);

}

}

e. Compile and run the program, then inspect the out put.

f. The heapsort is using maxheap to sort.

8. Move our code of min-heapsort into the packages.

We also have our program to do the heapsort but we use the minimum order heap property instead of the maximum heap-order property. Can we migrate our program into the textbook packages?

- Look at our program below and find a way to incorporate to the textbook packages.

- As soon as you are successful to merge the code into the textbooks packages, you will understand the book organization.

- Good luck to you.

public class TestSort

{

private static final int NUM_ITEMS = 10;

// to print out the array of integers

public static void print( int [ ] a )

{

for( int i = 0; i < a.length; i++ )

System.out.print( i+":"+a[i]+ " | " );

}

public static void main( String [ ] args )

{

//get array and print it out

int [ ] a = new int[ NUM_ITEMS];

a[ 0 ] = 0;

for( int i = 1; i < a.length; i++ ) a [ i ] = i;

System.out.print(“\nOriginal array”); print (a);

//Sort the array and print it out

Sort.heapsort2( a ); print (a);

System.out.print(“\nSorted array”); print (a);

}

}

class Sort

{

public static void heapsort2( int [ ] a )

{

for( int i = (a.length-1) / 2; i > 0; i-- ) /* buildHeap */

{

percDown2( a, i, a.length-1 );

System.out.print("\nPercDown at "+i+":");TestSort.print (a);

}

for( int i = a.length-1; i > 0; i-- ) /*sorting*/

{

swapReferences( a, 1, i ); /* exchange */

percDown2( a, 1, i-1);

System.out.print("\nPercDown3 at "+i+":"); TestSort.print (a);

}

}

private static void percDown2( int [ ] a, int i, int n )

{

int child;

int tmp=a[i];

for( ; i *2 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download