Write a java program to sort arrays using 3 different methods: Bubble Sort, Selection Sort and...

Question

Question

Write a java program to sort arrays using 3 different methods: Bubble Sort, Selection Sort and...

Write a java program to sort arrays using 3 different methods: Bubble Sort, Selection Sort and Insertion Sort. The numbers to be sorted will be obtained using a library function which generates pseudo-random numbers.

TO Do

1. Fill an array with 140 real numbers between 0.00 and 945.00. Generate the numbers using the subroutine that generates random numbers. Make a spare copy of the array; you will need it later.

2. Call a subroutine to print the contents of the array with 9 numbers per line, in F6.2 (ex. 835.60) format. Use double-spacing. The last line will not be full.

3. Call a subroutine to sort the array in ascending order using Selection Sort. You will need to pass the array as an argument of this subroutine.

4. Call the print subroutine again, as in (2). Also: skip 2 lines and then print lines stating the number of swaps and the number of comparisons used in the Selection Sort step.

5. Starting over with the original contents of the array, call a subroutine to sort the array in ascending order using Bubble Sort. You will need to pass the array as an argument of this subroutine, also.

6. Call the print subroutine again, as in (2). Also: skip 2 lines and then print lines stating the number of swaps and the number of comparisons used in the Bubble Sort step.

7. Starting over with the original contents of the array, call a subroutine to sort the array in ascending order using Insertion Sort. You will need to pass the array as an argument of this subroutine, also.

8. Call the print subroutine again. Also: skip 2 lines and then print lines stating the number of swaps and the number of comparisons used in the Insertion Sort step.

Submission

1. Source code of your completed program (must compile and execute without any error).

2. Output file called "P2.out" which is created by running the program using output redirection.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// Sorting.java

