Talk:Double bubble sort

From Wikipedia, the free encyclopedia

From what I can find, double-bubble sort is another name for cocktail sort. IMHO, this "double-bubble sort" is simply a variation of insertion sort less the temporary variable and plus the swapping. I am going to put this on VfD with a suggestion to merge to Insertion sort unless if Irate provides additional support that this is a different algorithm (from insertion sort) with this name.

— UTSRelativity 00:31, 2 Apr 2005 (UTC)

(content below from the a page misnamed as "Talk talk:Double bubble sort"; page history merged with this one --cesarb 18:36, 12 Jun 2005 (UTC))

What is the dispute?--Jirate 19:05, 2005 Apr 2 (UTC)

I think the dispute is about whether this algorithm is any different from insertion sort. I, for example, looked at the example code and thought "I must be missing something, because this looks exactly like insertion sort". After closer inspection, I still don't see how this is any different from insertion sort. As an aside, given today's optimizing compilers, xor swapping is less efficient than using a temp variable. Flatline 16:19, 2005 Apr 9 (UTC)
Firstly that processor does not come into it. If the allgorythm is the same as the Insertion sort, then it should be possible to implement it with the same number of vars, it cannot be done. IPSO facto it a different algoithmn. --Jirate 14:42, July 17, 2005 (UTC)

[edit] Nominate for deletion?

Actually, can I recommend deletion? I concur that this "algorithm" is simply a minor implementation variation on the traditional insertion sort algorithm, and as commented by flatline not a particularly good one (apart from anything else, it only works for integers or similar types, due to the assumption of availability of an XOR operator). And once this has been cleared out of the way, the page can be redirected to cocktail sort, which has more right to the name. JulesH 20:59, 9 July 2005 (UTC)

I think that deletion is appropriate. The meat of this algorithm is that take a list that is presumed sorted (at the beginning you start with a list of length 1 which is trivially sorted) and then shift the values up until you've opened up the position for the next item. This is the definition of Insertion sort. Whether the item is stored in a temp variable or shifted down as the other items are shifted up is an implementation detail that does not change the fact that the algorithm here is Insertion sort. --Flatline 19:41, 28 September 2005 (UTC)

I agree, this algorithm is not a 'double bubble sort', it's just a plain vanilla 'bubble sort' which is covered elsewhere in the Wiki.

PJB

If there's such a thing as a "plain vanilla" bubble sort, then it's the one described there. A very different algorithm from this. -- Smjg 14:28, 28 September 2005 (UTC)

Bubble sort makes passes of decreasing length. This algorithm, like other insertion sorts, makes passes of increasing length and stops each pass as soon as it can. It stores the item being inserted in the gap made while shifting other items over, while most insertion sort implementations cache it in a variable; logically there is no difference. In terms of performance I would be completely astonished if this algorithm were faster than than a conventional insertion sort, since you not only have to access off-processor memory, but must do so repeatedly and unnecessarily.

I'm naturally skeptical of someone who touts the xor swap as a way to improve the speed of a n^2 algorithm... reminds me of a usenet legend who presented a bubble sort written in assembly language for "maximum speed and efficiency." I'll skip the afd and just redirect this. Gazpacho 08:57, 25 January 2006 (UTC)

Noone said the algorithm was faster. If it is the same as insertion then rewrite insertion to use the same number of variables. It is a simple test. When you use a vary small processor you may find that saving variables is very important.--84.9.195.229 22:08, 2 March 2006 (UTC)

Hmm, I believe that the article does not describe what is usually called "double bubble sort". Real double bubble sort (AKA cocktail sort) is the algorithm described in the cocktail sort article. This article should be rewritten from scratch. - Anonymous, 22 March 2006

There is no logical difference between what is described here and insertion sort. It is simply a bad implementation. There is not a single textbook on algorithms that distinguishes sorting algorithms according to whether they use XOR swapping. Gazpacho 01:56, 8 April 2006 (UTC)

Nope not at all. Rewrite the insertion sort with the same number of variables as this you will have gone someway to show this is the same alogorithm, but you haven't do that. What you don't understand is what an algorithm is, you seem to think it is a program, it isn't. Alogrithmn pre date computing by a long way. Thos of us that have add to work on small machines like PIC, Z8 and other stuff you children haven't heard of are often grateful for a way of doing things which uses less memory. EVen if it is one byte. The test is simple write insertion sort with the same number of variables and you can redirect, but Wikipedia is not a place to push your POV. In this case the test is simple go and do it or go away, do keep crying "my mummy said"--84.9.195.103 13:34, 8 April 2006 (UTC)
If I was to implement insertion sort with the same number of variables as "this" then I'd have what you call "double bubble sort". I do not believe that an implementation using XOR swapping becomes a different algorithm. It really depends on what level of abstraction you take to be essential for insertion sort. Also, calling someone a "child" while posting as an anon is not very mature. — Image:Ca-on-sb.gif  UTSRelativity (Talk)  14:45, 8 April 2006 (UTC)
I was commenting on my venrability rather than his youth. What test for difference do you propose?--84.9.195.103 18:29, 8 April 2006 (UTC)

This was posted on my talk page: Are you by any chance a first year computing student?--84.9.195.103 13:36, 8 April 2006 (UTC)

My response: Hardly.

Either cite a source or leave the redirect in place. Gazpacho 06:14, 9 April 2006 (UTC)

Then what are you? You do not seem to know anything about computing especially alogrithmns.--84.9.210.183 11:42, 9 April 2006 (UTC)

As tempting as it is to list my resume, I'm not going to do so at this time. Wikipedia:Verifiability is very clear that you have the burden of providing a source. I'm going to keep reverting until you do so. Gazpacho 19:11, 9 April 2006 (UTC)

Go on list it do. I've demostrated that it has a minimum number variables that is smaller than the insertion sort, therefore it is a different algorithmn. --87.75.130.47 02:11, 10 April 2006 (UTC)

I'm not interested in your say-so. Provide a source, please. Who first described this algorithm as "double bubble sort"? Gazpacho 17:25, 10 April 2006 (UTC)

Oh, you're a banned user. Well, that simplifies matters greatly. Gazpacho 19:56, 10 April 2006 (UTC)

How would that change the argument. It doesn't but it looks like you try anything, any sign of your resume?--87.75.130.47 20:02, 10 April 2006 (UTC)

I've semi-protected the redirect until the anon can provide the asked-for sources. No one's credentials or résumé are relevant, only verifiability is. Angr (talk • contribs) 20:09, 10 April 2006 (UTC)

[edit] Knuth

Searching and Sorting mentions the "Cocktail Shaker Sort" and of course Bubble Sort, but in no case mentions "double bubble". It would appear that this is either (or both) non-WP:V or WP:NOR. But most of you knew that already :-) -- Gnetwerker 20:36, 10 April 2006 (UTC)