Bubble sort Details, Meaning Bubble sort Article and Explanation Guide

Bubble sort Guide, Meaning , Facts, Information and Description

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.

Table of contents

1 Implementations

1.1 C
1.2 C++
1.3 Java
1.4 Basic
1.5 Perl
1.6 Python
1.7 AppleScript

2 See also

Implementations

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

C++

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];
         array[j] ^= array[j+1];
      }
}

Java

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

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

Bubble sort Guide, Meaning , Facts, Information and Description

See also

Search Anything