Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order. Each pass of the algorithm iterates through the array and pushes the largest element to the end. This process is repeated until the array is fully sorted.

Algorithm Steps:

1. Start with the first element and compare it with the next element.
2. If the next element is smaller, swap the two elements.
3. Move to the next pair of elements and repeat step 2.
4. Repeat steps 1-3 for the remaining elements.
5. The largest element will move to the end in each pass, so the number of iterations is equal to the number of elements minus one.

Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst and average cases, where n is the number of elements in the array. This is because in each pass, we have to compare all adjacent pairs of elements. However, in the best case where the array is already sorted, the time complexity is O(n).

Example

Let's see an implementation of Bubble Sort in Java:

1${code}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Bubble Sort Algorithm

    int[] arr = {5, 2, 8, 12, 7};

    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {

      for (int j = 0; j < n - i - 1; j++) {

        if (arr[j] > arr[j + 1]) {

          // Swap elements

          int temp = arr[j];

          arr[j] = arr[j + 1];

          arr[j + 1] = temp;

        }

      }

    }

​

    // Print sorted array

    for (int i = 0; i < n; i++) {

      System.out.print(arr[i] + " ");

    }

  }

}