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)

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)