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.
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.
How to implement bubble sort in Java?
The implementation uses two nested for loop to compare two adjacent numbers in an array. If they are not ordered, swap their positions.
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)