Empirical Study of Sorting Algorithms Complexity

The goal of this project is to compare efficiency of three sorting algorithms by measuring the time it takes for them to sort exactly same array of integers.

• Find and copy into your code implementations of three classic sorting algorithms: Quicksort, Bubble sort, and Selection sort. All 3 can be found in Chapter 17 folder of the text book source code posted in Course Info and Resources module of the course.
• In main() write code that creates
• 3identicalarrays of size 1000000 filled with random numbers in the range [1 - 1000000]
• Use code fromRecursiveFibonacciTimer.javaDownload RecursiveFibonacciTimer.java from Chapter 17 folder to measure time it took each of the sorting algorithms to sort the array. Each sorting method must have the same set of numbers to sort, so use one of the 3 arrays you created for each method.
• When printing out time, convert it into minutes and seconds format.
• In the beginning of your file with the solution, in comments, record the timing results you got when running the sorting methods - for me to see.
• Finally, find out how much time it takes Quicksort to sort 100000000 random integers on your computer. Record that result in the beginning of the source code file too.

Name your solution EmpiricalStudy.java

Make sure to createa text file with table-like formatted data similar to what you see below. Name the file EmpiricalStudyTimes.txt

Sorting Algorithm and Array Size	Time
Bubble Sort on array of 1000000 elements
Selection Sort on array of 1000000 elements
Quicksort on array of 1000000 elements
Quicksort on array of 100000000 elements

In order to complete the next part of the assignment you will need to use the unit tests code provided in fileAsg05_Files.zipDownload Asg05_Files.zip

Make sure to write the class methods according to the following specifications and test them using the test cases provided inAsg05_Files.zipDownload Asg05_Files.zip. Do not alter any of the tests! If your code is not passing a test, find and fix errors in your method implementation rather than changing the test code.

BubbleSortTestCode

/**

This program tests the bubbleSort method in the

IntBubbleSorter class.

*/

public class BubbleSortTest

{

public static void main(String[] args)

{

// Createan int array with test values.

int[] values = { 5, 1, 3, 6, 4, 2 };

// Display the array's contents.

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

// Sort the array.

IntBubbleSorter.bubbleSort(values);

// Display the array's contents.

System.out.println(" Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println();

}

}

QuickSortTestCode

/**

This program tests the quickSort method in the

IntQuickSorter class.

*/

public class QuickSortTest

{

public static void main(String[] args)

{

// Createan int array with test values.

int[] values = { 5, 1, 3, 6, 4, 2 };

// Display the array's contents.

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

// Sort the array.

IntQuickSorter.quickSort(values);

// Display the array's contents.

System.out.println(" Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println();

}

}

SelectionSortTestCode

/**

This program tests the selectionSort method in the

IntSelectionSorter class.

*/

public class SelectionSortTest

{

public static void main(String[] args)

{

// Createan int array with test values.

int[] values = { 5, 1, 3, 6, 4, 2 };

// Display the array's contents.

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

// Sort the array.

IntSelectionSorter.selectionSort(values);

// Display the array's contents.

System.out.println(" Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println();

}

}

RecursiveFibonacciTimer

import java.util.Scanner;

/**

* This program times calls to the recursive Fibonacci method

* for 6 consecutive calls and displays the results.

*/

public class RecursiveFibonacciTimer

{

public static void main(String[] args)

{

// Get the starting argument

System.out.println("Enter a positive integer:");

Scanner sc = new Scanner(System.in);

int number = sc.nextInt();

// Variables used to determine time for a function call

long currentTime = System.currentTimeMillis();

long previousTime;

long elapsedTime = 0;

for (int k = 0; k <= 5; k++)

{

// Record time before function call

previousTime = currentTime;

System.out.print("The Fibonacci term at position ");

System.out.print((number + k) + " is " );

// Compute and print fib term for the next argument

System.out.println(fib(number + k));

// Record time after function call

currentTime = System.currentTimeMillis();

// Compute and print elapsed time in seconds

elapsedTime = (currentTime - previousTime)/1000;

System.out.println("Computed in " + elapsedTime + " seconds.");

}

}

/**

* Computes a term of the Fibonacci sequence

* @param n

* @return nth term of the sequence

*/

public static long fib(long n)

{

if (n <=1)

return 1;

else

return fib(n-2) + fib(n-1);

}

}