Bubble sort
|
|
Bubble 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 of the list via the swaps.
Bubble sort needs O(<math>n^2<math>) comparisons to sort <math>n<math> 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.
Bubble sort is asymptotically equivalent in running time to insertion sort, but the two algorithms differ greatly in the number of swaps necessary. In the worst case, bubble sort will require <math>O(n^2)<math> swaps, while insertion sort will require at most <math>O(n)<math> swaps. Nave implementations of bubble sort (like those below) usually perform badly on already-sorted lists (<math>O(n^2)<math>), while insertion sort needs only <math>O(n)<math> operations in this case. Hence many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort. It is possible to reduce the best case complexity to <math>O(n)<math> if a flag is used to denote whether any swaps were necessary during the first run of the inner loop. In this case, no swaps would indicate an already sorted list. Also, reversing the order in which the list is traversed for each pass improves the efficiency somewhat. This is sometimes called shuttle sort since the algorithm shuttles from one end of the list to the other.
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.
Due to its simplicity, the bubble sort is often used to introduce the concept of an algorithm to introductory programming students.
Code
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 1 {
for j from 1 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}
For implementations in real programming languages, see Wikisource.
See also
- Bubble sort animation (http://olli.informatik.uni-oldenburg.de/fpsort/Animation.html)de:Bubblesort
es:Bubblesort fr:Tri bulles it:Bubble sort lt:Burbulo rūšiavimo algoritmas nl:Bubblesort ja:バブルソート pl:Sortowanie bąbelkowe pt:Bubble sort fi:Kuplalajittelu