Talk:Sorting algorithms/Bubble sort

Algorithm link

Seems like it would be better for algorithm tasks to include their natural-language description, infobox, and perhaps pseudocode in a top-level section before the examples rather than on a separate page. --Bob9000 07:41, 31 January 2007 (EST)

Removed. Now for someone to fill in the description of the algorithm... --Short Circuit 10:53, 31 January 2007 (EST)

This is bubble sort?

This isn't the bubble sort I've learned. Where did you get this algorithm? This is my bubble sort:

void sort(int *a, int size)
{
  int i,j;
  for (j=size-1; j>0; j--)
    for (i=0; i<j; i++)
      if (a[i+1] < a[i])
        swap(a+i);
}

That may be "your bubble short", but it is definitely not Bubble Sort. The basic feature of Bubble Sort is that it finishes sorting when there were no more swaps needed. Because of this, the best case execution time of Bubble Sort is O(N), i.e. linear time, which is significantly better than that of QuickSort, O(N*Log(N)). --PauliKL 18:51, 24 November 2008 (UTC)

I also learned the bubble sort the way without checking for swaps (twice). I think we can all agree that the bubble sort is a comparison sort. If so, it would ONLY compare and swap items in the collection AND its best possible complexity would be O(n*log(n)). Adding this check for swaps seems like an optimization that takes it out of the comparison sort category, so I don't think it's part of the original algorithm. It may be the way that people implement it in practice (though I don't know why you'd use it in practice), and it may also be a welcome optimization (at least worth noting that it exists), but it doesn't seem like it's part of the idea of the sort. The "basic feature" of the bubble sort is the one it gets its name from: smaller elements bubbling to the top (front) of the collection. --Mwn3d 19:38, 24 November 2008 (UTC)

No, it is exactly the opposite. Testing if swaps were made in inner loop was the only exit criteria in the original algorithm (as I learned it back in the early eighties). Bubble Sort goes through all the values, swapping any two values that are not in correct order, and repeats from beginning if any swaps were made. That is where the name Bubble Sort cames from. The small values bubble towards the top. The sorting needs to continue as long as there are more bubbles going up. The fact that largest value falls to bottom is a side effect that can be used to optimize the outer loop. But that only reduces the worst case execution time to half.

The code above is not Bubble Sort, it is an inefficient implementation of insertion sort. It does not care about the bubbles, only about the largest value falling to bottom. --PauliKL 13:51, 9 December 2008 (UTC)

I think the difference is splitting hairs. One can unconditionally implement the nested loops for a guaranteed run-time of O(n**2) or one can track whether any swaps were performed in the most recent (inner loop) pass. One can consider that test to be an "optimization" which improves the best case while having negligible effect on typical and worst case performance.

Given that the bubble sort is only useful for pedagogical (educational/instructional) purposes it's worth discussing these differences in an academic coverage. Their the focus would be on the trade-offs between code complexity (an extra assignment in the innermost conditional and a couple of extra statements in the out loop to reset and check the flag) vs. the performance benefit (in this case only for best case or near best cases).

However, the different is trivial for purposes of the code examples here. The use of bubble sort examples on RosettaCode is to present each language's syntax and features as applied to an extremely familiar algorithm, one which is widely studied and understood. Having the conditional "optimizations" shows more of each language's fundamental syntax and features. JimD 23:30, 24 November 2008 (UTC)

That is not splitting hairs, it is a fundamental difference. We are talking about two different algorithms, poor implementation of insertion sort (the code above) vs. Bubble Sort. And there is huge difference in the best case execution time: O(n**2) vs. O(n). The best case is when the data is nearly sorted, which is a very common case.

Bubble Sort is definitely not "only useful for pedagogical purposes". It is the simplest sorting algorithm. In cases where the data set is small, there is no point using more complex algorithm. Especially in cases when the data is expected to be nearly sorted. In fact, for small data sets, a more complex algorithm is probably slower.

The difference is not insignificant in RosettaCode either. In order to be able to compare languages, it is important that all the implementations use the same algorithm. And it seems that Bubble Sort is not so familiar algorithm after all, since so many people seem to mix Bubble Sort and the poor implementation of Insertion Sort.

--PauliKL 16:49, 9 December 2008 (UTC)

I'd like to say mine: the pseudocode proposed is a BubbleSort; as far as I remember, BubbleSorting can be implementend in both the way, and still is BubbleSort. The name BubbleSort comes since it let the smaller elements get on the top like bubbles (in water?), letting the lighter bubble pass beyond the near heavier bubble. The principle is the same, but the pseudocode is more efficient since there's a test that avoid looping without swapping (while in the previous code extern loop must be executed even if the inner loop has not swapped anything) --ShinTakezou 17:31, 9 December 2008 (UTC)