Write a program that implements 3 sorting algorithms and times them in real time
ID: 3705458 • Letter: W
Question
Write a program that implements 3 sorting algorithms and times them in real time. First download the driver and include it in your project.
Next write a class Sorter with the following
bubbleSort: This static method takes in an array of integers via a parameter and sorts it based on the bubble sort algorithm. This method also should not return anything.
mergeSort: This static methods takes in an array of integers via a parameter and sorts it based on the quick sort algorithm. This method also should not return anything.
heapSort: This static method takes in an array of integers via a parameter and sorts it based on the heap sort algorithm.
HINT: The way heap sort works is you insert all the values into a heap first, and then you remove them all from the heap.
HINT: You may want to have another static array of integers for the heap and a static integer for the last index.
Driver:
Explanation / Answer
* The java program SortingTester that tests
* the Sorter class static methods bubble sort,
* quicksort and heap sort and print time of sorted
* in ms to console output.
* */
//SortingTester.java
import java.util.*;
public class SortingTester
{
public static void main(String[] args) {
int[] a = makeArray();
long beforeTime = System.currentTimeMillis();
Sorter.bubbleSort(a);
long afterTime = System.currentTimeMillis();
System.out.println("Sorted correctly? "+isSortedCorrectly(a));
System.out.println("It took "+(afterTime-beforeTime)+"ms for bubble sort");
a = makeArray();
beforeTime = System.currentTimeMillis();
Sorter.quickSort(a);
afterTime = System.currentTimeMillis();
System.out.println("Sorted correctly? "+isSortedCorrectly(a));
System.out.println("It took "+(afterTime-beforeTime)+"ms for quick sort");
a = makeArray();
beforeTime = System.currentTimeMillis();
Sorter.heapSort(a);
afterTime = System.currentTimeMillis();
System.out.println("Sorted correctly? "+isSortedCorrectly(a));
System.out.println("It took "+(afterTime-beforeTime)+"ms for heap sort");
}
public static boolean isSortedCorrectly(int[] a)
{
for(int i=0;i<a.length-1;i++)
{
if(a[i]>a[i+1])
return false;
}
return true;
}
public static int[] makeArray()
{
int[] a = new int[10000];//A big ole array
Random r = new Random(100);//fixes the seed at 100
for(int i=0;i<a.length;i++)
{
a[i] = r.nextInt(1000);//Picks a number from 0 to 999
}
return a;
}
}
------------------------------------------------------------------------
//Sorter.java
public class Sorter
{
private static int N;
/*
* Method bubbleSort that takes an array,arr
* that sorts the elemenets in sorted order
* */
public static void bubbleSort(int[] arr)
{
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++)
{
for(int j=1; j < (n-i); j++)
{
if(arr[j-1] > arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
//Method quicksort that takes array,a and sorts
//elements using qsort helper method
public static void quickSort(int[] a)
{
//calling qsort method
qsort(a);
}
public static void qsort(int[] values)
{
if (values ==null || values.length==0){
return;
}
//calling quicksort
quicksort(values,0, values.length - 1);
}
//Quiksort procedure
private static void quicksort(int []numbers,int low, int high)
{
int i = low, j = high;
int pivot = numbers[low + (high-low)/2];
while (i <= j)
{
while (numbers[i] < pivot)
i++;
while (numbers[j] > pivot)
j--;
if (i <= j)
{
exchange(numbers,i, j);
i++;
j--;
}
}
if (low < j)
quicksort(numbers,low, j);
if (i < high)
quicksort(numbers,i, high);
}
//swapping two elements at index i and j
private static void exchange(int []numbers,int i, int j)
{
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
//Method :heapsort
public static void heapSort(int[] a) {
hsort(a);
}
public static void hsort(int arr[])
{
//calling heapify
heapify(arr);
for (int i = N; i > 0; i--)
{
exchange(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}
/* Method to create a heap */
public static void heapify(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
/* Method to swap largest element in the heap */
public static void maxheap(int arr[], int index)
{
int left = 2*index ;
int right = 2*index + 1;
int maximum = index;
if (left <= N && arr[left] > arr[index])
maximum = left;
if (right <= N && arr[right] > arr[maximum])
maximum = right;
if (maximum != index)
{
exchange(arr, index, maximum);
maxheap(arr, maximum);
}
}
}//end of Sorter class
------------------------------------------------------------------------
Sample output:
Sorted correctly? true
It took 250ms for bubble sort
Sorted correctly? true
It took 1ms for quick sort
Sorted correctly? true
It took 3ms for heap sort