Need answer in java only with comments please ! Data Structures ( ASSIGNME Write

ID: 3912313 • Letter: N

Question

Need answer in java only with comments please !

Data Structures ( ASSIGNME Write a complete program to collect statistics on a series of sorts. The main program will continue the following until the end of the set of data... 1. Call a subprogram to read a group of numbers to be sorted 2. Call a subprogram to sort these values using three sorts 3. Call a subprogram to compare the three sorts STEP 1: The read subprogram will first read a heading describing the group of numbers might be: 10 numbers in order, or 50 numbers in a random order or 100 numbers in reverse o will read in the group of numbers. The original group should be printed as it is read in. rder). Then it STEP 2: The threesort subprog ram will call three separate sorts (be sure to send each one the items in their original order) a. One sort will be a stupid one either linear or bubble b. One sort will be quicksort c. One sort will be any other good one of your choice (eg heapsort) m finishes, the sorted array should be printed. Also print the number After each individual sort of comparisons each sort needed and the of times elements were computed within the three individual sorting subprograms. Use either additional variables, but be sure to include comments.) subprogra e values must be parameters or global STEP 3: The comparison subprogram will determine which sort used the most comparisons, which was in the middle, and which used the least. It will do the same thing for interchanges. DATA: Remember that each group of data must start with a heading describing what it is are allowed to have repeats in the group, but there should not be too include at least the following 9 groups (the heading for a group can testing. You many repeated values. you should be what I use to describe it) 1. 10 numbers in almost sorted order (two or three numbers interchanged) 3. 10 numbers in reverse order 4. 50 numbers in almost sorted order (a few out of order) 5. 50 numbers in random order 6. 50 numbers in reverse order 7. 100 numbers in almost sorted order (a few out of order) 8. 100 numbers in random order 9. 100 numbers in reverse order OPTIONAL: 1. Construct a sort which minimizes the number of interchanges (note: interchanges, not 2. Construct a way to generate 50 (or 100) numbers, num order bered 1-50 (or 1-100), without repeats, in random

Explanation / Answer

import java.io.*;

import java.util.*;

// Class SortingComparison definition

public class SortingComparison

{

// To store number of comparisons

static int totalBubble, totalInsert, totalQuick;

// Scanner class object created

static Scanner sc = new Scanner(System.in);

// To store heading

static String heading;

// Method for selection sort

public static void bubbleSort(int array[])

{

totalBubble = 0;

// Stores the length of array

int n = array.length;

// Loops till length minus one times

for (int i = 0; i < n - 1; i++)

{

// Loops till length minus i minus one times

for (int j = 0; j < n - i - 1; j++)

{

// Increase the counter by one

totalBubble++;

// Checks if the current position of array value is greater than the next position value then swap

if (array[j] > array[j+1])

{

// Swapping process

int temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}// End of if

}// End of inner for loop

}// End of outer for loop

}// End of method

* Method takes last element as pivot, places the pivot element at its correct position in sorted array,

* and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot

public static int partition(int array[], int low, int high)

{

int pivot = array[high];

// index of smaller element

int i = (low-1);

// Loops till low is less than high

for (int c = low; c < high; c++)

{

// If current element is smaller than or equal to pivot

if (array[c] <= pivot)

{

i++;

// Swap array[i] and array[c]

int temp = array[i];

array[i] = array[c];

array[c] = temp;

}//End of if

}//End of for

// Swap array[i+1] and array[high] (or pivot)

int temp = array[i+1];

array[i+1] = array[high];

array[high] = temp;

return i + 1;

}//End of method

// Method that implements QuickSort()

public static void quickSort1(int array[], int low, int high)

{

if (low < high)

{

// part is partitioning index, array[part] is now at right place

int part = partition(array, low, high);

// Recursively sort elements before partition and after partition

quickSort1(array, low, part-1);

quickSort1(array, part+1, high);

}//End of if

}//End of method

// Method for insertion sort

public static void insertionSort1(int array[])

{

// Stores the length of array

int len = array.length;

// Loops till length minus one times

for (int c = 1; c < len; ++c)

{

// Stores i index position value as key value

int key = array[c];

int d = c - 1;

// Move elements of array[0..i-1], that are greater than key, to one position ahead of their current position

while (d >= 0 && array[d] > key)

{

// Swaps each element of the array one position to right

array[d + 1] = array[d];

d = d - 1;

}// End of while

// Insert the key value at d plus one position

array[d+1] = key;

}// End of for

}// End of method

// Static method to read file contents and return the stored numbers array

static int [] readFile(String fileName)

{

// Declares an array of integer

int numbers[] = null;

int c = 0;

// Declares Scanner class object

Scanner readF = null;

// try block begins

try

{

// Creates the object to read file contents

readF = new Scanner(new File(fileName));

// Stores the heading

heading = readF.nextLine();

// Loops till end of the file

while(readF.hasNextInt())

{

// Read numbers

readF.nextInt();

// Increase the counter by one

c++;

}// End of while loop

// Dynamically allocates memory to array of size c

numbers = new int[c];

// Close the file

readF.close();

// Re opens the file

readF = new Scanner(new File(fileName));

// Skips the heading

readF.nextLine();

// Loops c times to read c numbers from file

for(int x = 0; x < c; x++)

{

// Reads data from file and stores it in array

numbers[x] = readF.nextInt();

}// End of for loop

}// End of try block

// Catch block to handle File not found exception

catch(FileNotFoundException fe)

{

System.out.println("Unable to open the file " + fileName);

}// End of catch block

// Closes the scanner

readF.close();

// Returns the array

return numbers;

}// End of method

// Static method to display menu and returns user choice

static int menu()

{

// To store user choice

int ch;

// Displays menu

System.out.print(" 1 - 10 numbers in almost sorted order.");

System.out.print(" 2 - 10 numbers in random order.");

System.out.print(" 3 - 10 numbers in reverse order.");

System.out.print(" 4 - 50 numbers in almost sorted order.");

System.out.print(" 5 - 50 numbers in random order.");

System.out.print(" 6 - 50 numbers in reverse order.");

System.out.print(" 7 - 100 numbers in almost sorted order.");

System.out.print(" 8 - 100 numbers in random order.");

System.out.print(" 9 - 100 numbers in reverse order.");

System.out.print(" 10 - Exit.");

// Accepts user choice

System.out.print(" Enter your choice: ");

ch = sc.nextInt();

// Returns user choice

return ch;

}// End of method

// main method definition

public static void main(String[] args)

{

// Integer array to store numbers

int anArray[] = null;

// Loops till user choice is not 10

{

// Counter initialized to zero

totalBubble = totalQuick = totalInsert = 0;

// Calls the method to accept use choice and reads appropriate file according to user choice

switch(menu())

{

case 1:

anArray = readFile("SortData1.txt");

break;

case 2:

anArray = readFile("SortData2.txt");

break;

case 3:

anArray = readFile("SortData3.txt");

break;

case 4:

anArray = readFile("SortData4.txt");

break;

case 5:

anArray = readFile("SortData5.txt");

break;

case 6:

anArray = readFile("SortData6.txt");

break;

case 7:

anArray = readFile("SortData7.txt");

break;

case 8:

anArray = readFile("SortData8.txt");

break;

case 9:

anArray = readFile("SortData9.txt");

break;

case 10:

System.out.print(" End Program. Thaks.");

System.exit(0);

break;

default:

System.out.print(" Invalid choice.");

}// End of switch - case

// Displays heading

System.out.println("********************************* " + heading + " ********************************************");

// Bubble Sort

// Displays array before bubble sort

System.out.println("Before Bubble Sort");

for(int i:anArray)

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

System.out.println();

//Sorting array using Bubble sort

bubbleSort(anArray);

//Displays array after Bubble sort

System.out.println("After Bubble Sort");

for(int i:anArray)

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

System.out.println(" Number of comparisons Bubble sort: " + totalBubble);

//Insertion Sort

//Displays array before Insertion sort

System.out.println(" Before Insertion Sort");

for(int i:anArray)

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

System.out.println();

//Sorting array using Insertion sort

insertionSort1(anArray);

//Displays array after Insertion sort

System.out.println("After Insertion Sort");

for(int i : anArray)

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

System.out.println(" Number of comparisons Insertion sort: " + totalInsert);

//Quick Sort

//Displays array before Quick sort

System.out.println(" Before Quick Sort");

for(int i:anArray)

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

System.out.println();

//Sorting array using quick sort

quickSort1(anArray, 0, anArray.length-1);

//Displays array after Quick sort

System.out.println("After Quick Sort");

for(int i:anArray)

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

System.out.println(" Number of comparisons Quick sort: " + totalQuick);

}while(true); // End of do - while

}// End of main method

}// End of class

Sample Output:

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 1

********************************* 10 numbers in almost sorted order ********************************************

Before Bubble Sort

5 7 9 12 18 22 25 32 40 39

After Bubble Sort

5 7 9 12 18 22 25 32 39 40

Number of comparisons Bubble sort: 45

Before Insertion Sort

5 7 9 12 18 22 25 32 39 40

After Insertion Sort

5 7 9 12 18 22 25 32 39 40

Number of comparisons Insertion sort: 0

Before Quick Sort

5 7 9 12 18 22 25 32 39 40

After Quick Sort

5 7 9 12 18 22 25 32 39 40

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 2

********************************* 10 numbers in random order ********************************************

Before Bubble Sort

12 89 66 45 10 78 99 32 1 67

After Bubble Sort

1 10 12 32 45 66 67 78 89 99

Number of comparisons Bubble sort: 45

Before Insertion Sort

1 10 12 32 45 66 67 78 89 99

After Insertion Sort

1 10 12 32 45 66 67 78 89 99

Number of comparisons Insertion sort: 0

Before Quick Sort

1 10 12 32 45 66 67 78 89 99

After Quick Sort

1 10 12 32 45 66 67 78 89 99

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 3

********************************* 10 numbers in reverse order ********************************************

Before Bubble Sort

99 91 89 77 57 35 22 19 5 2

After Bubble Sort

2 5 19 22 35 57 77 89 91 99

Number of comparisons Bubble sort: 45

Before Insertion Sort

2 5 19 22 35 57 77 89 91 99

After Insertion Sort

2 5 19 22 35 57 77 89 91 99

Number of comparisons Insertion sort: 0

Before Quick Sort

2 5 19 22 35 57 77 89 91 99

After Quick Sort

2 5 19 22 35 57 77 89 91 99

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 4

********************************* 50 numbers almost sorted order ********************************************

Before Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 99 94

After Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Bubble sort: 1225

Before Insertion Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

After Insertion Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Insertion sort: 0

Before Quick Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

After Quick Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 5

********************************* 50 numbers random order ********************************************

Before Bubble Sort

1 17 9 10 2 8 22 25 37 29 13 32 35 49 42 45 57 99 51 53 95 58 60 61 76 69 71 64 66 77 79 82 85 80 91 98 21 23 15 19 90 89 5 55 70 19 31 4 16 67

After Bubble Sort

1 2 4 5 8 9 10 13 15 16 17 19 19 21 22 23 25 29 31 32 35 37 42 45 49 51 53 55 57 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 95 98 99

Number of comparisons Bubble sort: 1225

Before Insertion Sort

1 2 4 5 8 9 10 13 15 16 17 19 19 21 22 23 25 29 31 32 35 37 42 45 49 51 53 55 57 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 95 98 99

After Insertion Sort

1 2 4 5 8 9 10 13 15 16 17 19 19 21 22 23 25 29 31 32 35 37 42 45 49 51 53 55 57 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 95 98 99

Number of comparisons Insertion sort: 0

Before Quick Sort

1 2 4 5 8 9 10 13 15 16 17 19 19 21 22 23 25 29 31 32 35 37 42 45 49 51 53 55 57 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 95 98 99

After Quick Sort

1 2 4 5 8 9 10 13 15 16 17 19 19 21 22 23 25 29 31 32 35 37 42 45 49 51 53 55 57 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 95 98 99

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 6

********************************* 50 numbers reverse order ********************************************

Before Bubble Sort

99 94 93 91 89 88 85 82 80 79 77 76 74 72 71 69 66 63 60 58 57 55 53 52 51 49 47 45 42 40 39 35 32 31 30 29 27 25 23 22 20 18 15 12 10 9 7 5 3 1

After Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Bubble sort: 1225

Before Insertion Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

After Insertion Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Insertion sort: 0

Before Quick Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

After Quick Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 7

********************************* 100 numbers almost sorted order ********************************************

Before Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 99 94 101 103 145 147 159 160 162 165 168 170 172 183 185 187 190 193 197 199 200 201 205 209 217 219 221 225 229 230 235 237 240 244 245 246 249 257 259 261 266 267 269 273 275 279 280 283 285 289 294 291

After Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 57 58 60 63 66 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99 101 103 145 147 159 160 162 165 168 170 172 183 185 187 190 193 197 199 200 201 205 209 217 219 221 225 229 230 235 237 240 244 245 246 249 257 259 261 266 267 269 273 275 279 280 283 285 289 291 294

Number of comparisons Bubble sort: 4950

Before Insertion Sort

After Insertion Sort

Number of comparisons Insertion sort: 0

Before Quick Sort

After Quick Sort

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 8

********************************* 100 numbers random order ********************************************

Before Bubble Sort

1 17 9 111 2 8 222 25 37 279 13 32 135 49 42 45 157 199 51 53 95 58 60 61 76 69 71 64 66 77 79 82 85 80 91 98 21 23 15 19 90 89 5 55 70 19 31 4 16 67 101 107 94 110 228 223 125 137 29 130 132 235 149 242 245 157 190 151 163 295 158 160 166 122 169 171 164 266 277 279 282 185 180 121 138 211 223 215 219 290 289 5 7 170 177 131 14 26 97

After Bubble Sort

1 2 4 5 5 7 8 9 13 14 15 16 17 19 19 21 23 25 26 29 31 32 37 42 45 49 51 53 55 58 60 61 64 66 67 69 70 71 76 77 79 80 82 85 89 90 91 94 95 97 98 101 107 110 111 121 122 125 130 131 132 135 137 138 149 151 157 157 158 160 163 164 166 169 170 171 177 180 185 190 199 211 215 219 222 223 223 228 235 242 245 266 277 279 279 282 289 290 295

Number of comparisons Bubble sort: 4851

Before Insertion Sort

After Insertion Sort

Number of comparisons Insertion sort: 0

Before Quick Sort

After Quick Sort

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 9

********************************* 100 numbers reverse order ********************************************

Before Bubble Sort

199 198 195 192 191 190 189 186 185 182 181 180 179 175 174 170 169 166 165 162 160 159 157 156 155 152 151 150 149 142 140 139 135 132 130 127 125 120 117 115 111 110 109 102 103 101 100 99 94 93 91 89 88 85 82 80 79 77 76 74 72 71 69 67 66 63 60 58 57 56 55 53 52 51 49 47 45 42 40 39 35 32 31 30 29 27 26 25 23 22 20 18 15 12 10 9 7 5 3 1

After Bubble Sort

1 3 5 7 9 10 12 15 18 20 22 23 25 26 27 29 30 31 32 35 39 40 42 45 47 49 51 52 53 55 56 57 58 60 63 66 67 69 71 72 74 76 77 79 80 82 85 88 89 91 93 94 99 100 101 102 103 109 110 111 115 117 120 125 127 130 132 135 139 140 142 149 150 151 152 155 156 157 159 160 162 165 166 169 170 174 175 179 180 181 182 185 186 189 190 191 192 195 198 199

Number of comparisons Bubble sort: 4950

Before Insertion Sort

After Insertion Sort

Number of comparisons Insertion sort: 0

Before Quick Sort

After Quick Sort

Number of comparisons Quick sort: 0

1 - 10 numbers in almost sorted order.

2 - 10 numbers in random order.

3 - 10 numbers in reverse order.

4 - 50 numbers in almost sorted order.

5 - 50 numbers in random order.

6 - 50 numbers in reverse order.

7 - 100 numbers in almost sorted order.

8 - 100 numbers in random order.

9 - 100 numbers in reverse order.

10 - Exit.

Enter your choice: 10

End Program. Thaks.

Navigate

Need answer in c++ programming using classes The Fibonacci sequence is the serie

Need answer in twenty minutes!!! ABC, Inc. purchased new machinery in order to i

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Need answer in java only with comments please ! Data Structures ( ASSIGNME Write

Question

Explanation / Answer

Related Questions

Navigate