PLEASE POST SOLUTION IN JAVA ONLY!

Implement (or use built-in algorithms for) QuickSort, and InsertionSort. Compare their running times on sets of integers of size 10, 25, 50, and 100. Which appears to perform better as the number of integers increases? Why did you get the results you did? Make sure to run each algorithm at least 5 times on each set size (five times for set size of 10, five times for 25, etc. for EACH algorithm.)

Hint: Make use of the currentTimeMillis() method of System.

E.g.,

long startingTime = System.currentTimeMillis(); long total = 0;

//do something here: run an algorithm to test timing on

long stoppingTime = System.currentTimeMillis();

long elapsed = stoppingTime - startingTime;

System.out.println(elapsed);

This obtains the current time from the system at the beginning, then after the algorithm being tested is performed, get the stopping time. Then, find the difference, referred to as the elapsed time, and do something with it.

I am going to post my source code here. Most of the work is already completed and the project runs and gives the total times in QuickSort and InsertionSort after 5 runs on each set of numbers (10, 25, 50, 100), but what I am having trouble with is printing each of the 5 different run times for each number (e.g. 5 runtimes for 10, 5 runtimes for 25, 5 runtimes for 50, 5 runtimes for 100, etc.) in both QuickSort and InsertionSort before showing the total elapsed time for each of the integers. What I want to do is show all 5 of the runtimes along with the total elapsed time.

Source Code:

//TestingSort

package testingsort;

import java.util.Random;

public class TestingSort {

/** * @param args the command line arguments */ public static void main(String[] args) {

//sets variables int size; int[] items1; int[] items2; long timeStart, timeStop, timeElapsed, total, total1, total2 = 0, total3 = 0; //set array size size = 10; items1 = new int[size]; items2 = new int[size]; fillArrays(items1, items2, size);

System.out.println("Size: " + size); total = 0; for (int i = 1; i <= 5; i++) { timeStart = System.nanoTime(); QuickSort(items1); timeStop = System.nanoTime(); timeElapsed = timeStop - timeStart; total += timeElapsed; } System.out.println("Elapsed time for Quick Sort in nanoseconds: " + total); total2 += total; total1 = 0; for (int i = 1; i <= 5; i++) { timeStart = System.nanoTime(); InsertionSort(items2); timeStop = System.nanoTime(); timeElapsed = timeStop - timeStart; total1 += timeElapsed; } total3 += total1; System.out.println("Elapsed time for Insertion Sort in nanoseconds: " + total1); if (total < total1) { System.out.println("Quicksort is faster in this case."); } else { System.out.println("Insertion Sort is faster in this case."); } for (size = 25; size <= 100; size *= 2) { System.out.println(" Size: " + size); items1 = new int[size]; items2 = new int[size]; fillArrays(items1, items2, size);

total = 0; for (int i = 1; i <= 5; i++) { timeStart = System.nanoTime(); QuickSort(items1); timeStop = System.nanoTime(); timeElapsed = timeStop - timeStart; total += timeElapsed; } total2 += total; System.out.println("Elapsed time for QuickSort in nanoseconds: " + total);

total1 = 0; for (int i = 1; i <= 5; i++) { timeStart = System.nanoTime(); InsertionSort(items2); timeStop = System.nanoTime(); timeElapsed = timeStop - timeStart; total1 += timeElapsed; } total3 += total1; System.out.println("Elapsed time for InsertionSort in nanoseconds: " + total1); if (total < total1) { System.out.println("Quicksort is faster in this case."); } else { System.out.println("Insertion Sort is faster in this case."); }

}

System.out.println(); System.out.println("The total elapsed time for quicksort for all cases: " + total2); System.out.println("The total elapsed time for insertion sort for all cases: " + total3); if (total2 < total3) { System.out.println("As the list size continues to grow QuickSort is faster overall for all test cases."); } else { System.out.println("As the list size continues to grow InsertionSort is faster overall for all test cases."); } }

public static void fillArrays(int[] items1, int[] items2, int size) { Random rand = new Random();

for (int i = 0; i < size; i++) { int number = rand.nextInt(size); items1[i] = number; items2[i] = number; } }

public static void QuickSort(int[] items) { QuickSort(items, 0, items.length - 1); }

private static void QuickSort(int[] items, int l, int r) { int s = Partition(items, l, r);

if (l < s - 1) { QuickSort(items, l, s - 1); } if (s < r) { QuickSort(items, s, r); } }

private static int Partition(int[] items, int l, int r) { int p = l; int q = r; int temp; int pivot; pivot = items[(l + r) / 2];

while (p <= q) { while (items[p] < pivot) { p++; } while (items[q] > pivot) { q--; }

if (p <= q) { temp = items[p]; items[p] = items[q]; items[q] = temp; p++; q--; } } return p; }

public static void InsertionSort(int[] items) { for (int i = 1; i < items.length; i++) { int temp = items[i]; int j = i;

while (j > 0 && temp < items[j - 1]) { items[j] = items[j - 1]; j--; }

items[j] = temp; } } } //end main program