Bubble Sort

AlgorithmDivide_and_ConquerSorting_AlgorithmsBubble_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.

1. Start from the beginning of the array, compare the first two elements. If the first element is greater than the second, swap them.
2. Move to the next pair of the adjacent elements, and repeat the comparison, swap if necessary.
3. 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