Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Talk:Sorting algorithms/Bubble sort (view source)
Revision as of 17:22, 10 December 2008
, 15 years agoidea: lets implement both!
(idea: lets implement both!) |
|||
Line 40:
:::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) --[[User:ShinTakezou|ShinTakezou]] 17:31, 9 December 2008 (UTC)
: 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
::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.
Line 73:
:::Yes, that is an optimized version of Bubble Sort which reduces the worst case execution time to half. (I fixed the swap command in your code.) The correct un-optimized version of Bubble Sort is given in the pseudo code in the article. The first code in this thread is a poor implementation of Selection sort (not Insertion Sort as I said earlier). --[[User:PauliKL|PauliKL]] 16:08, 10 December 2008 (UTC)
: How about a compromise? We implement both optimized and unoptimized versions on some other tasks. Why not here? (From that paper on the history of Bubble Sort, it appears that both forms have been named Bubble Sort over time. Earlier names include ''sorting by exchange'', "exchange sorting", and ''shuttle sort''. It appears Ken Iverson of [[APL]] and [[J]] fame first coined ''Bubble Sort''.) --[[User:IanOsgood|IanOsgood]] 17:22, 10 December 2008 (UTC)
| |||