Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: My sorting algorithm that counts in values in arrays, JTsort or Countsort
Replies: 18   Last Post: Jan 9, 2013 7:57 PM

 Messages: [ Previous | Next ]
 JT Posts: 1,448 Registered: 4/7/12
Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
Posted: Jan 8, 2013 8:39 PM

On 8 Jan, 16:23, forbisga...@gmail.com wrote:
> On Monday, January 7, 2013 10:10:09 PM UTC-8, Kiru Sengal wrote:
> > It is called bucket sort where each bucket is a single integer value (instead of a range).
>
> > This is (a variation of) what humans use to sort exam papers by grade (100, 99) or last name (A,B,C,..).
>
> Thanks, I couldn't remember the name.  I was thinking block sort like
> we used to do on the old card sorters.  No one wanted to sort 20 boxes
> of cards on 20 columns so we would sort the most significant column
> first then repeated this on the next most significant column until each
> block of cards were managable.  Then we switch to sorting from least to
> most significant, finally we'd put the batches back together in order
> and all were sorted.
>
> I tried reasoning with JT for a few days.  It doesn't work.  JT talks
> about recursively applying his "countsort" algorithm.  Maybe he is
> slowly coming to his senses.
>
> It seems to me the problem is predicting the sweet spot where one would
> expect a large number of duplicates.  For instance in your example
> of sorting grades, it wouldn't make sense to have 100 buckets for
> 20 students but it might make sense to have four since one could
> easily take 20 sheets of 8x11 paper and drop them into one of
> four buckets.  Depending upon the curve one set different easy
> ranges so the 20 sheets split about even.  Sorting 5 sets of paper
> by hand wouldn't be too hard.  Sorting 20 tests into 100 buckets
> would involve a lot of movement and hunting then picking up the
> papers would take even more time.  This would swamp the time saved
> by not having to handle any paper more than once.
>
> Heck, not being the academic type I haven't had to deal with
> grading papers.  It seems to me that grading papers needn't
> involve sorting them.  One would merely need to grade the
> papers first, write the scores in a ledger, then normalize the
> scorea into the letter grades, and finally make a second pass
> through the tests and put the letter grades on them.
>
> I guess the optimal sort algorithm depends upon the resources
> available.  Back in the day we did an 8 tape(drive) sort on the annual
> transaction logs.  It would take us days since we didn't have
> sufficient disk space to store all the records, making an index
> sort impractical.  As I recall the monthly transaction logs
> would span about 4 9track tapes each.  The computer only had
> 19K memory stored in 12 6bit character words.  We had 4 5M drives
> and 4 20M drives but they stored current account records for
> online access and the online programs.  Heck, I got in trouble
> for storing a program that only ran once a month on disk rather
> than punch cards.

Did i say the pointer approach was implemented in -97 to solve *A HARD
PROBLEM*

Date Subject Author
1/3/13 JT
1/3/13 JT
1/3/13 JT
1/3/13 JT
1/4/13 JT
1/8/13 kiru.sengal@gmail.com
1/8/13 JT
1/8/13 kiru.sengal@gmail.com
1/8/13 JT
1/8/13 JT
1/8/13 JT
1/8/13 forbisgaryg@gmail.com
1/8/13 JT
1/8/13 kiru.sengal@gmail.com
1/8/13 JT
1/8/13 forbisgaryg@gmail.com
1/9/13 JT
1/9/13 kiru.sengal@gmail.com
1/9/13 kiru.sengal@gmail.com