Home > database >  Can someone explain me this bubble sort code?
Can someone explain me this bubble sort code?

Time:05-08

so I'm practicing algorithms and I understand how bubble sort work but I'm kinda lost on this code btw this is not my code

public class Main{
    
    // bubble sort = pairs of adjacent elements are compared, and the elements
    //                  swapped if they are not in order.
    
    //               Quadratic time O(n^2)
    //               small data set = okay-ish
    //               large data set = BAD (plz don't)
    
    public static void main(String[] args) {
        
        int array[] =  {9, 1, 8, 2, 7, 3, 6, 4, 5};
        
        bubbleSort(array);
        
        for(int i : array) {
            System.out.print(i);
        }
    }
    
    public static void bubbleSort(int array[]) {
        
        for(int i = 0; i < array.length - 1; i  ) {
            for(int j = 0; j < array.length - i - 1; j  ) {
                if(array[j] > array[j 1]) {
                    int temp = array[j];
                    array[j] = array[j 1];
                    array[j 1] = temp;
                }
            }
        }
    }
}

CodePudding user response:

In The code you provided the bubble sort simply pushes the maximum in the iteration number to the last right before the number bigger than it because that is the end of the inner loop where the condition (array.length - i - 1), by swaping two adjacent numbers of the first is bigger than the second.

These are the iterations:

intial: [9, 1, 8, 2, 7, 3, 6, 4, 5] // the array
Iteration 1: [1, 8, 2, 7, 3, 6, 4, 5, 9] // pushes 9 to the last
Iteration 2: [1, 2, 7, 3, 6, 4, 5, 8, 9] // pushes 8 right before 9 because it not bigger than so it can't swap them
Iteration 3: [1, 2, 3, 6, 4, 5, 7, 8, 9] // pushes 7 right before 8 because it not bigger than so it can't swap them
Iteration 4: [1, 2, 3, 4, 5, 6, 7, 8, 9] // pushes 6 right before 7 because it not bigger than so it can't swap them
Iteration 5: [1, 2, 3, 4, 5, 6, 7, 8, 9] // the numbers are now sorted this is just case where a different array would not be sorted by now it depends on how the array elements are placed at the start 
Iteration 6: [1, 2, 3, 4, 5, 6, 7, 8, 9] // sorted
Iteration 7: [1, 2, 3, 4, 5, 6, 7, 8, 9] // sorted
Iteration 8: [1, 2, 3, 4, 5, 6, 7, 8, 9] // sorted
Iteration 9: [1, 2, 3, 4, 5, 6, 7, 8, 9] // sorted

This is Bubble sort visualization which may help you to understand the sort a bit more link.

But if you are more into reading here an article about it link.

CodePudding user response:

Code with comments:

public static void bubbleSort(int array[]) {
    // look at each array element from start to end (outer loop)   
    for(int i = 0; i < array.length - 1; i  ) { 
        // for each outer element loop over all earlier unsorted elements (inner loop)
        // first iteration bubbles largest element to the end
        // second iteration bubbles second largest just before largest element
        for(int j = 0; j < array.length - i - 1; j  ) {
            // bubble bigger elements upwards
            if(array[j] > array[j 1]) { // element bigger than next
                // swap elements
                int temp = array[j]; // save left element
                array[j] = array[j 1]; // store right element to left side
                array[j 1] = temp; // store left element to right
            }
        }
    }
}

Code with output instructions:

import java.util.Arrays;
public class Main{
    public static void main(String[] args) {
        int array[] =  {9, 1, 8, 2, 7, 3, 6, 4, 5};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void bubbleSort(int array[]) {
        System.out.println(Arrays.toString(array));
        for(int i = 0; i < array.length - 1; i  ) {
            System.out.print("i: "   i   " array[i]: "   array[i]);
            for(int j = 0; j < array.length - i - 1; j  ) {
                if(array[j] > array[j 1]) {
                    int temp = array[j];
                    array[j] = array[j 1];
                    array[j 1] = temp;
                }
            }
            System.out.println(" -> "   Arrays.toString(array));
        }
    }
}

Output:

$ java Main.java
[9, 1, 8, 2, 7, 3, 6, 4, 5]
i: 0 array[i]: 9 -> [1, 8, 2, 7, 3, 6, 4, 5, 9]
i: 1 array[i]: 8 -> [1, 2, 7, 3, 6, 4, 5, 8, 9]
i: 2 array[i]: 7 -> [1, 2, 3, 6, 4, 5, 7, 8, 9]
i: 3 array[i]: 6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
i: 4 array[i]: 5 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
i: 5 array[i]: 6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
i: 6 array[i]: 7 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
i: 7 array[i]: 8 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
  •  Tags:  
  • java
  • Related