Insertion and Heap Sort

1 Practice Programming: Recursive Methods in Java

• Write a recursive Java method power(double x,int n) that returns the values of xn. For example, power(2,3) must have the value 8, assuming that n > 0.
• Write a recursive Java method count(int d,int n) that will count the occurrences of the digit d in the number n. For example, count(3,23533) will have the value 3.
• Write a recursive Java method sumDigits(int n) that returns the sum of the digits in the number n. For example, sumDigits(2345) is 14.

2 Sorting Algorithms Implementation

2.1 Introduction

In this programming question, n integers ranging from 0 to n-1 are stored randomly in A, an array of size n. In the class Sort.java, you are supposed to implement the following two sorting algorithms: Insertion-sort and Heap-sort. You have to work directly on the given starter code.

2.2 What to do

Download the starter code from the course web site. Read the starter code and make sure you understand how it works before attempting to modify it. In the given class Sort.java, Selectionsort is already implemented and is used to sort an array of numbers from 0 to 9.

Initially, the array is: 0

1 2 3 4 5 6 7 8 9

After randomization, the array becomes: 8

2 0 1 9 5 4 3 6 7

SELECTION SORT...

The array is now sorted:

0 1 2 3 4 5 6 7 8 9

Implement Insertion-sort and Heap-sort in the Sort class.

Write a driver class Driver0.java, where an array of random integers are taken, and then heapsort is called to sort them. Temporally! revise your implementation of heapsort so

• it will print out intermediate steps in constructing the heap and sorting the heap/array;

Now if the lecture example is given to Driver0.java, the following would be printed out:

Initially, the array is: 4
1 3 2 16 9 10 14 8 7
BUILDING A HEAP...
max heapify on element with array index: 4
4 1 3 2 16 9 10 14 8 7
max heapify on element with array index: 3
4 1 3 14 16 9 10 2 8 7 max heapify on
element with array index: 2
4 1 10 14 16 9 3 2 8 7 max heapify on
element with array index: 1
4 16 10 14 7 9 3 2 8 1 max heapify on
element with array index: 0 16 14 10 8 7 9
3 2 4 1
Program written by Your Name/012345678, about to sort the array!
HEAP-SORT...
heap-sort working on element with array index: 9
14 8 10 4 7 9 3 2 1 16
heap-sort working on element with array index: 8
10 8 9 4 7 1 3 2 14 16
heap-sort working on element with array index: 7
9 8 3 4 7 1 2 10 14 16
heap-sort working on element with array index: 6
8 7 3 4 2 1 9 10 14 16
heap-sort working on element with array index: 5
7 4 3 1 2 8 9 10 14 16
heap-sort working on element with array index: 4
4 2 3 1 7 8 9 10 14 16
heap-sort working on element with array index: 3
3 2 1 4 7 8 9 10 14 16
heap-sort working on element with array index: 2
2 1 3 4 7 8 9 10 14 16
heap-sort working on element with array index: 1
1 2 3 4 7 8 9 10 14 16

Remove those program lines printing out these intermediate steps as above.

Run Solver.java, where 20 array instances of 1M random integers are sorted (using Insertionsort and Heap-sort, respectively). Solver.java is given, however the two sorting algorithms of course are implemented by yourself.

Starter Codes

Solver.java

public class Solver {
public static void main(String[] args) {
final int SIZE = 1000000; // 1 million
final int Instances=20;
int[][] TwoDimArray = new int[Instances][SIZE];

Sort s = new Sort();

for(int i=0; i s.initializeArray(TwoDimArray[i], SIZE);
s.randomizeArray(TwoDimArray[i], SIZE);
}



final long startTime = System.nanoTime();
for(int i=0; i s.insertionSort(TwoDimArray[i], SIZE);
//s.heapSort(TwoDimArray[i], SIZE);
}

final long duration = (System.nanoTime() - startTime)/ 1000000;
System.out.println("Duration in seconds:" + (duration/1000.0));

}
}

Sort.java

import java.util.Random;

public class Sort {

// swap the ith element with the jth elements.
private void swap(int[] a, int i, int j){
int temp;
temp = a[i]; a[i] = a[j]; a[j] = temp;
}

// initialize the array a with elements from 0 to size-1.
public void initializeArray(int[] a, int size){
for (int i=0; i a[i]=i;
}
}

// display the elements in the array a, rowSize elements per row.
public void displayArray(int[] a, int size){
int rowSize=100;
for (int i=0; i if(i%rowSize==0){
System.out.println();
}
System.out.print(a[i]+ " ");
}
System.out.println();
}

// randomly swap two elements in a for SWAPTIMES times.
public void randomizeArray(int[] a, int size){
final int SWAPTIMES = 10000;
Random r = new Random();
int j, k;
for(int i=0; i< SWAPTIMES; i++){
j = r.nextInt(size);
k = r.nextInt(size);
this.swap(a, j, k);
}
}


// selectionSort
public void selectionSort(int a[], int size){
int i, j, min, minIndex;
for (j=0; j minIndex=j; min = a[j];
for (i=j+1; i if(a[i] < min ){minIndex=i; min = a[i];}
}
this.swap(a, j, minIndex);
}
}

}

Starter.java

public class Starter{
public static void main(String[] args) {
final int SIZE = 10;
int[] array = new int[SIZE];

Sort s = new Sort();

s.initializeArray(array, SIZE);
System.out.print("Initially, the array is:");
s.displayArray(array, SIZE);

System.out.println();
System.out.print("After randomization, the array becomes:");

s.randomizeArray(array, SIZE);
s.displayArray(array, SIZE);
System.out.println("nSELECTION SORT...n");
System.out.print("The array is now sorted:");

s.selectionSort(array, SIZE);
s.displayArray(array, SIZE);


}
}