Write a Bubble Sort program that sorts the given input array in descending order and prints the number of swaps made after m passes in the algorithm.
Sample Input 1:
2
4
1 2 3 4
Sample Output 1:
5
Explanation 1:
Here, m = 2. Thus, we need to calculate the number of swaps that are done after 2 passes of bubble sort.
Given array is: 1 2 3 4
We need to sort the array in descending order, i.e. 4 3 2 1.
For sorting the given array in descending order, the iterations would look like:
Iteration 1:
Swap 1: 2 1 3 4 (2 > 1)
Swap 2: 2 3 1 4 (3 > 1)
Swap 3: 2 3 4 1 (4 > 1)
Now, iteration 1 is complete as 1 is at its right position.
Iteration 2:
Swap 1: 3 2 4 1 (3 > 2)
Swap 2: 3 4 2 1 (4 > 2)
Now, iteration 2 is complete.
Thus, the total number of swaps after 2 iterations is: 3 + 2 = 5.
import java.util.Scanner;
class Source {
static int totalBubbleSortSwaps(int[] array, int m) {
int pass=0;
boolean isDone;
for (int k = 0; k < ( array.length-1 ); k++) {
isDone=true;
for (int j = 0; j < array.length-k-1; j++) {
if (array[j] < array[j+1])
{
//isDone=false;
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
pass++;
}
}
if(isDone){
break;
}
}
//for (pass =1; pass <m; ++pass){
//for (k = 0; k < size; k++)
return pass;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int size = scanner.nextInt();
int array[] = new int[size];
for (int i = 0; i < size; i++) {
array[i] = scanner.nextInt();
}
System.out.println(totalBubbleSortSwaps(array, m));
}
}
Please help me in solving the Bubble Sort Problem. Here I run the program but I am getting 6 in place of 5.
0 Answer(s)