Algorithm Divide_and_Conquer Sorting_Algorithms Bubble_Sort
Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. After each iteration, one more element will be sorted to the correct position.
Implementation
In this implementation the array is sorted in ascending order.
- Start from the beginning of the array, compare the first two elements. If the first element is greater than the second, swap them.
- Move to the next pair of the adjacent elements, and repeat the comparison, swap if necessary.
- Continue this process for
array.length
times.
After each inner loop iteration, the largest element will have “bubbled up” to its correct position at the end of the list.
public static void bubbleSort(int[] nums) {
// length-1 to avoid j+1 out of bound
for (int i=nums.length-1; i>0; i--) {
for (int j=0; j<i; j++) {
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
}
Performance optimisation
If there is no swap happen in an iteration, it suggests the array is already sorted, there is no need for further iterations. Use a flag to keep track of whether swap is happen in an iteration, if elements are swapped, set flag to true, false otherwise. Stop further iterations if the flag is false after one inner iteration.
public static void bubbleSortOptimised(int[] nums) {
boolean isSwapped = false;
for (int i=nums.length-1; i>0; i--) {
for (int j=0; j<i; j++) {
if (nums[j] > nums[j+1]) {
isSwapped = true;
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
if (!isSwapped) break;
}
}
Back to parent page: Data Structures and Algorithms