Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Talk:Sorting algorithms/Bubble sort (view source)
Revision as of 18:37, 9 December 2008
, 15 years ago→This is bubble sort?
(→This is bubble sort?: Knuth is my homeboy) |
|||
Line 41:
: As the person who originally asked the question, I acknowledge that I was mistaken about the definition of "Bubble Sort". The given algorithm was the first sorting algorithm I learned, but I am happy to implement the better one for this task. The task's bubble sort is the one analyzed by Knuth. I mean... '''KNUTH!''' /discussion --[[User:IanOsgood|IanOsgood]] 18:04, 9 December 2008 (UTC)
::Ok, then let's call it Optimized Bubble Sort, since it is that: a Bubble Sort that does not waste times executing outmost loop when the inner loop '''always''' won't swap anything. This condition becomes true since for the first time the inner loop makes no change.
<pre>
void sort(int *a, int size)
{
int i,j, swapped=0;
for (j=size-1; j>0; j--) {
swapped=0;
for (i=0; i<j; i++) {
if (a[i+1] < a[i]) {
swap(a+i); swapped=1
}
}
if ( swapped == 0 ) break;
}
}
</pre>
::I wrote it fastly, but hopely it works; would you call it still BubbleSort or no? Do you agree with the fact that if the inner loop makes no swap, it will make no swap even in every other iteration? So it is still bubble sort in principle, but the code is optimised; but let us have the implementation A of the algo X. If the Code Optimizer (a person) optimize A generating the implementation B, B is still an implementation of X? Even though Knuth would be more precise in word using, I believe it would say yes. On internet you can find also interesting resources, like [http://www.cs.duke.edu/~ola/bubble/bubble.pdf this pdf file] where we can read:
<blockquote style="background-color:#DDF; padding:5px">
Nearly every description of bubble sort describes how
to terminate the sort early if the vector becomes sorted.
This optimization requires checking if any swaps are
made and terminating if no swaps are made after j it-
erations of the inner loop.
</blockquote>
::and presents a code very close to yours. Even the wikipedian explanation of how the BubbleSort operates tell the fact that they are just two different implementation of the same thing, the first being an optimisation of the more rough way of doing it. --[[User:ShinTakezou|ShinTakezou]] 18:37, 9 December 2008 (UTC)
| |||