Bubble Sort algorithm

  • english


Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list of elements, comparing adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted.

Here’s a step-by-step explanation of how Bubble Sort works:

  1. Comparison and Swapping: The algorithm starts at the beginning of the list and compares the first two elements. If the first element is greater than the second, they are swapped. If not, they remain in their current order.
  1. Iterative Passes: The algorithm then moves to the next pair of elements, compares them, and swaps if necessary. This process continues until the algorithm reaches the end of the list.
  2. One Pass Completes: After completing one pass through the list, the largest unsorted element (the maximum) is guaranteed to be at the end of the list.
  3. Repeat Until Sorted: Steps 1-3 are repeated for each element in the list. After each pass, the next largest unsorted element is moved to its correct position.
  4. Optimization: The algorithm can be optimized by recognizing that after each pass, the largest element is in its final position. Therefore, the algorithm does not need to consider it in subsequent passes.
  5. Termination: The process continues until no more swaps are needed during a pass, indicating that the entire list is now sorted.

Bubble Sort is not the most efficient sorting algorithm, especially for large datasets, as its time complexity in big O notation is O(n^2).

Array: [64,34,25,12,22,11,90]

Now, let’s go through the steps of the Bubble Sort algorithm:

Pass 1:

  • Compare 64 and 34 (swap): 34,64,25,12,22,11,90
  • Compare 64 and 25 (swap): 34,25,64,12,22,11,90
  • Compare 64 and 12 (swap): 34,25,12,64,22,11,90
  • Compare 64 and 22 (swap): 34,25,12,22,64,11,90
  • Compare 64 and 11 (swap): 34,25,12,22,11,64,90
  • Compare 64 and 90 (no swap): 34,25,12,22,11,64,90

Now, the largest element (90) is in its correct position at the end of the array.

Pass 2:

  • Compare 34 and 25 (swap): 25,34,12,22,11,64,90
  • Compare 34 and 12 (swap): 25,12,34,22,11,64,90
  • Compare 34 and 22 (swap): 25,12,22,34,11,64,90
  • Compare 34 and 11 (swap): 25,12,22,11,34,64,90

Now, the second largest element (64) is in its correct position.

Pass 3:

  • Compare 25 and 12 (swap): 12,25,22,11,34,64,90
  • Compare 25 and 22 (swap): 12,22,25,11,34,64,90
  • Compare 25 and 11 (swap): 12,22,11,25,34,64,90

Now, the third largest element (25) is in its correct position.

Pass 4:

  • Compare 22 and 11 (swap): 12,11,22,25,34,64,90

Now, the fourth largest element (22) is in its correct position.

Pass 5:

  • No swaps needed, the array is already sorted.

The final sorted array is 11,12,22,25,34,64,90

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("Unsorted Array: ");
        printArray(array);

        bubbleSort(array);

        System.out.println("\nSorted Array: ");
        printArray(array);
    }

    // Function to perform the bubble sort
    static void bubbleSort(int[] arr) {
        int n = arr.length;

        // Outer loop for each pass
        for (int i = 0; i < n-1; i++) {

            // Inner loop for each comparison in the pass
            for (int j = 0; j < n-i-1; j++) {

                // Compare adjacent elements and swap if they are in the wrong order
                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;
                }
            }
        }
    }

    // Utility function to print an array
    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Explanation of each part:

  1. public class BubbleSort {: Declares a class named BubbleSort.
  2. public static void main(String[] args) {: The main method where the program execution begins.
  3. int[] array = {64, 34, 25, 12, 22, 11, 90};: Initializes an array with unsorted values.
  4. System.out.println("Unsorted Array: ");: Prints a message indicating the array is unsorted.
  5. printArray(array);: Calls a function to print the unsorted array.
  6. bubbleSort(array);: Calls the function to perform the Bubble Sort on the array.
  7. System.out.println("\nSorted Array: ");: Prints a message indicating the array is sorted.
  8. printArray(array);: Calls a function to print the sorted array.
  9. static void bubbleSort(int[] arr) {: Defines the function to perform the Bubble Sort.
  10. int n = arr.length;: Gets the length of the array.
  11. for (int i = 0; i < n-1; i++) {: Outer loop for each pass through the array.
  12. for (int j = 0; j < n-i-1; j++) {: Inner loop for each comparison in the pass.
  13. if (arr[j] > arr[j+1]) {: Compares adjacent elements.
  14. int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;: Swaps the elements if they are in the wrong order.
  15. static void printArray(int[] arr) {: Defines the function to print an array.
  16. for (int value : arr) { System.out.print(value + " "); }: Prints each element of the array.
  17. System.out.println();: Moves to the next line after printing the array.