Talk:Flashsort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Stub-class)
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.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
Note icon
This article has been automatically rated by a bot or other tool as Stub-Class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.

Page started[edit]

This page was requested, so I wrote it. Any thoughts? I think it satisfies notability as independent publications from reputed scientists have cited and used it, in spite of the apparent fact that author is a terribly poor writer and has few academic credentials. Testing has shown that this algorithm is indeed the real deal. SamuelRiv 02:52, 6 November 2007 (UTC)

The worst case with Quicksort still is O(n^2).--Azrael60 (talk) 19:00, 29 November 2007 (UTC)

Of course, that's my fault. I will clarify the point. SamuelRiv 19:16, 30 November 2007 (UTC)

well i dont think so —Preceding unsigned comment added by 84.169.84.80 (talk) 16:32, 21 February 2008 (UTC)

Opening line[edit]

Flashsort is a sorting algorithm with extremely good O(n) efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert.

This made me laugh hard enough that I couldn't bring myself to change it. Such a specific sort! Xkcd (talk) 20:07, 28 June 2009 (UTC)

Algorithm[edit]

m needs to be defined explicitly. —Preceding unsigned comment added by 69.230.52.197 (talk) 00:42, 13 July 2009 (UTC)

I think m is the number of elements that need sorting. Am I wrong, or does this sort assume an even distribution of elements across the range of values? I can't see this sort working very well for even simple cases such as sorting surnames. --Surturz (talk) 19:42, 23 February 2010 (UTC)

Quicksort cannot be used to speed up the sort[edit]

AFAIK, quicksort has O(n log n) best case behaviour. Even if the list is perfectly sorted. Yet the article suggests using QuickSort instead of Insertion Sort (which has O(n) best case behaviour, giving Flashsort its inherent speed), which just doesn't make sense. Is this original (and poor) research? Or is there a variant of Quick Sort with O(n) best case behaviour that I'm not aware of? If no one corrects me in a week I'll remove the offending line.. Themania (talk) 10:08, 5 November 2009 (UTC)

Reading the citations, it looks like you can perform the search on just each class, where quicksort could be used without losing O(n). I feel the article needs to explain this, anyone want to change it? Themania (talk) 23:38, 5 November 2009 (UTC)

Just a reinvented bucket sort[edit]

It seems to me that Dr Neubert has just reinvented the in-place bucket sort. What he describes seems very similar to what is described in the abstract here: http://www.springerlink.com/content/31dvgnd8c911drka/

Furthermore, this page suggests that Dr Neubert used the same name as an older alogrithm:

http://www.itl.nist.gov/div897/sqg/dads/HTML/flashsort.html

Artelius (talk) 05:31, 6 July 2010 (UTC)

Specifically, the first pass of counting members of each class in an auxiliary vector L makes it look like an American flag sort. --Damian Yerrick (talk | stalk) 03:32, 29 December 2011 (UTC)
Yup, the algorithm described in Burnetas et al. (1997, submitted 1995) looks very similar. They call their algorithm Groupsort. Groupsort also uses only an additional vector, which stores starting positions of subarrays (buckets, groups) in the input-array. They claim that a size of 0.2n is optimal in practice (Neubert uses 0.42n). They sort the groups via Quicksort (Neubert sort his classes via Insertionsort). The approximate address computation looks very similar (they cite Isaac, Singleton, Sorting by Address Calculation, JACM, 1956 for the idea of using an approximate address computation).
--Gms (talk) 20:22, 24 February 2012 (UTC)