BUAG = B = bucky bits

bubble sort n.

Techspeak for a particular sorting technique in which pairs of adjacent values in the list to be sorted are compared and interchanged if they are out of order; thus, list entries `bubble upward' in the list until they bump into one with a lower sort value. Because it is not very good relative to other methods and is the one typically stumbled on by naive and untutored programmers, hackers consider it the canonical example of a naive algorithm. (However, it's been shown by repeated experiment that below about 5000 records bubble-sort is OK anyway.) The canonical example of a really bad algorithm is bogo-sort. A bubble sort might be used out of ignorance, but any use of bogo-sort could issue only from brain damage or willful perversity.

--Jargon File, autonoded by rescdsk.

EDIT ME!
The Everyone Project.
Log in: "everyone" Password: "everyone"
First created by: rescdsk
Modified by: (nobody)

The Bubble Sort (O(N^2)) is, on average, the worst of the sorting algorithms which were designed with good things in mind. For
specific cases in which the data are already sorted, or almost sorted, bubble sort is by far the fastest sort.

In this writeup, I assume that the name of the array to be sorted is A, that it is N entries long, that the entries are indexed 0 to (N - 1) [inclusive], that element number i of the array is referenced by A{i}, and that the array is to be sorted so for all integers i and j between 0 and (N - 1) incusive, (A{i} ≤ A{j}) iff (ij) [i.e. A{0} contains the lowest-valued element and the values of successive entries in A are nondecreasing].

The basic idea of the bubble sort is to apply the divide and conquer method; reduce the problem of sorting an entire array to the problem of sorting two adjacent elements, then apply this simpler problem in a way that will accomplish the larger problem. The problem of sorting an adjacent pair of elements is very simple; if the element at the lower index has a greater value then the pair needs to be swapped, otherwise the pair are already sorted [relative to each other, at least - not necessarily sorted in the larger context of the entire array]. A 'pass' is made through the array, sorting the pair A{0} and A{1}, then the pair A{1} and A{2}, and every pair, in order, up to A{N - 2} and A{N - 1} [thus, a pass consists of (N - 1) adjacent-pair-sorts]. It can be proved that after each pass, at least one more element is guaranteed to be in the correct position, so at most (N - 1) passes are necessary to sort the entire array [if (N - 1) elements are properly sorted, there's no place for the Nth element to be but it's properly sorted place too]. A simplistic implementation of the bubble sort looks like this:


i := 0
while (i < (N - 1))
  j := 0
  while (j < (N - 1))
    if (A{j} > A{j + 1})
      swap A{j} and A{j + 1}
    end if
    j := (j + 1)
  end while
  i := (i + 1)
end while

This takes (N - 1)2 adjacent-pair-sorts. By realising that after one sweep, the greatest element must be at the highest index and generalising from there, one can see that the highest elements can be ignored on later passes so new, better code can be written:


i := (N - 1)
while (i > 0)
  j := 0
  while (j < i)
    if (A{j} > A{j + 1})
      swap A{j} and A{j + 1}
    end if
    j := (j + 1)
  end while
  i := (i - 1)
end while

This takes ((N - 1) * (N - 2) / 2) adjacent-pair-sorts, less than half the number of the first code. Another optimisation can be added: if, on any pass, there are no swaps, this means that the array is sorted, and the sort algorithm can end. This adds a little more processing to each pass, but the beneft of saving a few passes can so outweigh the cost of the little extra processing in each pass that it is generally considered a good idea to include it.


i := (N - 1)
DidSwap := true
while ((i > 0) ∧ (DidSwap = true))
  DidSwap := false
  j := 0
  while (j < i)
    if (A{j} > A{j + 1})
      swap A{j} and A{j + 1}
      DidSwap := true
    end if
    j := (j + 1)
  end while
  i := (i - 1)
end while

Finally, when one considers a mostly-sorted array [e.g. an array that is fully sorted, but has an extra element added onto the end with a value lower than any other entry], another optimisation comes to mind. A pass through the array from the lowest index to the highest ensures that the greatest element is properly sorted. Likewise, a pass from the highest index to the lowest would ensure the least element is properly sorted. A sweeping back-and-forth of passes would therefore most likely perform better on a mostly-sorted array.


limit{-1} := -1
limit{1} := (N - 1)
i := 0
direction := 1
DidSwap := true
while (((limit{-1} + 1) < limit{1}) ∧ (DidSwap = true))
  DidSwap := false
  while (ilimit{direction})
    if (A{i} > A{i + 1})
      swap A{i} and A{i + 1}
      DidSwap := true
    end if
    i := (i + direction)
  end while
  limit{direction} := (limit{direction} - direction)
  i := (limit{direction} - direction)
  direction := -direction
end while

All array entries with index lower than or equal to limit{-1} are sorted, and all array entries with index higher than limit{1} are sorted, at all times. direction is 1 for an ascending sweep through the array, and is -1 for a descending sweep. Once a pass is completed, the appropriate limit has direction subtracted from it, so the next pass in the same direction won't go unnecessarily far into a part of the array which is known to be sorted already. i is reinitialised to start the sweep in the opposite direction, so that it doesn't start in the part of the array which is known to be sorted already, and direction is inverted so the next sweep is in the opposite direction.

Here is a short and (hopefully) amusing story about a real-world implementation of bubble sort I have recently observed. Mind you these are non-computer types that do this, and miraculously it ends up pretty close (not exactly, but close) to a bubble sort. It is only approximate, but it is also quite fault tolerant.

Okay, here's the story. At the Chapter House (a bar that I go to for a pint from time to time), the tap room is layed out as follows: If you are facing the bar, at the far right of the room there is the entrance from the outside, which consists of a drafty old wooden door that doesn't quite seal, and a wall of old 1800's era windows that are also quite drafty. On the far left, there is a steam radiator that kicks out an impressive amount of heat. So, as you'd expect, it's cold and drafty at the side by the door, and warm and nice at the side by the radiator.

There exists a row of about 9 or 10 chairs that are the right height to sit on while at the bar. These chairs have seen better days, and some of them are so wobbley and rickety that they feel quite hazardous to sit in even when your world is on a completely even tilt, so you can imagine how people feel about them once they get a couple pints in them. There is a fairly even and continuous distribution among these chairs on a scale between completely falling apart and relatively sturdy.

Now comes the fun part. I was sitting there one day watching a newcomer settle in. Here are the steps that most people take when sitting down at the bar:

  1. Find the leftmost (warmest) unoccupied space at the bar
  2. Test the quality of the chair at that spot, as well as the chair at the next unoccupied spot to the right (the next warmest spot)
  3. If the chair at your spot is more sturdy, keep it. If not, most people simply swap their more rickety chair with the more sturdy one to the right.
This fuzzy process occasionally is broken by somebody who doesn't care about chair quality, or temperature, or if there is a group of several sitting down such that they need to find a contiguous block of several chairs, but on the whole it is remarkably effective. Most of the winter (when the temperature issue matters most), you will find the chairs pretty accurately sorted so the rickety chairs live down at the cold end of the bar, and the most solid chairs live at the warm end.

This is a real pisser if you come late, however, because then you get the cold seat, and a crummy chair to boot. Every once in a while they sweep the floors, and in doing to randomly reorganize the chairs, but within a day or so, they end up sorted again. It's quite amazing to watch.

Log in or registerto write something here or to contact authors.