Talk:Counting sort

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as start-Class on the assessment scale
High rated as high-importance on the assessment scale

Contents

[edit] sort

Hello. I am Diego R. Martinez, the original author of this page. I'd like to find out where did you get the second refe,mn.mn.mn.nj.jkrence for this page and what does it refer to?

Hi Diego. I am the inventor of counting sort and radix sort. "Information sorting..." is my 1954 Masters thesis. Many other sorts are included in its 60 pages. Knuth's sorting and searching (vol. 3) describes my sorts, including "replacement selection." How do I contact you again?

Harold H. Seward hseward@alum.mit.edu

[edit] Hello Harold

I am milad the inventor of the Rapid sort, Check sort, Instant sort and Simple routines who's publication in the Wikipedia has sparked a controversy that these sorts are duplications of your Counting sort although I invented them quite independently and without any knowledge of your Counting sort prior to their invention. Although both sorts use array indexing and increment the value of a numerical array as prescribed by the algorithms they follow I strongly disagree that their differences are insufficient to tell them apart. For one thing the Rapid sort can be duplicated directly in hardware by simply substituting an address bus of a random access memory chip for the array index and a single bit data bus as the means of indicating the presence of checkmark data (a single digit binary count) in the case of the Check sort or its hardware version the Instant sort and a multiple bit data bus in the case of the Rapid sort which has the capability of counting the number of identical pieces of data when they occur. The single bit memory is used to eliminate duplicates while the multiple digit data bus is used to include a count of duplicates. Along with a counter that can be sequentially incremented to retrieve the sorted data and a comparator and another counter to recognize memory content which has been incremented (even if only once as in the case of the checkmark function) and to accommodate its decrement to zero in order to provide a means of duplicating the count the random access memory chip make up the core of the hardware digital circuit. I would therefore greatly appreciate having your opinion as to the differences between the two sorts so that this argument might be resolved. Thanks. Patrick C Eberhart. ...IMHO (Talk) 23:38, 3 June 2006 (UTC)

[edit] Potential implementation error

Hello.

I think there is an error in the C and Java implementations presented here. The variable 'range' is assigned a value of 'max-min+1', and the array 'count' has this many elements, indexed from 0 to 'range-1'. However, in filling the array (in the second for loop), an index 'c' equal to 'array[i]+1-min' is used. With a maximum value of 'array[i]' being, presumably, 'max', 'c' may be given a maximum value of 'max+1-min' which is equal to 'range' and is therefore beyond the bounds of the array 'count'. (Similarly, the minimum value of 'c' is 'min+1-min' = 1, meaning count[0] is never used).

There are probably a number of ways to correct this, but as I'm in the process of trying to understand and implement the algorithm myself (as opposed to actually knowing it well), I'm probably not the best person to be suggesting a solution.

If and when a fix is made, please let me know. Thanks.

Cheers, David Fernandez (i.am.david.fernandez(at)gmail.com)

I believe you're correct - for some reason the code here was written for one-based arrays rather than zero-based. If the original author doesn't object I'll fix it. Deco 03:29, 25 November 2005 (UTC)

No, the arrays are not one-based - surely you can see that by looking at the other array accesses? The problem was that the first element of the count array is never written to (because there are zero elements lower than the first) and that the one-past-the-end element was written to (but never read). I increased the size of the count array by one to allow for this. JonathanWakely 09:52, 28 January 2006 (UTC) P.S why are there two almost identical implementations? The Java one should be removed or replaced with something sufficiently different to be worthwhile.

I believe this C implementation (as of 20 May 2006) is not stable. To make it stable, shouldn't the sorting loop (the 2nd last loop of the code) be run from end-1 to 0 and count[i]-- be used instead of count[i]++?

--221.134.24.54 18:32, 20 May 2006 (UTC)


I noticed the C implementation had some typos and did not compile. I took the liberty of fixing the typos and enhancing the comments, including a Doxygen style header, as well as giving some of the variables more descriptive names. I did not change the algorithm and tested it to make sure it works as advertised. Barbarab111 06:10, 14 December 2006 (UTC)

I'm new to C++ but the code doesn't compile as is. "int [] counts = new int[distinct_element_count];" raises "expected unqualified-id before '[' token" compiler error (g++). Shouldn't it be "int counts[distinct_element_count];" or, if you want to allocate the memory manually "int * counts = new int[distinct_element_count]"?

[edit] Remove Performace Measurement from Visual Basic Implementation

In my opinion the performance measurement goes beyond the presentation of the Sorting algorithm in one single implementation. It could be presented in an extra section. It should be programming language independent, if possible.

The Basic code will be much more readable. And it could do with a bit of indenting.

-- Torsten T. Will

[edit] Stability

The article claims that counting sort is a stable sort... I don't believe this is true. The question of stability is not applicable when sorting integers, since repeated integers are not distinct. I'm removing all references to stability. ~ Booya Bazooka 19:19, 14 September 2006 (UTC)

I think the stability references MUST be undeleted! The reason is in this example:
Suppose you're a teacher and you've sorted the exams by name. The exams have signs from 1 to 5 (or A to E). Then you make 5 places to put the exams. Starting from the last put the exams to the right place. Then if you examine the packs, each will be ordered by name. Here the "repeated integers" ARE distinct, because each belongs to another student. This is why it's called stable, it keeps the previous ordering of not distinct elements.
Try this example with some papers, and you will find out... if you don't beleive me :P TWiStErRob 01:53, 6 December 2006 (UTC)