Algorithms Lab $-$ Sorting Speed Real Time Comparison

Overview

Compare the real time speed between sorting algorithms on large sets of data.

Part $1$

public static int$[]$ createArrayWithRandomData$($int size, int randomMaxValue$)$

This method should allocate a new array of int $($number of elements is size$).$ Initialize all elements of the array with random numbers. The random numbers should be between $0$ and randomMaxValue. It should return the int$[]$ instance at the end of the method.

To generate random numbers first create an instance of Random:

Random rand $=$ new Random$()$; $//$instance of Random class

Use the Random instance to generate the numbers:

int randNum;

randNum $=$ rand.nextInt$(100000)$; $//$ Generates a random number in the range $0-99999$

Part $2$

Create a method with the following header:

public static void show$($int$[]$ ar$)$

This method should display all data in the array on screen.

Part $3$

Main method code:

Use createArrayWithRandomData to create an array with $1000$ items. The range of items should be $0-9.$ Save in variable ar$1.$

Make a copy of the original array containing the random data $($ar$1)$ using Arrays.copy. For example:

int$[]$ ar$2=$ Arrays.copyOf$($ar$1,$ ar$1.$length$)$;

Note: We are copying the array so that we can compare how the sorts run on the exact same data.

Show the data in both arrays on screen. Check that they have the same exact data.

Part $4$

Create a method with the following header:

public static void runJavaSort$($int$[]$ ar$)$

This method should call the Arrays.sort to sort ar$.$

Note: Arrays.sort uses a combination of sorts to sort the data $($quicksort$,$ mergesort, insertion sort, and heapsort$).$

Part $5$

public static void bubbleSort$($int$[]$ ar$)$

Implement the bubble sort algorithm. It should sort the int$[]$ parameter. Here is the pseudocode for bubble sort:

Part $6$

Test both sorts in main:

Call runJavaSort on ar$1.$

Call bubbleSort on ar$2.$

Show both sorted arrays on screen.

Part $7$

Run each sort in main and calculate how many nanoseconds it takes for each to run. You should print the results on screen.

Here is sample code to get the current time in nanoseconds:

long currentTime $=$ System.nanoTime$()$;Do the following:

Update runJavaSort to calculate the time it takes to sort the data.

Get the start time before starting the sort.

Get the end time after finishing the sort.

Subtract the start time from the end time and print it on screen.

Update bubbleSort to calculate the time it takes to sort the data.

Get the start time before starting the sort.

Get the end time after finishing the sort.

Subtract the start time from the end time and print it on screen.

Here is sample output after running the updated methods showing the times.

Part $8$

Implement counting sort and use it on another copy of the random data $($ar$3).$ Make sure to add the code to calculate the time.

Here is sample output after also running counting sort.

$\{\begin{array}{ccc}\text{:}[2,& 6,7,4,0,1,5,5,7,8,9,3,6,6,3,6,2,4,5,6,7,7,8,\text{d}\text{o}\text{t}\text{s}& ]\end{array}$

$\{\begin{array}{ccc}\text{:}[,& 6,7,4,0,1,5,5,7,8,9,3,6,6,3,6,2,4,5,6,7,7,8,\text{d}\text{o}\text{t}\text{s}& ]\end{array}$

runJavasort: $919800$

bubbleSort: $53756100$

counting sort: $342500$

Note: Counting sort is the fastest in the above scenario because the range is small $(0-9).$ You can try running all the sorts on $1000$ items where the range of items should be $0-100000000.$ Here are the results now:Counting sort is now worse than both the other sorts because k $($the range of items$)$ is very high with respect to n $($the number of items$).$