Bubble Sort Algorithm in Java

1. Introduction

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

2. Implementation Steps

1. Start at the beginning of the list.

2. Compare the first two elements.

3. If the first element is greater than the second, swap them.

4. Move to the next element and repeat the previous step.

5. Continue this process until a pass through the list requires no swaps.

3. Implementation in Java

public class BubbleSort {
    // Bubble Sort function
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no swaps happened, then the array is already sorted
            if (!swapped) break;
        }
    }
    // Function to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(arr);
        bubbleSort(arr);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output:

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

Explanation:

1. The bubbleSort function sorts an array using the Bubble Sort algorithm.

2. It contains two nested loops. The outer loop runs for n-1 times, where n is the length of the array.

3. The inner loop compares adjacent elements and swaps them if they're in the wrong order.

4. After each pass of the outer loop, the largest element bubbles up to the last position.

5. The variable swapped checks if any swapping operation took place in the inner loop. If no swaps occur during a complete iteration of the inner loop, the array is already sorted, and we break out of the outer loop.

6. printArray is a utility function to print the elements of an array.

7. The main function demonstrates the Bubble Sort algorithm on a sample array.


Comments