Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Bubble Sort Problem- Number of Passes

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 871
    Answer it

    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: 

    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)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: