What's a bubble sort?

Question

What is a bubble sort? Can someone help me?

Edit-

See also this earlier question: What is a Bubble Sort good for? Although very similar, "What is a bubble sort?" is a more fundamental question and is therefore still useful for beginners to programming.

Answer 1

http://www.sorting-algorithms.com/

More specifically:

http://www.sorting-algorithms.com/bubble-sort

Answer 2

A bubble sort is a simple, though inefficient, means of sorting a list of data by continually passing through the list, swapping pairs of elements that are out of order. You can implement it something like this in Java (assuming you have an integer array, 'data', which contains the data to be sorted):

  for (int passNo = 0; passNo < data.length; passNo++) {
    int maxPos = data.length - 1 - passNo;
    boolean swapped = false;
    for (int i = 0; i < maxPos; i++) {
      int d0 = data[i];
      int d1 = data[i+1];
      if (d1 < d0) {
        data[i] = d1; data[i+1] = d0;
        swapped = true;
      }
    }
    if (!swapped)
      break;
  }

The sort is thus so-called because a given piece of data gradually "bubbles" over the array until it reaches its correct place. The loop over 'i' does the "bubbling". It compares all consecutive pairs of ints, swapping any that are out of order. We need to repeat this process a maximum of 'n' times, where 'n' is the length of the array (hence the outer loop over 'passNo'). However, if in practice, we do a pass where no pair of data is swapped, then we know that the data is sorted, hence the 'swapped' variable.

Bubble sort is an inefficient means of sorting data and is practically never used. Pretty much its only redeeming feature is that it is simple enough for your granny to understand. If for some reason you find yourself stuck with your laptop on a desert island with no access to any other sort library, it might be the sort routine you can remember.

As with inefficient sort algorithms in general (compare the insertion sort), the inefficiency comes from the fact that we end up comparing the same pairs of data many times. More efficient algorithms often use a "divide and conquer" strategy (in one way or another, you divide up the list, sort each sub-part, then stick the sub-parts back together) to avoid having to repeat the same comparisons multiple times.

Answer 3

Bubble sort is one of the many sorting algorithms that people use to sort a list.

Worst case performance- O(n^2)

Best case performance- O(n): ironically this only happens if the list is already sorted

Example source code:

void bubbleSort(int numbers[], int array_size)
{
      int i, j, temp;
      int sorted=1;
      for (i = (array_size - 1); i >= 0; i--)
      {
        sorted=1;
        for (j = 1; j <= i; j++)
        {

          if (numbers[j-1] > numbers[j])
          {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
            sorted=0;
          }
        }
        if (sorted) { break; } //if done in first loop this it makes best case performance
      }

}

Example of the first loop: array: [45, 67, 12, 34, 25, 39]

In the first step, the focus is on the first two elements which are compared and swapped, if necessary. In this case, since the element at index 1 is larger than the one at index 0, no swap takes place.

45, 67, 12, 34, 25, 39

Then the focus move to the elements at index 1 and 2 which are compared and swapped, if necessary. In this example, 67 is larger than 12 so the two elements are swapped. The result is that the largest of the first three elements is now at index 2.

45, 12, 67, 34, 25, 39

The process is repeated until the focus moves to the end of the array, at which point the largest of all the elements ends up at the highest possible index. The remaining steps result are:

45, 12, 34, 67, 25, 39

45, 12, 34, 25, 67, 39

45, 12, 34, 25, 39, 67

Then repeat the same process starting at index 0;

For more detail here: Bubble Sort

Answer 4

It's an algorithm that sorts in 0 (N^2).

It goes through an array twice, comparing each element of the array to the entire array, and swapping them on some criteria (greater than, lower than).

Its called bubble sort because "heavier" elements go to the "bottom" of the array.

And no, it has no relationship with 1986's Bubble bobble

Answer 5

It's one of the simplest sorting algorithms. It works by swapping consecutive members of a set in the desired order. It is pretty unefficient since it will evaluate each pair once in every run and will rerun through the set until no swapping is necessary.

       do {
            bool ordered = true;
            for(int i = 0; i < values.Length - 1; i++)
                if(values[i] > values[i + 1]){
                    swap(values[i], values[i + 1]);
                    ordered = false;
                }
        } while(!ordered);

One "property" of this sorting algorithm is that, the last members of the set, will be sorted first.

Answer 6

You can watch it on the traditional Berkeley videos here, among other sort algorithms.

Of course, this is old. But is invaluable!

You must watch the complete Sorting out Sorting series.

Answer 7

Think of the values you're sorting as bubbles that go up depending on the fashion, increasing / decreasing. Technically, values are contained in a list, you iterate the list comparing two values at a time and whichever is smaller / bigger you make it "bubble" up to the top.