Bubble Sort
17 July 2009, 06:05 PM
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~