Iterative Bubble Sort in Java

Overview

The bubble sort algorithm sorts an array by swapping adjacent elements until it is fully sorted. Bubble sort can be O(n) or O(n²) depending on the array being sorted.

Implementation

public static void bubbleSortIterative(int[] arr) {
  for (int step = 0; step < arr.length - 1; step++) {
    for (int curIndex = 0; curIndex < arr.length - 1 - step; curIndex++) {
      if (arr[curIndex] > arr[curIndex + 1]) {
        int firstVal = arr[curIndex];
        arr[curIndex] = arr[curIndex + 1];
        arr[curIndex + 1] = firstVal;
      }
    }
  }
}

public static void: Bubble sort mutates the array parameter that is passed in, therefore we do not return an array. Instead, the array that is passed to the sort method will be changed directly.

int[] arr: Takes an array as a paramater called arr.

for (int step = 0; ... step++): Loops through the array multiple times until the array is fully sorted. At the end of each iteration/step, the next highest element will be sorted.

step < arr.length - 1;: prevents the array from doing an uneccessary loop. On the last iteration, there will only be 1 element to sort left, which means it will already be in the correct position. We can subtract 1 from array.length to remove the final iteration that isn't needed.

for (int curIndex = 0; ... curIndex++): loops through the entire unsorted portion of the array.

curIndex < arr.length - 1 - step;: this prevents unnecessary iterations by not looping through the sorted part of the array. Bubble sort only focuses on unsorted elements. After each step, the sorted elements would be the final elements of the array. This means that we can loop through the unsorted elements by subtracting steps from it.

Bubble sort always focuses on the current element, and the next element. So on the 2nd to last iteration for curIndex, the last element would be sorted. We can remove checking the last element by subtracting 1 from array.length - step

if (arr[curIndex] > arr[curIndex + 1]): Gets the value of the current element and the next element. If the first element's value is greater, then it will swap the two.

int firstVal = arr[curIndex];: Temporarily stores the value of the current element.

arr[curIndex] = arr[curIndex + 1]; Sets the value of the first element to the value of the next element. At this point the current element and the next element are the same value.

arr[curIndex + 1] = firstVal;: Sets the value of the next element to the original first value. This effectively swaps the value of both elements.

Optimizing Bubble Sort

"Right now, the algorithm is O(n²). If a sorted array is passed in, then it will loop through it n² times.

If the array ends up being sorted early, we can just end the bubble sort since there is nothing more to sort. We can tell if an array is sorted if we did not swap any elements during an iteration / step.

public static void bubbleSortIterative(int[] arr) {
  for (int step = 0; step < arr.length - 1; step++) {
    int swaps = 0;
    for (int curIndex = 0; curIndex < arr.length - 1 - step; curIndex++) {
      if (arr[curIndex] > arr[curIndex + 1]) {
        int firstVal = arr[curIndex];
        arr[curIndex] = arr[curIndex + 1];
        arr[curIndex + 1] = firstVal;
        swaps++;
      }
    }

    if (swaps == 0) {
      break;
    }
  }
}

int swaps = 0;: Sets the swaps to equal 0 each iteration / step. Each iteration, we want to count the amount of swaps happen. If it goes through an iteration with no swaps, we will stop the algorithm.

swaps++;: Increments swaps by 1 every time a swap occurs. Keep in mind swap becomes 0 each time it navigates through the array.

if (swaps == 0): A conditional that checks if no swaps have happened during the current iteration. This code is called after each iteration.

break;: Ends the current loop. Since this code is within the steps loop, the entire function is done.