package sorting; import java.util.*; public class Sort2 { public static int left
ID: 3870314 • Letter: P
Question
package sorting;
import java.util.*;
public class Sort2 {
public static int left (int i) {
/*
* fill in your program
*/
}
public static int right (int i) {
/*
* fill in your program
*/
}
public static int parent (int i) {
/*
* fill in your program
*/
}
public static int[] max_heapify (int[] array, int heap_size, int i) {
/*
* fill in your program
*/
}
public static int[] build_heap (int[] array) {
/*
* fill in your program
*/
}
public static int[] heap_sort (int[] array) {
/*
* fill in your program
*/
}
public static int[] quick_sort (int[] array, int p, int r) {
/*
* fill in your program
*/
}
public static int partition (int[] array, int p, int r) {
/*
* fill in your program
*/
}
/*
* the values in array range from 0 to k
*/
public static int[] counting_sort (int[] array, int k) {
/*
* fill in your program
*/
}
/*
* n: the size of the output array
* k: the maximum value in the array
*/
public static int[] generate_random_array (int n, int k) {
List<Integer> list;
int[] array;
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);
array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();
return array;
}
/*
* n: the size of the output array
*/
public static int[] generate_random_array (int n) {
List<Integer> list;
int[] array;
list = new ArrayList<Integer> ();
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 = 100;
System.out.println("Heap sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort2.heap_sort(array);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
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[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort2.quick_sort(array, 0, n-1);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Quick sort ends ------------------");
System.out.println("Counting sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort2.generate_random_array(n, k);
long t1 = System.currentTimeMillis();
array = Sort2.counting_sort(array, k);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Counting sort ends ------------------");
}
}
. Task 1 (30 pts). Implement the Heap Sort algorithm as discussed in Lec- ture 3. (Hint: use the function checked sorted to check if your output is indeed sorted.) ·Task 2 (30 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 (30 pts). Implement the Counting Sort algorithm as discussed in Lecture 4. (Hint: use the function checkedsorted to check if your output is indeed sorted.) ·Task 4 (10 pts). Generate a report to discuss the time performance of the three algorithms. Compare it with their theoretical time complexity as discussed in the lecture. Plots and figures are encouraged to help draw the conclusion.Explanation / Answer
package sorting;
import java.util.*;
public class Sort2 {
private static int[] a;
private static int n;
private static int left;
private static int right;
private static int largest;
public static int left (int i) {
/*
* fill in your program
*/
}
public static int right (int i) {
/*
* fill in your program
*/
}
public static int parent (int i) {
/*
* fill in your program
*/
}
public static int[] max_heapify (int[] array, int i) {
left = 2 * i;
right = 2 * i + 1;
if (left <= n && array[left] > array[i])
{
largest = left;
} else
{
largest = i;
}
if (right <= n && array[right] > array[largest])
{
largest = right;
}
if (largest != i)
{
exchange(i, largest);
max_heapify(a, largest);
}
}
public static int[] build_heap (int[] array) {
n = array.length - 1;
for (int i = n / 2; i >= 0; i--)
{
max_heapify(a, i);
}
}
public static void exchange(int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static int[] heap_sort (int[] array) {
a = array;
build_heap(a);
for (int i = n; i > 0; i--)
{
exchange(0, i);
n = n - 1;
max_heapify(a, 0);
}
}
public static int[] quick_sort (int[] array, int p, int r) {
if (p < r)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(array, p, r);
// Recursively quick_sort elements before
// partition and after partition
quick_sort(array, p, pi-1);
quick_sort(array, pi+1, r);
}
}
public static int partition (int arr[], int low, int high) {
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/*
* the values in array range from 0 to k
*/
public static int[] counting_sort (int[] array, int k) {
int N = array.length;
if (N == 0)
return;
/** find max and min values **/
int max = array[0], min = array[0];
for (int i = 1; i < N; i++)
{
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
int range = max - min + 1;
/** check if range is small enough for count array **/
/** else it might give out of memory exception while allocating memory for array **/
if (range > MAX_RANGE)
{
System.out.println(" Error : Range too large for sort");
return;
}
int[] count = new int[range];
/** make count/frequency array for each element **/
for (int i = 0; i < N; i++)
count[arrayi] - min]++;
/** modify count so that positions in final array is obtained **/
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
/** modify original array **/
int j = 0;
for (int i = 0; i < range; i++)
while (j < count[i])
array[j++] = i + min;
}
/*
* n: the size of the output array
* k: the maximum value in the array
*/
public static int[] generate_random_array (int n, int k) {
List<Integer> list;
int[] array;
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);
array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();
return array;
}
/*
* n: the size of the output array
*/
public static int[] generate_random_array (int n) {
List<Integer> list;
int[] array;
list = new ArrayList<Integer> ();
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 = 100;
System.out.println("Heap sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort2.heap_sort(array);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
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[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort2.quick_sort(array, 0, n-1);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Quick sort ends ------------------");
System.out.println("Counting sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort2.generate_random_array(n, k);
long t1 = System.currentTimeMillis();
array = Sort2.counting_sort(array, k);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Counting sort ends ------------------");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.