Implement the following 4 static sorting methods: (a) selectionSort(int[] arr),
ID: 3555784 • Letter: I
Question
Implement the following 4 static sorting methods:
(a) selectionSort(int[] arr), which calls a recursive selectionSort method that calls a recursive selection method.
(b) insertionSort(int[] arr), which calls a recursive insertionSort method that calls a recursive insertion method.
(c) heapSort(int[] arr), which builds heap using the linear algorithm that turns an array into a heap by fixing parent-child orders (not the one that builds a heap by repeated insertion).
(d) quickSort(int[] arr), which randomly chooses the pivot value within the (sub)array to be sorted.
In each of the above methods, keep two counters to record the number of comparisions and assignments executed on array elements.
The main program should repeat the following test 100 (or more) times:
(1) Generate an array of N random integers between 1 and 99 (allow duplicated values). Let N be 50 for initial testing. (2) Make 4 identical copies of the array, and sort them using the 4 methods, respectively.
(3) Accumulate the total numbers of comparisions and assignments. In the testing process, display the input and output of each sorting method to confirm that it works correctly.
At the end, summarize the testing results in a table in which for each method list the average number of comparisions and assignments, and compare them with N*log(N) and N*N for different N values.
Explanation / Answer
// Recursive Selection sort
void selectionSort(int[] array, int startIndex)
{
if ( startIndex >= array.length - 1 )
return;
int minIndex = startIndex;
for ( int index = startIndex + 1; index < array.length; index++ )
{
if (array[index] < array[minIndex] )
minIndex = index;
}
int temp = array[startIndex];
array[startIndex] = array[minIndex];
array[minIndex] = temp;
selectionSort(array, startIndex + 1);
}
public class RecursiveInsertionSort {
static int[] arr = {5, 2, 4, 6, 1, 3};
int maxIndex = arr.length;
public static void main(String[] args) {
print(arr);
new RecursiveInsertionSort().sort(arr.length);
}
private int sort(int maxIndex) {
if (maxIndex <= 1) {
// at this point maxIndex points to the second element in the array.
return maxIndex;
}
maxIndex = sort(maxIndex - 1); // recursive call
int key = arr[maxIndex];
int i = maxIndex - 1;
while ((i >= 0) && (arr[i] > key)) {
arr[i+1] = arr[i];
i--;
}
arr[i+1] = key;
print(arr);
return maxIndex + 1;
}
private static void print(int[] arr) {
System.out.println();
for (int i : arr) {
System.out.print(i + ", ");
}
}
}
public class QuickSort {
public void sortNumbers(int[] list){
Quicksort(list, 0,list.length-1);
}
public void Quicksort(int[] A, int start, int end){
if (start < end){
//we partition the list and get back two lists (lower than pivot, and bigger than pivot)
int middle = Partition(A, start, end);
//we then do a recursive call to sort out lower numbers than pivot
Quicksort(A, start, middle-1);
//and we do same with higher numbers than pivot
Quicksort(A, middle+1, end);
//NOTE: pivot is already in it's place, where he supposed to be (in a sorted list).
}
}
public int Partition (int[] A, int start, int end){
int pivot = A[end]; //we define pivot (the number we will be comparing other numbers to
int lo = start-1; // we define low value index
for (int hi = start; hi < end; hi++){ //we go throug the list, compare other numbers to pivot
if (A[hi] <= pivot){ //if pivot is lower that the current number
lo++; //we increase lo value
//and exchange current lo with hi (so we will have all lower numbers than pivot on one side
int temp = A[lo];
A[lo] = A[hi];
A[hi] = temp;
}
}
int temp = A[lo+1];
A[lo+1] = A[end];
A[end] = temp;
return lo+1; //we return the pivot elements place
}
public static void main(String[] args){
int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
QuickSort qs = new QuickSort();
qs.sortNumbers(list);
for (int i = 0;i<list.length;i++){
System.out.println(list[i]);
}
}
}
public class HeapSort {
private static int heapSize;
public void sortNumbers(int[] A){
HeapSort(A);
}
private void HeapSort(int[] A){
heapSize = A.length; //we need to sort all the list so heapSize == A.length
BuildMaxHeap(A);
for (int i = A.length-1; i>0; i--){
int temp = A[0];
A[0] = A[i];
A[i] = temp;
//reduce the heap size
heapSize--;
//find new biggest
MaxHeapify(A,0);
}
}
private void BuildMaxHeap(int[] A){
for(int i = A.length/2-1;i>=0;i--){
MaxHeapify(A, i);
}
}
private void MaxHeapify(int[] A, int i){
int l = Left(i); //lets find left child of the given index.
int r = Right(i);//lets find right child of the given index.
int max;
if (l < heapSize){
if (A[l] > A[i]){ //if left child is bigger than parent
max = l; //left child becomes maximum
}
else {
max = i; //otherwise parent is maximum
}
}
else { //if this index does not have left child
max = i;
}
if (r < heapSize){
if(A[r] > A[max]){
max = r;
}
}
if (max != i){
int temp = A[i];
A[i] = A[max];
A[max] = temp;
MaxHeapify(A, max);
}
}
private int Left(int i){
return 2 * i;
}
private int Right(int i){
return (2 * i) + 1;
}
/**
* Just for testing purposes.
*/
public static void main(String[] args){
int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
HeapSort hs = new HeapSort();
hs.sortNumbers(list);
for (int i = 0;i<list.length;i++){
System.out.println(list[i]);
}
}
}