Bubble sort compares adjacent elements and swaps them if they are in the wrong order. The implementation uses two nested for loop to check two numbers in an array. The optimized solution uses a flag to skip the remaining passes. The bubble sort gif uses animations to explains the process.
How bubble sort works?
Bubble sort compares adjacent elements and swaps them if they are in the wrong order. The algorithm is named for the way smaller or larger elements “bubble” to the top of the list.
Bubble sort gif
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
Sorting doodles compilation (YouTube)