 # Sorting Out Sorts

## Question

Description
As a new and eager employee of NovaTech, Inc. (Nova Technology Incorporated, a subsidiary of NSU) you've been asked by your employer to implement a sorting algorithm for inclusion in a package for a lucrative client. However, your boss just wants you to implement one of the simple, quadratic sorting algorithms. To prove that this would be a big mistake, you've decided (on your own) to prove to your idiot boss that it's worth the extra effort to implement one of the O(n log n) sorting algorithms. For this project, you will implement and compare five sorting algorithms: bubble sort, insertion sort, selection sort, quicksort, and either mergesort or shellsort.

Your main program will then do the following:
1. Ask the user for the size n of the list he/she wants to sort.
2. Create an array of size n and fill it with random integers between 1 and n. If n<=100, display the random array on the screen.
3. Run each of your sorts on this array. You must make a deep copy of the array before sorting it, or your second sort will have an easy time of it. Use the System.currentTimeMillis() function to determine the running time of each sort.
4. If n<=100, display the sorted arrays on the screen (they better be the same!).
5. Display the time each sort used to sort the array.
Once you have your program working, use it to plot a graph. Have the x-axis represent n, and the y-axis the running time. Use n=10000, 20000, ..., 100000. Plot all sorting algorithms on the same graph (use different colors or line styles). You shall use a spreadsheet program (e.g., MS Excel) or some other program to do this for you. (Will your boss be convinced?)

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.util.*;

/*
*/
public class Lab4 {

// Helper method to construct random array
public static int[] randomArray(int n) {
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = 1 + (int) (Math.random() * (n+1));
}
return array;
}

// Main method for program execution
public static void main(String[] args) {
Scanner s = new Scanner(System.in);

// Query the user for random array size
System.out.println("Enter the size of the list you would like to sort: ");
int n = Integer.parseInt(s.nextLine());

// Construct random array
int[] array = randomArray(n);
int startTime, endTime, duration;
Sorts.setValues(array);
if (n <= 100) {
System.out.println("Random Array:");
Sorts.printValues();
}

// Do Bubble Sort
Sorts.setValues(array);
startTime = (int) System.currentTimeMillis();
Sorts.bubbleSort();
endTime = (int) System.currentTimeMillis();
if (n <= 100) {
System.out.println("After Bubble Sort:");
Sorts.printValues();
}
duration = endTime - startTime;
System.out.println("Bubble Sort duration: " + duration + "\n");

// Do Insertion Sort
Sorts.setValues(array);
startTime = (int) System.currentTimeMillis();
Sorts.insertionSort();
endTime = (int) System.currentTimeMillis();
if (n <= 100) {
System.out.println("After Insertion Sort:");
Sorts.printValues...
\$70.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.