One of the points we made in Module 2 was that the different sorts can have diff
ID: 3719671 • Letter: O
Question
One of the points we made in Module 2 was that the different sorts can have different efficiencies/complexities. This is in contrast to binary search, which we can expect to work in approximately O(log2 n) of the size n of the sorted list. In other classes you can get into the theoretical elements of the computational complexity of sorting. Here we will look at it experimentally. We will look at the behavior of two different sorts on randomly generated lists of different sizes. • The two sorts are bubblesort and quicksort. • Randomly generate integers in the range 0-99 for your random numbers. You may choose your own random number generation technique. You must document the source of your random number generation in the code. Here is what your code should do: 1. Do this 10 times: a. Generate a random list of 100 items b. Have each algorithm sort the list. c. Give the original list, the sorted list, and the number of comparisons done by each algorithm. 2. At the end: a. For each algorithm and each list length give the average of the number of comparisons.
using java please
Explanation / Answer
package javaapplication36;
import java.util.Random;
class Sort
{
int comp1,comp2,swap1,swap2;
int a[],b[];
public Sort()
{
comp1=0;
comp2=0;
swap1=0;
swap2=0;
a=new int[100];
b=new int[100];
}
void swap(int arr[],int i, int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
comp1++;
if (arr[j] <= pivot)
{
i++;
swap1++;
// swap arr[i] and arr[j]
swap(arr,i,j);
}
}
// swap arr[i+1] and arr[high] (or pivot)
swap(arr,i+1,high);
return i+1;
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
void displayarray(int arr[])
{
int i,n=arr.length;
System.out.print(" Array before sorting: ");
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
}
void bubbleSort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
comp2++;
if (arr[j] > arr[j+1])
{
swap(arr,j, j+1);
swap2++;
}
}
}
}
public void RandomArrayElement()
{
int i,t;
Random random=new Random();
for(i=0;i<100;i++)
{
t=random.nextInt(100);
a[i]=t;
b[i]=t;
}
}
public void comparison()
{
int i;
for(i=0;i<10;i++)
{
RandomArrayElement();
displayarray(a);
bubbleSort(a);
quickSort(b,0,b.length-1);
System.out.print(" Number of Comarioson in Bubbele Sort:= "+comp2 + " number of swap=:"+swap2);
System.out.print(" Number of Comarioson in Quick Sort:= "+comp1+ " number of swap=:"+swap1);
System.out.print(" ");
comp1=0;
comp2=0;
swap1=0;
swap2=0;
}
}
}
public class SortCompare {
public static void main(String[] args) {
Sort s= new Sort();
s.comparison();
}
}
output:
run:
Array before sorting:
71 95 30 85 29 29 35 11 61 72 98 29 60 23 87 4 32 66 25 29 9 56 52 36 26 89 40 7 91 69 85 31 28 84 4 43 93 56 14 97 62 84 49 31 19 99 3 91 53 31 16 68 39 64 84 25 51 88 17 7 73 32 63 48 10 13 77 30 75 54 24 63 37 75 56 35 37 7 47 67 64 70 91 66 65 77 20 44 0 52 55 88 36 27 90 75 52 92 99 20
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2317
Number of Comarioson in Quick Sort:= 645 number of swap=:225
Array before sorting:
81 92 21 94 38 29 40 51 70 95 70 67 76 31 74 41 14 94 44 46 45 19 86 41 44 26 55 45 79 95 81 32 95 24 32 41 87 87 25 68 45 0 16 7 11 95 4 33 98 15 30 83 82 26 22 39 72 45 86 44 13 40 15 49 42 36 85 5 57 32 47 16 28 26 25 86 29 3 4 0 34 90 72 48 22 3 48 29 58 42 26 24 38 84 45 79 40 6 77 36
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2815
Number of Comarioson in Quick Sort:= 603 number of swap=:330
Array before sorting:
85 86 59 20 82 92 13 76 53 96 45 60 74 55 40 99 63 54 26 68 5 93 99 58 15 0 64 33 24 55 43 85 61 22 81 73 62 74 76 78 14 76 61 91 18 11 12 31 99 4 39 61 20 51 98 31 74 4 92 46 95 90 15 14 58 39 54 47 94 92 79 56 3 5 53 95 57 4 17 70 15 93 81 22 72 65 46 50 42 52 62 75 40 62 70 22 6 57 38 90
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2637
Number of Comarioson in Quick Sort:= 682 number of swap=:356
Array before sorting:
12 28 59 77 43 16 60 53 92 8 68 16 36 82 55 97 49 77 70 71 19 21 28 22 23 70 98 52 77 26 95 86 45 9 90 45 98 31 13 87 59 45 68 63 59 96 68 2 32 63 67 87 56 24 85 6 92 86 47 20 91 90 12 91 94 48 29 26 23 10 71 69 59 77 32 91 52 59 19 19 1 33 89 85 45 20 88 94 32 27 35 80 72 70 53 97 64 46 83 11
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2346
Number of Comarioson in Quick Sort:= 617 number of swap=:292
Array before sorting:
12 27 99 96 15 48 54 99 61 61 35 10 1 85 21 83 11 27 89 35 30 41 65 51 10 14 10 41 89 13 87 77 29 96 63 23 56 9 90 27 58 2 53 16 31 48 77 51 33 0 91 23 57 65 14 27 16 75 88 68 84 69 50 53 14 59 60 50 43 22 38 44 49 88 25 50 88 5 37 49 45 97 52 94 77 85 96 2 57 52 15 19 97 66 56 89 50 86 57 69
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2172
Number of Comarioson in Quick Sort:= 649 number of swap=:400
Array before sorting:
24 15 79 62 95 20 76 94 67 64 58 3 42 3 51 52 59 58 94 9 94 12 99 7 13 45 15 21 31 0 12 90 24 48 5 39 14 81 78 94 21 89 71 96 19 50 51 36 80 21 83 1 40 94 29 14 41 65 5 54 53 16 67 99 21 55 59 72 61 76 93 10 61 1 24 87 36 53 22 62 95 70 46 80 96 96 47 84 98 94 97 75 57 27 75 63 56 46 32 89
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2091
Number of Comarioson in Quick Sort:= 707 number of swap=:387
Array before sorting:
32 34 2 39 92 64 2 24 63 61 45 96 48 0 82 31 78 48 52 96 29 83 35 40 98 14 72 8 41 43 10 72 1 32 25 81 99 9 40 54 37 18 28 0 2 58 35 27 22 89 23 29 40 69 62 97 40 67 63 84 35 90 37 62 90 52 13 80 55 90 42 3 24 97 36 45 62 67 12 79 41 85 48 31 33 78 56 39 49 38 69 16 29 40 79 69 16 94 80 68
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2237
Number of Comarioson in Quick Sort:= 605 number of swap=:379
Array before sorting:
17 56 47 54 86 9 80 7 6 74 6 69 40 12 71 22 59 91 66 47 65 77 17 98 34 48 44 3 88 51 35 31 68 93 1 81 77 40 65 14 45 38 73 81 15 10 23 48 80 30 64 30 71 21 73 50 29 60 92 17 47 13 55 80 81 48 36 65 51 94 72 83 3 28 95 5 34 26 15 41 50 9 41 75 2 62 41 58 28 5 44 61 67 35 43 58 84 68 12 71
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2476
Number of Comarioson in Quick Sort:= 641 number of swap=:390
Array before sorting:
11 75 11 72 99 4 58 45 16 11 91 38 62 64 54 86 53 10 19 69 23 17 90 12 74 25 59 86 26 91 40 60 90 48 27 71 86 39 11 35 25 83 28 15 58 91 27 96 46 75 84 47 65 64 3 64 5 75 30 89 24 80 93 8 2 74 15 85 43 43 93 88 47 65 29 24 59 87 45 61 94 95 44 79 42 98 70 60 60 63 19 83 6 28 69 79 82 38 63 40
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2220
Number of Comarioson in Quick Sort:= 597 number of swap=:336
Array before sorting:
87 87 3 43 37 54 19 17 39 91 21 20 69 24 3 11 12 30 0 48 38 0 91 58 40 81 57 12 67 51 35 44 2 92 73 53 36 7 35 18 78 57 59 68 16 62 99 60 61 30 77 66 84 72 80 78 95 98 35 88 95 28 10 95 71 43 1 96 62 91 74 70 10 77 30 10 99 27 59 51 45 90 17 68 20 21 7 78 10 91 65 61 51 67 49 12 48 49 95 9
Number of Comarioson in Bubbele Sort:= 4950 number of swap=:2204
Number of Comarioson in Quick Sort:= 645 number of swap=:314
BUILD SUCCESSFUL (total time: 1 second)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.