Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


JT
Posts:
1,388
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 UTC8, 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*



