Question

Task 1 (40 pts). Implement the Quick Sort algorithm as discussed in Lecture 4. (Hint: use the function checked_sorted to check if your output is indeed sorted.) • Task 2 (40 pts). Implement the Counting Sort algorithm as discussed in Lecture 4. (Hint: use the function checked sorted to check if your output is indeed sorted.)package sorting;

import java.util.*;

public class Sort3 {
public static int[] quick_sort (int[] array, int p, int r) {

}

public static int partition (int[] array, int p, int r) {

}

public static int[] counting_sort (int[] array, int k) {

}


public static int[] generate_random_array (int n, int k) {
List list;
int[] array;
Random rnd;

rnd = new Random(System.currentTimeMillis());

list = new ArrayList ();
for (int i = 1; i <= n; i++)
list.add(new Integer(rnd.nextInt(k+1)));

Collections.shuffle(list, rnd);

array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();

return array;
}

public static int[] generate_random_array (int n) {
List list;
int[] array;

list = new ArrayList ();
for (int i = 1; i <= n; i++)
list.add(new Integer(i));

Collections.shuffle(list, new Random(System.currentTimeMillis()));

array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();

return array;
}

/*
* Input: an integer array
* Output: true if the array is acsendingly sorted, otherwise return false
*/
public static boolean check_sorted (int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i-1] > array[i])
return false;
}
return true;
}

public static void print_array (int[] array) {
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + ", ");
System.out.println();
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int k = 10000;

System.out.println("Quick sort starts ------------------");
for (int n = 100000; n <= 1000000; n=n+100000) {
int[] array = Sort3.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort3.quick_sort(array, 0, n-1);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort3.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Quick sort ends ------------------");

System.out.println("Counting sort starts ------------------");
for (int n = 100000; n <= 1000000; n=n+100000) {
int[] array = Sort3.generate_random_array(n, k);
long t1 = System.currentTimeMillis();
array = Sort3.counting_sort(array, k);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort3.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Counting sort ends ------------------");
}
}

Answer 1

Check the explanation

Step-by-step explanation:

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Random;

