SimuVedaAlgorithms Lab Open in the lab

Sorting / Beginner

Bubble Sort Visualizer

Walk through the array and swap any neighbors that are out of order. After each pass, the largest remaining value has bubbled to the end.

Start the Bubble Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n²)
Worst timeO(n²)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Bubble sort on 5 values. The largest value sinks to the right on every pass. [5, 1, 4, 2, 8]
  2. Pass 1.
  3. Compare 5 and 1.
  4. 5 is bigger, so swap them. [1, 5, 4, 2, 8]
  5. Compare 5 and 4.
  6. 5 is bigger, so swap them. [1, 4, 5, 2, 8]
  7. Compare 5 and 2.
  8. 5 is bigger, so swap them. [1, 4, 2, 5, 8]
  9. Compare 5 and 8.
  10. 8 is now in its final place.
  11. Pass 2.
  12. Compare 1 and 4.
  13. Compare 4 and 2.
  14. 4 is bigger, so swap them. [1, 2, 4, 5, 8]
  15. Compare 4 and 5.
  16. 5 is now in its final place.
  17. Pass 3.
  18. Compare 1 and 2.
  19. Compare 2 and 4.
  20. No swaps in pass 3, so the array is already sorted. Stop early.
  21. Sorted. 9 comparisons and 4 swaps.

Try it with your own input →

Bubble sort in Java, Python, C++, C and JavaScript

void bubbleSort(int[] a) {
  int n = a.length;
  for (int i = 0; i < n - 1; i++) {
    boolean swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        swap(a, j, j + 1);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
void bubbleSort(vector<int>& a) {
  int n = a.size();
  for (int i = 0; i < n - 1; i++) {
    bool swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        swap(a[j], a[j + 1]);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}
void bubbleSort(int a[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int swapped = 0;
    for (int j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
        swapped = 1;
      }
    }
    if (!swapped) break;
  }
}
function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}

In an interview

Interviewers like to ask how to make it stop early. The swapped flag does that, which is why the best case is O(n).

More sorting