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 essentially equivalent in running time to insertion sort -- it compares and swaps the same pairs of elements, but in a different order. Naive 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 most modern algorithm textbooks strongly discourage use of the algorithm, or even avoid mentioning it, 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.
Implementations
sub bubble_sort(@) {
my @a = @_;
foreach $i (reverse 0..@#a) {
foreach $j (0..$i-1) {
($a[$j],$a[$j+1]) = ($a[$j+1],$a[$j]) if ($a[$j] > $a[$j+1]);
}
}
return @a;
}
def bubblesort(iterable):
seq = list(iterable)
for passesLeft in range(len(seq)-1, 0, -1):
for index in range(passesLeft):
if seq[index] > seq[index + 1]:
seq[index], seq[index + 1] = seq[index + 1], seq[index]
return seq
-- Note: AppleScript is 1-based, the first item of a list is "item 1"
--
on bubblesort( array )
repeat with i from length of array to 2 by -1 --> go backwards
repeat with j from 1 to i - 1 --> go forwards
tell array
if item j > item ( j + 1 ) then
set { item j, item ( j + 1 ) } to { item ( j + 1 ), item j } -- swap
end if
end tell
end repeat
end repeat
end bubblesort
See also