public class Sort2 {

public static int leftside(int i) {

return 2*i + 1;

}

public static int rightside(int i) {

return 2*i + 2;

}

public static int parentside(int i) {

return i/2;

}

public static int[] maximum_heapify(int[] arrayvalue, int sizeheap, int i1) {

int large = i1;

int l1 = leftside(i1);

int r1 = rightside(i1);

if (l1 < sizeheap && arrayvalue[l1] > arrayvalue[large])

large = l1;

if (r1 < sizeheap && arrayvalue[r1] > arrayvalue[large])

large = r1;

if (large != i1)

{

int swapelement = arrayvalue[i1];

arrayvalue[i1] = arrayvalue[large];

arrayvalue[large] = swapelement;

maximum_heapify(arrayvalue, sizeheap, large);

}

return arrayvalue;

}

public static int[] build_heap(int[] arrayvalue) {

int n1 = arrayvalue.length;

for (int i = n1 / 2 - 1; i >= 0; i--)

maximum_heapify(arrayvalue, n1, i);

return arrayvalue;

}

public static int[] heap_sort(int[] arrayvalue) {

arrayvalue = build_heap(arrayvalue);

int n1 = arrayvalue.length;

for (int i=n1-1; i>=0; i--)

{

int tempvalval = arrayvalue[0];

arrayvalue[0] = arrayvalue[i];

arrayvalue[i] = tempvalval;

maximum_heapify(arrayvalue, i, 0);

}

return arrayvalue;

}

public static int[] quick_sort(int[] arrayvalue, int p1, int r1) {

if (p1 < r1)

{

int pival = partition(arrayvalue, p1, r1);

quick_sort(arrayvalue, p1, pival-1);

quick_sort(arrayvalue, pival+1, r1);

}

return arrayvalue;

}

public static int partition(int[] arrayvalue, int p1, int r1) {

int pivotelement = arrayvalue[r1];

int i1 = (p1-1);

for (int j1=p1; j1<r1; j1++)

{

if (arrayvalue[j1] <= pivotelement)

{

i1++;

int tempvalval = arrayvalue[i1];

arrayvalue[i1] = arrayvalue[j1];

arrayvalue[j1] = tempvalval;

}

}

int tempvalval = arrayvalue[i1+1];

arrayvalue[i1+1] = arrayvalue[r1];

arrayvalue[r1] = tempvalval;

return i1+1;

}

public static int[] countvalsort(int[] arrayvalue, int k1) {

int n1 = arrayvalue.length;

int outputval[] = new int[n1];

int countval[] = new int[k1+1];

for (int i=0; i<k1+1; ++i)

countval[i] = 0;

for (int i=0; i<n1; ++i)

++countval[arrayvalue[i]];

for (int i=1; i<=k1; ++i)

countval[i] += countval[i-1];

for (int i = 0; i<n1; ++i)

{

outputval[countval[arrayvalue[i]]-1] = arrayvalue[i];

--countval[arrayvalue[i]];

}

for (int i = 0; i<n1; ++i)

arrayvalue[i] = outputval[i];

return arrayvalue;

}

public static int[] generate_random_arrayvalue(int n, int k) {

List<Integer> list;

int[] arrayvalue;

Random rnd;

rnd = new Random(System.currentTimeMillis());

list = new ArrayList<Integer>();

for (int i = 1; i <= n; i++)

list.add(new Integer(rnd.nextInt(k + 1)));

Collections.shuffle(list, rnd);

arrayvalue = new int[n];

for (int i = 0; i < n; i++)

arrayvalue[i] = list.get(i).intValue();

return arrayvalue;

}

public static int[] generate_random_arrayvalue(int n) {

List<Integer> list;

int[] arrayvalue;

list = new ArrayList<Integer>();

for (int i = 1; i <= n; i++)

list.add(new Integer(i));

Collections.shuffle(list, new Random(System.currentTimeMillis()));

arrayvalue = new int[n];

for (int i = 0; i < n; i++)

arrayvalue[i] = list.get(i).intValue();

return arrayvalue;

}

public static boolean check_sorted(int[] arrayvalue) {

for (int i = 1; i < arrayvalue.length; i++) {

if (arrayvalue[i - 1] > arrayvalue[i])

return false;

}

return true;

}

public static void print_arrayvalue(int[] arrayvalue) {

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

System.out.print(arrayvalue[i] + ", ");

System.out.println();

}

public static void main(String[] args) {

int k = 100;

System.out.println("Heap sort starts ------------------");

for (int n = 10; n <= 100000; n = n * 2) {

int[] arrayvalue = Sort2.generate_random_arrayvalue(n);

long t1 = System.currentTimeMillis();

arrayvalue = Sort2.heap_sort(arrayvalue);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

boolean flag = Sort2.check_sorted(arrayvalue);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("Heap sort ends ------------------");

System.out.println("Quick sort starts ------------------");

for (int n = 10; n <= 100000; n = n * 2) {

int[] arrayvalue = Sort2.generate_random_arrayvalue(n);

long t1 = System.currentTimeMillis();

arrayvalue = Sort2.quick_sort(arrayvalue, 0, n - 1);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

boolean flag = Sort2.check_sorted(arrayvalue);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("Quick sort ends ------------------");

System.out.println("countvaling sort starts ------------------");

for (int n = 10; n <= 100000; n = n * 2) {

int[] arrayvalue = Sort2.generate_random_arrayvalue(n, k);

long t1 = System.currentTimeMillis();

arrayvalue = Sort2.countvalsort(arrayvalue, k);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

boolean flag = Sort2.check_sorted(arrayvalue);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("countvaling sort ends ------------------");

}

}