Bubble sort in java

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The process is called "bubbling" because smaller or larger elements gradually "bubble" to their correct positions.

Here's a step-by-step explanation of how the bubble sort algorithm works:

1. Start with an unsorted list of elements.

2. Compare the first pair of adjacent elements in the list.

3. If the elements are in the wrong order (e.g., the first element is greater than the second element), swap them.

4. Move to the next pair of adjacent elements and repeat the comparison and swapping process.

5. Continue this process until you reach the end of the list. At this point, the largest element in the unsorted portion of the list will "bubble" to the end of the list.

6. Repeat steps 2 to 5 for the remaining unsorted portion of the list. After each iteration, the next largest element will "bubble" to its correct position.

7. Repeat the process until the entire list is sorted, i.e., there are no more swaps needed during an iteration.

Here's an example to illustrate the bubble sort algorithm:

Let's say we have an unsorted list: [5, 3, 8, 2, 1]

1. First iteration:

   • Compare 5 and 3: 5 > 3, so swap them. List becomes [3, 5, 8, 2, 1]

   • Compare 5 and 8: 5 < 8, no swap. List remains [3, 5, 8, 2, 1]

   • Compare 8 and 2: 8 > 2, so swap them. List becomes [3, 5, 2, 8, 1]

   • Compare 8 and 1: 8 > 1, so swap them. List becomes [3, 5, 2, 1, 8] The largest element (8) has "bubbled" to the end of the list.

2. Second iteration:

   • Compare 3 and 5: 3 < 5, no swap. List remains [3, 5, 2, 1, 8]

   • Compare 5 and 2: 5 > 2, so swap them. List becomes [3, 2, 5, 1, 8]

   • Compare 5 and 1: 5 > 1, so swap them. List becomes [3, 2, 1, 5, 8] The second largest element (5) has "bubbled" to its correct position.

3. Third iteration:

   • Compare 3 and 2: 3 > 2, so swap them. List becomes [2, 3, 1, 5, 8]

   • Compare 3 and 1: 3 > 1, so swap them. List becomes [2, 1, 3, 5, 8] The third largest element (3) has "bubbled" to its correct position.

4. Fourth iteration:

   • Compare 2 and 1: 2 > 1, so swap them. List becomes [1, 2, 3, 5, 8] The fourth largest element (2) has "bubbled" to its correct position.

5. Fifth iteration: No swaps are needed since the list is already sorted.

The final sorted list is [1, 2, 3, 5, 8].

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int arr[] = {4,3,5,2,5,3,2,5,5,4,2,2,4,5,1,7,9,7,5,1};
        bubbleSort(arr);
        printArray(arr);
    }
    public static int[] bubbleSort(int[] arr) {
        System.out.println("Sort.bubbleSort() time complexity: n^2");
        for(int i=0; i<arr.length; i++) 
            for(int j = 0; j<arr.length-i-1; j++)
                if(arr[j]>arr[j+1]){
                    //swap the values
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }        
        return arr;
    }
    public static void printArray(int[] outputArr) {
        System.out.println(Arrays.toString(outputArr));        
    }
}