Bubble sort

From TheBestLinks.com

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.

Table of contents

1 Implementations

1.1 C
1.2 Basic
1.3 Perl
1.4 Python
1.5 AppleScript

2 See also

Implementations

C

 void bubbleSort(int *array, int length)
 {
   int i, j;
   for(i = length - 1; i > 0; i--)
     for(j = 0; j < length - i; j++)
       if(array[j] > array[j+1]) /* compare neighboring elements */
       {
         int temp;
         temp = array[j];    /* swap array[j] and array[j+1] */
         array[j] = array[j+1];
         array[j+1] = temp;
       }
 }

Basic

 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

Perl

 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;
 }

Python

 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

AppleScript

 -- 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

Discussion

Last posted 0 of 0 messages

[no messages posted yet]

>> post message >>

Watch

You can add this article to your own "watchlist" and receive e-mail notification about all changes in this page.

Retrieved from "http://www.thebestlinks.com/Bubble_sort.html"

Categories: Sort algorithms