home | news | contact | about
Bubble Sort
17 July 2009, 06:05 PM
Often taught as introductory material in classes, bubble sort is an elementary sorting algorithm that relies on brute force. The algorithm works in a way that it keep passing through the array of interest, exchanging adjacent elements if necessary, and when there is no more elements exchanged, the array is sorted. This algorithm is now considered as a deprecated method so try avoiding it even for small problem with little elements. There are better elementary algorithms for instance the insertion sort or its improved cousin shellsort.


Applet: BubbleSort applet in slow motion.

The above applet shows how the algorithm exchanges elements in the array. If it isn't moving at all the sort might be completed. Click on the applet to restart the sort with new random elements. Once it starts, notice a red vertical line to the right, a blue vertical line on the left, and a yellow bar next to the blue line. As the blue line passes through the array it picks the tallest bar it encounters (change color to yellow) along the way and drag it towards the red line. In other words the next biggest element "bubbles" to the "surface". The applet also used something called swapped element check making it capable of stopping the search before the red line reaches the other side on the left. Without this check it will always reach there regardless of data fed into the algorithm. Bubble sort is an in-place algorithm so it uses the same input array as the output. By the time the sort ends, the same input array is then sorted.

Next is a Java implementation for bubble sort and is the same code used for the applet above. Wonder what that commented section is for? It is still a bubble sort except lacking the swapped element check and of slightly different structure. It's there only for reference, not an endorsement to use the other one. Personally, you shouldn't even consider bubble sort for actual production environment.

/**
 * Bubble sort data. Sorting is in-place.
 * @param data Array to sort.     
 */
public void bubbleSort(int[] data) {
    /*
    // this commented code is also a bubble sort w/o swapped-element check
    int v ;
    for (int i = data.length - 1; i >= 0; i--) {
        for (int j = 1; j <= i; j++) {
            if (data[j-1] > data[j]) {
                v = data[j-1] ;
                data[j-1] = data[j] ;
                data[j] = v ;
            }
        }
    }*/
    int v, n = data.length ;
    boolean swapped ;
    do {
        swapped = false ;
        n = n - 1 ;
        for (int i = 0; i < n; i++) {
            if (data[i] > data[i+1]) {
                v = data[i+1] ;
                data[i+1] = data[i] ;
                data[i] = v ;
                swapped = true ;
            }
        }
    } while (swapped) ;
}


Why should you use bubble sort?
- It is used only because it is popular otherwise don't use it.

Why not to use bubble sort?
- It is slower and not simpler than other elementary algorithm.
- There are other better elementary sorting:
Insertion sort
Shellsort
Last edited on 17 July 2009

Comments

Post a comment~
Name*
What is the first odd prime number?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.