Bubble sort compares adjacent elements and swaps them if they are in the wrong order.
Bubble sort time and space complexity
The algorithm is named for the way smaller or larger elements “bubble” to the top of the list. Time complexity is O(n 2) average and worst. The bubble sort is slow. It is only for beginners to explore the sorting techniques. The space complexity is O(1).
Implement bubble sort
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.Arrays; public class BubbleSort { //Solution 1, Time worst and average O(n^2), Space O(1), n is array length public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) swap(arr, j, j+1); } } } //Solution 2, Use a flag to skip the remaining passes. //Time worst O(n^2) Best O(n), Space O(1) public static void bubbleSortBetter(int[] arr) { boolean swapped = true; int last = arr.length - 1; while (swapped) { swapped = false; for (int i = 0; i < last; i++) { if (arr[i] > arr[i+1]) { swap(arr, i, i+1); swapped = true; } } } } //Swap two elements by index, Time O(1), Space O(1) private static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { int[] a = {19, 33, 4 , 61, 5, 38, -36, 21, 0}; //Solution 1, Simple bubbleSort(a); System.out.print("Bubber sort (simple): "); System.out.println(Arrays.toString(a)); //Solution 2, Use flag int[] b = {19, 33, 4 , 61, 5, 38, -36, 21, 0}; bubbleSortBetter(b); System.out.print("Bubber sort (better): "); System.out.println(Arrays.toString(b)); } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
//Solution 1, Time worst and average O(n^2), Space O(1), n is array length function bubbleSort(arr) { var n = arr.length; for (let i = 0; i < n; i++) { for (let j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) swap(arr, j, j+1); } } } //Solution 2, Use a flag to skip the remaining passes. //Time worst O(n^2), Best O(n), Space O(1) function bubbleSortBetter(arr) { var swapped = true; var last = arr.length - 1; while (swapped) { swapped = false; for (let i = 0; i < last; i++) { if (arr[i] > arr[i+1]) { swap(arr, i, i+1); swapped = true; } } } } //Swap two elements by index, Time O(1), Space O(1) function swap(arr, i, j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } let array = [1, 45, 7, 2, 54, 7]; //Solution 1, Simple bubbleSort(array); console.log("Bubber sort (simple): "); console.log(array); let b = [1, 45, 7, 2, 54, 7]; bubbleSortBetter(b); console.log("Bubber sort (better): "); console.log(b); |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#Solution 1, Time worst and average O(n^2), Space O(1), n is array length def bubbleSort(arr) : n = len(arr) for i in range(0, n) : for j in range (0, n-i-1) : if arr[j] > arr[j+1]: swap(arr, j, j+1) #Solution 2, Use a flag to skip the remaining passes. #Time worst O(n^2), Best O(n), Space O(1) def bubbleSortBetter(arr) : swapped = True last = len(arr) - 1 while (swapped) : swapped = False for i in range(0, last, 1) : if arr[i] > arr[i+1] : swap(arr, i, i+1) swapped = True #Swap two elements by index, Time O(1), Space O(1) def swap(arr, i, j) : tmp = arr[i] arr[i] = arr[j] arr[j] = tmp array = [1, 45, 7, 2, 54, 7] #Solution 1, Simple bubbleSort(array) print("Bubber sort (simple): ") print(array) b = [1, 45, 7, 2, 54, 7] bubbleSortBetter(b) print("Bubber sort (better): ") print(b) |
Doodle
Free download
Download Java, JavaScript and Python code
View how bubble sort in action
Sorting doodles compilation (YouTube)
Can you explain Bubble sort in one sentence?
Bubble sort compares adjacent elements and swaps them if they are in the wrong order.