Answer:
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 ------------------");
}
}