Bubble Sort in Java

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.

Steps of Bubble Sort

1. Initialization:
   • Start with the first element in the array.
   • Assume the array has n elements.
2. Pass-Through the List:
   • For each element in the array (from the first to the second last):
     • Compare the current element with the next element.
     • If the current element is greater than the next element, swap them.
3. Repeat Passes:
   • Repeat the above step for all elements in the array.
   • After each pass, the largest unsorted element will have “bubbled up” to its correct position at the end of the array.
   • Decrease the range of comparison by one each time (since the last elements are already sorted).
4. Stop When Sorted:
   • Continue repeating the passes until no more swaps are needed (i.e., the array is sorted).

Detailed Example

Let’s sort the array [64, 34, 25, 12, 22, 11, 90] using Bubble Sort.

Initial Array:

64, 34, 25, 12, 22, 11, 90

Pass 1:

• Compare 64 and 34. Swap because 64 > 34.
• Compare 64 and 25. Swap because 64 > 25.
• Compare 64 and 12. Swap because 64 > 12.
• Compare 64 and 22. Swap because 64 > 22.
• Compare 64 and 11. Swap because 64 > 11.
• Compare 64 and 90. Do not swap because 64 < 90.

Array after Pass 1:

34, 25, 12, 22, 11, 64, 90

Pass 2:

• Compare 34 and 25. Swap because 34 > 25.
• Compare 34 and 12. Swap because 34 > 12.
• Compare 34 and 22. Swap because 34 > 22.
• Compare 34 and 11. Swap because 34 > 11.
• Compare 34 and 64. Do not swap because 34 < 64.
• (90 is already in its correct position)

Array after Pass 2:

25, 12, 22, 11, 34, 64, 90

Pass 3:

• Compare 25 and 12. Swap because 25 > 12.
• Compare 25 and 22. Swap because 25 > 22.
• Compare 25 and 11. Swap because 25 > 11.
• Compare 25 and 34. Do not swap because 25 < 34.
• (64 and 90 are already in their correct positions)

Array after Pass 3:

12, 22, 11, 25, 34, 64, 90

Pass 4:

• Compare 12 and 22. Do not swap because 12 < 22.
• Compare 22 and 11. Swap because 22 > 11.
• Compare 22 and 25. Do not swap because 22 < 25.
• (34, 64, and 90 are already in their correct positions)

Array after Pass 4:

12, 11, 22, 25, 34, 64, 90

Pass 5:

• Compare 12 and 11. Swap because 12 > 11.
• Compare 12 and 22. Do not swap because 12 < 22.
• (25, 34, 64, and 90 are already in their correct positions)

Array after Pass 5:

11, 12, 22, 25, 34, 64, 90

Pass 6:

• Compare 11 and 12. Do not swap because 11 < 12.
• (22, 25, 34, 64, and 90 are already in their correct positions)

Array after Pass 6:

11, 12, 22, 25, 34, 64, 90

Since no swaps were made during the last pass, the array is now sorted.

Final Sorted Array:

11, 12, 22, 25, 34, 64, 90

Bubble Sort Java Code

public class BubbleSort {

    // Function to implement bubble sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length; // Get the length of the array
        for (int i = 0; i < n - 1; i++) { // Outer loop for number of passes
            for (int j = 0; j < n - 1 - i; j++) { // Inner loop for each pass
                if (arr[j] > arr[j + 1]) { // Compare adjacent elements
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Main method to test the bubble sort function
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90}; // Sample array
        System.out.println("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        bubbleSort(arr); // Call bubble sort function

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Code Explanation:

Function Definition:

• The bubbleSort function takes an array of integers arr as input.

Outer Loop:

• for (int i = 0; i < n - 1; i++): This loop runs for n-1 passes, where n is the length of the array. Each pass moves the largest unsorted element to its correct position.

Inner Loop:

• for (int j = 0; j < n - 1 - i; j++): This loop runs within each pass to compare and swap adjacent elements. The -i part reduces the range of comparison as the largest elements get sorted and placed at the end of the array.

Comparison and Swap:

• if (arr[j] > arr[j + 1]): This condition checks if the current element is greater than the next element.
• If true, the elements are swapped using a temporary variable temp.

Main Method:

• An array arr is defined with sample values.
• The original array is printed.
• The bubbleSort function is called to sort the array.
• The sorted array is printed.

OUTPUT:

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

Bubble Sort Key Points

• Time Complexity: O(n^2) in the worst and average case.
• Space Complexity: O(1) (in-place sorting).
• Stability: Bubble Sort is stable, meaning that it maintains the relative order of equal elements.

Bubble Sort is easy to understand and implement, but it is not suitable for large datasets due to its inefficiency.