Warning: eregi(): REG_BADRPT:repetition-operator operand invalid in c:\httpd\www\masterliness\article.php on line 185
Bubble Sort Implementations C++ Java Basic Perl Python
Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > 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() comparisons to sort 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 (), while insertion sort needs only 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 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.
1 Implementations
1.1 C
void bubbleSort(int *array, size_t length)
{
int i, j;
for (i = length - 1; i > 0; i--)
for (j = 0; j < i; j++)
if(array[j] > array[j+1]) /* compare neighboring elements */
{
array[j] ^= array[j+1]; // Use XOR swapping to increase efficiency
array[j+1] ^= array[j];
array[j] ^= array[j+1];
}
}
template void bubbleSort(Type *array, size_t length)
{
int i, j;
for(i = length - 1; i > 0; i--)
for(j = 0; j < i; j++)
if(array[j] > array[j+1]) /* compare neighboring elements */
{
array[j] ^= array[j+1]; // Use XOR swapping to increase efficiency,
array[j+1] ^= array[j]; // but only when you're sure it is permissible to
array[j] ^= array[j+1]; // prefer efficiency to correctness.
}
}
template void bubble_sort(T *base, size_t n) {
T *p, *q, t;
while (n--) {
for (q = (p = base) + 1; p < base + n; ++q, ++p) {
(*p > *q) && (t = *p, *p = *q, *q = t);
}
}
}
public void bubbleSort(int [] array, int length)
{
int i, j;
for(i = length - 1; i > 0; i--)
for(j = 0; j < i; j++)
if(array[j] > array[j+1]) /* compare neighboring elements */
{
array[j] ^= array[j+1]; // Use XOR swapping to increase efficiency
array[j+1] ^= array[j];
array[j] ^= array[j+1];
}
}
Sub Bubblesort(Array() as Integer, Length as Integer)
Dim I as Integer
Dim J as Integer
Dim Temp as Integer
For I = Length -1 To 1 Step -1
For J = 0 to I - 1
IF Array(J)>Array(J+1) THEN ' Compare neighboring elementa
Temp = Array(j)
Array(J) = Array(J+1)
Array(J+1) = Temp
End If
Next J
Next I
End Sub
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;
}
Read more »