Talk:Odd–even sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing / Software / CompSci (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
Taskforce icon
This article is supported by WikiProject Software (marked as Low-importance).
Taskforce icon
This article is supported by WikiProject Computer science (marked as Low-importance).
 

I may be missing something, but it appears that this algorithm is functionally identical to the Cocktail sort? — Preceding unsigned comment added by 206.195.193.254 (talk) 21:35, 05 June 2007 (UTC)

  • As I understand it, this algorithm us a unique one that is intended for use in parallel (as depicted in the image), (meaning while it is worthwhile for this article to exist, it needs a complete rewrite). The idea seems to be to basically cocktail sort by two's, such that each pass switches each value with the value next to it if it needs to be switched, without bubbling up to the top/bottom completely. —Preceding unsigned comment added by 192.235.8.5 (talk) 01:32, 23 October 2007 (UTC)
  • The algorithm described here is Cocktail sort. Odd-even sort uses parallel processors, each using bubblesort. The effect is that it compares all odd indexed elements to their right hand neighbours in the same step, and all even indexed elements in the next, repeated until the list is sorted. I will try to fix it. Thomas Nygreen 11:23, 7 November 2007 (UTC)
  • Removed everything that was "cocktail sort". I also suspect that the name "alternating bubble sort" did refer to cocktail sort, refering to the alternating directions of the looping. But it might also refer to the alternating of odd-even and even-odd steps... not sure so removed it too. Image is correct though (can see parallel bubbling in both directions) so left it. Moo (talk) 23:37, 27 May 2008 (UTC)
  • Added basic odd-even algorithm from my understanding of the algorithm description. I tried odd-only and even-only parallel bubble sorts and it doesn't produce a fully sorted list. Either the algorithm description is wrong or I cant fit the bit about parallel processing into the picture. I mean...on parallel processors...you split the list, sort them individually and then merge. And there are words such as "alternating" in the algorithm description.203.219.14.183 (talk) 14:01, 10 January 2009 (UTC)

parallelization[edit]

It seems that the only interest of this algorithm (in ragards with bubble sort) is that it can be efficiently parallelized. Hence the article should at least mention the complexity of the parallelized algorithm, not only the worst case of the sequential algorithm.

What about the average case ? —Preceding unsigned comment added by 88.183.11.75 (talk) 15:36, 13 June 2009 (UTC)

Algorithm[edit]

The proof here only shows, that odd-even sorting, reduced on Knuth 0-1 sorting Principle, takes n passes. Either the statement of the Theorem has to be changed or the proof, that reducing the problem to Knuth 0-1 sorting, didn't change the amount of passes. — Preceding unsigned comment added by 128.176.106.48 (talk) 13:38, 21 January 2014 (UTC)

That's an interesting question. I think that reduction to Knuth's 0-1 case does not change the number of passes, but I am not sure of a simple proof. Deconvolution (talk) 06:11, 27 April 2014 (UTC)

Keep just Pseudo code, remove other Language specific code[edit]

As suggested with other sorting entries, all code other than pseudo-code should be removed, perhaps someone somewhere else would like to capture it before deletion? 60.242.247.177 (talk) 14:04, 12 November 2015 (UTC)

Dead Link, in References[edit]

Link # 1. was found to be "not found" on server, please edit page. — Preceding unsigned comment added by 184.6.67.68 (talk) 06:04, 15 December 2016 (UTC)