Bubble sort - Misplaced Pages

This is an old revision of this page, as edited by 70.49.41.233 (talk) at 18:29, 4 August 2006 (→Performance). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 18:29, 4 August 2006 by 70.49.41.233 (talk) (→Performance)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Bubble sort, also known as exchange sort, is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. head) of the list via the swaps. Because it only uses comparisons to read elements, it is a comparison sort.

In more detail, the bubble sort algorithm works as follows:

Compare adjacent elements. If the first is greater than the second, swap them.
Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest.
Repeat the steps for all elements except the last one.
Keep repeating for one fewer element each time, until you have no more pairs to compare. (Alternatively, keep repeating until no swaps are needed.)

function bubblesort (A : list) {
    var int i, j;
    for i from n downto 1 {
        for j from 1 to i-1 { 
            if (A > A)
                swap(A, A)
        }
    }
}

Performance

Bubble sort needs $O(n^{2})$ comparisons to sort n items and can sort in-place. Although the algorithm is one of the simplest sorting algorithms to understand and implement, it is too inefficient for use on lists having more than a few elements. Even among simple $O(n^{2})$ sorting algorithms, algorithms like insertion sort are considerably more efficient.

Due to its simplicity, the bubble sort is often used to introduce the concept of an algorithm to introductory programming students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught. The Jargon file, which famously calls bogosort "he archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Don Knuth, in his famous The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Insertion sort needs only $O(n)$ operations if the list is already sorted, whereas naïve implementations of bubble sort (like the pseudocode above) require $O(n^{2})$ operations. (This can be reduced to $O(n)$ if code is added to stop the outer loop when the inner loop performs no swaps.) Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.

Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort.

Reversing the order in which the list is traversed for each pass improves the efficiency somewhat. This bi-directional bubblesort is sometimes called shuttle sort since the algorithm shuttles from one end of the list to the other.

Variations

Odd-even sort is a parallel version of bubblesort, for message passing systems.

References

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Problem 2-2, pg.38.
Sorting in the Presence of Branch Prediction and Caches

External links

Template:Wikibookschapter

Categories: