Sorting fundamentals #1: Bubble sort

What is bubble sort?

Bubble sort is a sorting algorithm in which we compare adjacent elements and swap their position if the element in the (i-1)th position is greater than the element at the i-th position. In this way, larger elements will bubble up to the end of the list.

Bubble sort is a stable sorting algorithm.

Bubble sort

Bubble sort performance

• Time complexity: O(n²)
• Space complexity: O(1)

Bubble sort implementation

void bubble_sort(int[] arr, int n) {
  for (int i = 0; i < n - 1; i++) {
     boolean isSwapped = false;
     for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         isSwapped = true;
        }
     }
     if (isSwapped == false)
      break;
    }
}

Subscribe to my Medium: https://medium.com/@exploreintellect/subscribe