public class Sorting {

// global variables to count the number of swaps and comparisons taken by

// each sorting methods

private static int swaps = 0, comparisons = 0;

// method to create and return an array containing size number of random

// doubles

public static double[] generateRandom(int size) {

double array[] = new double[size];

for (int i = 0; i < array.length; i++) {

// generating a number between 0 and 94500

int num = (int) (Math.random() * 94501);

// dividing by 100 to get a double number between 0.0 and 945.00

double x = (double) num / 100.0;

// adding to array

array[i] = x;

}

return array;

}

// method to print the contents of an array, 9 elements at a time

static void print(double array[]) {

for (int i = 0; i < array.length; i++) {

System.out.printf("%6.2f ", array[i]);

if ((i + 1) % 9 == 0) {

System.out.println();

}

System.out.println();

}

// method to return a copy of the array passed.

static double[] copyArray(double original[]) {

double[] copy = new double[original.length];

for (int i = 0; i < original.length; i++) {

copy[i] = original[i];

}

return copy;

}

// method to sort numbers using selection sort

static void selectionSort(double[] data) {

// resetting swaps and comparisons to 0

swaps = 0;

comparisons = 0;

int n = data.length;

// using selection sort algorithm to sort elements in data

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

// finding the index of smallest element in the unsorted array

int index_min = i;

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

comparisons++;

if (data[j] < data[index_min])

index_min = j;

}

// swapping element at i with element at index_min

double temp = data[index_min];

data[index_min] = data[i];

data[i] = temp;

swaps++;

}

// method to sort numbers using bubble sorting

public static void bubbleSort(double[] array) {

// resetting swaps and comparisons to 0

swaps = 0;

comparisons = 0;

int n = array.length;

for (int pass = 1; pass < n; pass++) {

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

if (array[i] > (array[i + 1])) {

// swap elements

double temp = array[i];

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

array[i + 1] = temp;

swaps++;

}

comparisons++;

}

// method to sort numbers using insertion sorting

public static void insertionSort(double[] array) {

// resetting swaps and comparisons to 0

swaps = 0;

comparisons = 0;

for (int i = 1; i < array.length; i++) {

double temp = array[i];

int j = i;

comparisons++;

while ((j > 0) && (array[j - 1] > array[j])) {

if (array[j - 1] > array[j]) {

// increasing number of comparisons

comparisons++;

}

temp = array[j - 1];

array[j - 1] = array[j];

array[j] = temp;

j--;

// increasing swaps

swaps++;

}

public static void main(String[] args) {

// generating an aray of 140 doubles

double original[] = generateRandom(140);

// taking a copy

double copy[] = copyArray(original);

// printing array

print(copy);

// performing selection sort, printing array and number of swaps &

// comparisons

System.out.println("Selection Sort\n");

selectionSort(copy);

print(copy);

System.out.println("\n\nNumber of swaps: " + swaps);

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

// taking a copy of the original again

copy = copyArray(original);

// performing bubble sort, printing array and number of swaps &

// comparisons

System.out.println("Bubble Sort\n");

bubbleSort(copy);

print(copy);

System.out.println("\n\nNumber of swaps: " + swaps);

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

// taking a copy of the original again

copy = copyArray(original);

// performing insertion sort, printing array and number of swaps &

// comparisons

System.out.println("Insertion Sort\n");

insertionSort(copy);

print(copy);

System.out.println("\n\nNumber of swaps: " + swaps);

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

}

/*OUTPUT*/

556.53 661.73 493.20 254.76 545.33 520.93 17.83 826.65 678.03

762.35 13.66 912.14 174.69 667.91 54.02 31.91 885.21 469.75

496.53 860.40 463.49 114.44 105.20 703.10 597.95 795.34 598.14

728.18 606.84 385.25 126.12 347.10 731.98 587.79 800.63 667.16

81.56 765.71 842.47 42.07 142.79 703.47 450.58 307.40 817.65

29.12 18.87 268.81 310.42 792.37 747.27 679.77 698.50 105.97

592.04 859.19 328.60 87.79 764.09 415.82 733.87 48.65 387.94

798.18 407.93 593.77 283.16 507.61 291.04 66.81 474.24 467.16

209.10 905.86 779.57 15.43 365.66 679.12 449.37 647.33 293.30

322.10 852.51 313.21 145.06 218.95 236.74 398.40 93.34 61.95

592.28 732.21 703.34 782.77 783.33 889.18 220.10 932.56 313.14

830.22 608.23 815.67 78.24 757.45 145.40 797.85 108.18 179.53

586.67 15.62 43.35 943.33 493.35 167.14 303.84 33.13 611.65

893.52 393.92 321.05 508.70 831.28 292.78 124.98 414.50 67.67

218.67 545.83 406.98 665.53 75.16 161.54 488.01 407.75 860.12

23.23 592.24 239.74 569.65 677.60

Selection Sort

13.66 15.43 15.62 17.83 18.87 23.23 29.12 31.91 33.13

42.07 43.35 48.65 54.02 61.95 66.81 67.67 75.16 78.24

81.56 87.79 93.34 105.20 105.97 108.18 114.44 124.98 126.12

142.79 145.06 145.40 161.54 167.14 174.69 179.53 209.10 218.67

218.95 220.10 236.74 239.74 254.76 268.81 283.16 291.04 292.78

293.30 303.84 307.40 310.42 313.14 313.21 321.05 322.10 328.60

347.10 365.66 385.25 387.94 393.92 398.40 406.98 407.75 407.93

414.50 415.82 449.37 450.58 463.49 467.16 469.75 474.24 488.01

493.20 493.35 496.53 507.61 508.70 520.93 545.33 545.83 556.53

569.65 586.67 587.79 592.04 592.24 592.28 593.77 597.95 598.14

606.84 608.23 611.65 647.33 661.73 665.53 667.16 667.91 677.60

678.03 679.12 679.77 698.50 703.10 703.34 703.47 728.18 731.98

732.21 733.87 747.27 757.45 762.35 764.09 765.71 779.57 782.77

783.33 792.37 795.34 797.85 798.18 800.63 815.67 817.65 826.65

830.22 831.28 842.47 852.51 859.19 860.12 860.40 885.21 889.18

893.52 905.86 912.14 932.56 943.33

Number of swaps: 139

Number of comparisons: 9730

Bubble Sort