(JAVA) We will look at the behavior of three different sorts on randomly generat
ID: 3593597 • Letter: #
Question
(JAVA)
Explanation / Answer
source Code:
-----------------------------
package tasks;
import java.util.Random;
import java.util.Scanner;
public class Sorting_Analysis
{
public int bubble_count=0;
public int quick_count=0;
public int insertion_count=0;
public void quick(int[] array)
{
quickSort(array, 0, array.length - 1);
}
public void quickSort(int array[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = array[(low + high) / 2];
while (i <= j)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
quick_count++;
i++;
j--;
}
}
if (low < j)
quickSort(array, low, j);
if (i < high)
quickSort(array, i, high);
}
public void insertionSort(int arr[])
{
int N = arr.length;
int i, j, temp;
for (i = 0; i< N; i++)
{
j = i;
temp = arr[i];
while (j >0 && temp < arr[j-1])
{
arr[j] = arr[j-1];
j = j-1;
insertion_count++;
}
arr[j] = temp;
}
}
public void bubblesort(int array[])
{
int temp;
int length=array.length;
for(int i=0;i<length;i++)
{
for(int j=i+1;j<length;j++)
{
if(array[i]<array[j])
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
bubble_count++;
}
}
}
}
public static void main(String[] args)
{
Sorting_Analysis obj=new Sorting_Analysis();
Random t = new Random();
int array[] =new int[11];
int[] insertion_input =new int[10];
int[] quick_sort=new int[10];
int[] bubble_sort=new int[10];
Scanner sc = new Scanner(System.in);
for (int i=0;i<10;i++)
{
array[i]=t.nextInt(100);
insertion_input[i]=array[i];
quick_sort[i]=array[i];
bubble_sort[i]=array[i];
}
System.out.println("----------------------------");
System.out.println("***Performing Bubble sort***");
System.out.println("The Elements Before Sorting");
for(int i=0;i<10;i++)
{
System.out.print(" "+array[i]);
}
System.out.println(" The Elements After sorting");
obj.bubblesort(bubble_sort);
for(int i=0;i<10;i++)
{
System.out.print(" "+bubble_sort[i]);
}
int bubble=obj.bubble_count;
System.out.println(" The No of Comparisons made by Bubble Sort is:"+obj.bubble_count);
System.out.println("----------------------------");
System.out.println(" ***Performing Insertion Sort****");
System.out.println("The Elements Before Sorting");
for(int i=0;i<10;i++)
{
System.out.print(" "+insertion_input[i]);
}
obj.insertionSort(insertion_input);
System.out.println(" The Elements After sorting");
for(int i=0;i<10;i++)
{
System.out.print(" "+insertion_input[i]);
}
int insert=obj.insertion_count;
System.out.println(" The No of Comparisons made by Insertion Sort is:"+obj.insertion_count);
System.out.println("----------------------------");
System.out.println(" ***Performing Quick Sort****");
System.out.println(" The Elements Before Sorting");
for(int i=0;i<10;i++)
{
System.out.print(" "+quick_sort[i]);
}
System.out.println(" The Elements After sorting");
obj.quick(quick_sort);;
for(int i=0;i<10;i++)
{
System.out.print(" "+quick_sort[i]);
}
int quick=obj.quick_count;
System.out.println(" The No of Comparisons made by Quick Sort is:"+obj.quick_count);
System.out.println("----------------------------");
System.out.println(" 2nd Part: ");
int array2[] =new int[101];
int[] insertion_input2 =new int[100];
int[] quick_sort2=new int[100];
int[] bubble_sort2=new int[100];
for (int i=0;i<100;i++)
{
array2[i]=t.nextInt(100);
insertion_input2[i]=array2[i];
quick_sort2[i]=array2[i];
bubble_sort2[i]=array2[i];
}
System.out.println("----------------------------");
System.out.println("***Performing Bubble sort***");
System.out.println("The Elements Before Sorting");
for(int i=0;i<100;i++)
{
System.out.println(array2[i]);
}
System.out.println("The Elements Before Sorting");
for(int i=0;i<100;i++)
{
System.out.println(array2[i]);
}
System.out.println(" The Elements After sorting");
obj.bubblesort(bubble_sort2);
for(int i=0;i<100;i++)
{
System.out.println(bubble_sort2[i]);
}
bubble=bubble+obj.bubble_count;
System.out.println(" The No of Comparisons made by Bubble Sort is:"+obj.bubble_count);
System.out.println("----------------------------");
System.out.println(" ***Performing Insertion Sort****");
System.out.println("The Elements Before Sorting");
for(int i=0;i<100;i++)
{
System.out.println(insertion_input2[i]);
}
obj.insertionSort(insertion_input2);
System.out.println(" The Elements After sorting");
for(int i=0;i<100;i++)
{
System.out.println(insertion_input2[i]);
}
insert=insert+obj.insertion_count;
System.out.println(" The No of Comparisons made by Insertion Sort is:"+obj.insertion_count);
System.out.println("----------------------------");
System.out.println(" ***Performing Quick Sort****");
System.out.println(" The Elements Before Sorting");
for(int i=0;i<10;i++)
{
System.out.println(quick_sort2[i]);
}
System.out.println(" The Elements After sorting");
obj.quick(quick_sort2);;
for(int i=0;i<100;i++)
{
System.out.println(quick_sort2[i]);
}
quick=quick+obj.quick_count;
System.out.println(" The No of Comparisons made by Quick Sort is:"+obj.quick_count);
System.out.println("----------------------------");
System.out.println(" ");
bubble=bubble/2;
insert=insert/2;
quick=quick/2;
System.out.println( "The Average No of Comparisons For Bubble sortis:"+bubble);
System.out.println("The Average No of Comparisons For Insertion sort is"+insert);
System.out.println("The Average No of Comparisons For Quick sort is"+quick);
}
}
Sample output:
----------------------------
----------------------------
***Performing Bubble sort***
The Elements Before Sorting
41 63 55 11 25 81 46 17 2 89
The Elements After sorting
89 81 63 55 46 41 25 17 11 2
The No of Comparisons made by Bubble Sort is:21
----------------------------
***Performing Insertion Sort****
The Elements Before Sorting
41 63 55 11 25 81 46 17 2 89
The Elements After sorting
2 11 17 25 41 46 55 63 81 89
The No of Comparisons made by Insertion Sort is:24
----------------------------
***Performing Quick Sort****
The Elements Before Sorting
41 63 55 11 25 81 46 17 2 89
The Elements After sorting
2 11 17 25 41 46 55 63 81 89
The No of Comparisons made by Quick Sort is:12
----------------------------
2nd Part:
----------------------------
***Performing Bubble sort***
The Elements Before Sorting
78
31
61
64
8
69
59
64
95
40
64
86
59
4
69
19
21
90
99
4
23
87
29
84
48
2
11
92
5
47
0
42
31
14
63
13
21
39
76
56
3
97
53
81
73
71
40
10
17
25
91
76
96
48
71
13
4
20
23
56
83
92
17
63
28
42
31
97
71
52
88
42
59
63
78
0
4
66
96
68
95
3
68
14
19
82
82
85
22
83
65
35
84
3
80
25
56
38
2
5
The Elements Before Sorting
78
31
61
64
8
69
59
64
95
40
64
86
59
4
69
19
21
90
99
4
23
87
29
84
48
2
11
92
5
47
0
42
31
14
63
13
21
39
76
56
3
97
53
81
73
71
40
10
17
25
91
76
96
48
71
13
4
20
23
56
83
92
17
63
28
42
31
97
71
52
88
42
59
63
78
0
4
66
96
68
95
3
68
14
19
82
82
85
22
83
65
35
84
3
80
25
56
38
2
5
The Elements After sorting
99
97
97
96
96
95
95
92
92
91
90
88
87
86
85
84
84
83
83
82
82
81
80
78
78
76
76
73
71
71
71
69
69
68
68
66
65
64
64
64
63
63
63
61
59
59
59
56
56
56
53
52
48
48
47
42
42
42
40
40
39
38
35
31
31
31
29
28
25
25
23
23
22
21
21
20
19
19
17
17
14
14
13
13
11
10
8
5
5
4
4
4
4
3
3
3
2
2
0
0
The No of Comparisons made by Bubble Sort is:1710
----------------------------
***Performing Insertion Sort****
The Elements Before Sorting
78
31
61
64
8
69
59
64
95
40
64
86
59
4
69
19
21
90
99
4
23
87
29
84
48
2
11
92
5
47
0
42
31
14
63
13
21
39
76
56
3
97
53
81
73
71
40
10
17
25
91
76
96
48
71
13
4
20
23
56
83
92
17
63
28
42
31
97
71
52
88
42
59
63
78
0
4
66
96
68
95
3
68
14
19
82
82
85
22
83
65
35
84
3
80
25
56
38
2
5
The Elements After sorting
0
0
2
2
3
3
3
4
4
4
4
5
5
8
10
11
13
13
14
14
17
17
19
19
20
21
21
22
23
23
25
25
28
29
31
31
31
35
38
39
40
40
42
42
42
47
48
48
52
53
56
56
56
59
59
59
61
63
63
63
64
64
64
65
66
68
68
69
69
71
71
71
73
76
76
78
78
80
81
82
82
83
83
84
84
85
86
87
88
90
91
92
92
95
95
96
96
97
97
99
The No of Comparisons made by Insertion Sort is:2471
----------------------------
***Performing Quick Sort****
The Elements Before Sorting
78
31
61
64
8
69
59
64
95
40
The Elements After sorting
0
0
2
2
3
3
3
4
4
4
4
5
5
8
10
11
13
13
14
14
17
17
19
19
20
21
21
22
23
23
25
25
28
29
31
31
31
35
38
39
40
40
42
42
42
47
48
48
52
53
56
56
56
59
59
59
61
63
63
63
64
64
64
65
66
68
68
69
69
71
71
71
73
76
76
78
78
80
81
82
82
83
83
84
84
85
86
87
88
90
91
92
92
95
95
96
96
97
97
99
The No of Comparisons made by Quick Sort is:209
----------------------------
The Average No of Comparisons For Bubble sortis:865
The Average No of Comparisons For Insertion sort is1247
The Average No of Comparisons For Quick sort is110
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.