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 4:06 AM

On 8 Jan, 07:32, JT <jonas.thornv...@gmail.com> wrote:
> On 8 Jan, 07:10, Kiru Sengal <kiru.sen...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>

> > On Thursday, January 3, 2013 10:05:28 PM UTC-5, JT wrote:
> > > I once created this algorithm that works a bit backward it actually
>
> > > first create the range of numbers in an array and actually just count
>
> > > them in to different slots in an array no sorting needed. Was i the
>
> > > first person who came up with this idea? I am not that mathematically
>
> > > inclined although i enjoy solve problems with mathematics. As i see it
>
> > > for 100 MB of values it must be superior to any other sorting
>
> > > algorithm because it actually do not sort anything just count it, and
>
> > > this will work as long there is memory to use this type of sort.
>
> > It doesn't sort, just counts it, but will work as a sort :)
>
> > > However there must be a limit to the range/size of numbers relative
>
> > > the amount of data to sort, ***at what size of numbers*** will the
>
> > > best algorithm beat countsort using 10TB data?
>
> > Depends.  n*log(n) sorts like quicksort might beat it even if your algorithm is (n) for specific "limit/range/size of numbers relative..."
>
> I am kind of tired of numbnuts like you this is not radixsort/
> bucketsort, this is rapidsort aka JTsort there is no attached data
> just the index, so there is no aftersort. It index in linear time,
> there is no sort.
> Although this array implementation indeed have memory shortcomings, my
> pointer implementation working at digit level have none other then
> that the unique values within set must fit in memory. This is so much
> better then anything else that it make bubblesort look freakishly fast
> compared to quicksort, that quicksort look freakishly slow compare to
> JTsort.
>
>
>

> > > Just from reasoning this algorithm  will beat any other algorithm
>
> > > sorting >1 TB data using numbers ranging from 0 - 2^20 on any standard
>
> > > computer given a language that allow an array with 1 048 576 slots.
>
> > > 50
>
> > 1TB of purely 32 bit integers equals 2.5x10^11 integers.
> > With a range of 1million values, your data set has on average 250 thousand integers at every number in that range.  Is this what you had in mind?

Yes i was thinking 18 bit * 1 000 000 = 2 250 000 bytes memory
requirment, but i see now . I have no idea what programming language
will allow this but without doubt Python, and maybe Java.
But i see now maybe 19-20 bit would be no problem, this is of course
no use for sorting text strings, only 2.5 char (.

But just as you imply it may be enough to sort US citizens by birth or
social security number. Which isn't that bad, but can not really
compete with a dynamic pointer solution where you basicly could sort
anything.
> As i said my recursive pointer implementation done -97 only use.
> _
> x digit * S=memory requirments*** "here overlined x means average
> number of digits * unique members of the set"
> (You just save a single occurences of each value and their accompanied
> counter/index within the pointer structure the sorting terms can
> therefor have any length unlike the array implementation)
>
>
>

> > > Please  inform with if i am wrong.
>
> > > PS  Does this really qualify as a sorting algorithm.
>
> > 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,..).
>
> Well since JTsort/rapidsort runs in linear time one have to wonder why
> it has not been used historically.
>
>
>
>
>
>
>
>
>

> > > //**********************************************
>
> > > //                        Algorithm
>
> > > //dval is a string of values ranging 0-255 separated by ","
>
> > > //**********************************************
>
> > > function jtsort(){
>
> > > //The actual (?_sort_?)
>
> > > dist=document.encipher.cipher.value;
>
> > > dval = dist.split(",");
>
> > > countval= new Array();
>
> > > for (j=0;j<256;j++){
>
> > > countval[j]=0;
>
> > > }
>
> > > for (i=0;i<dval.length-1;i++){
>
> > >  temp=dval[i];
>
> > >  countval[temp]=countval[temp]+1;
>
> > > }
>
> > > //Creatin the (?_sort_?) output
>
> > > temp2=0;
>
> > > valdist="";
>
> > > for (j=0;j<256;j++){
>
> > >   temp2=countval[j]
>
> > >   for (k=0;k<temp2;k++){
>
> > >    valdist=valdist+j+",";
>
> > >   }
>
> > > }
>
> > > document.dasort.distrib.value=valdist;
>
> > > }
>
> > > //*************END***************
>
> > > 8 BITSORT IMPLEMENTATION:
>
> > > Below an example implementation to try out in your browser, as you
>
> > > can
>
> > > understand
>
> > > javascript isn't exactly ideal. But the idea is there.
>
> > > <HTML>
>
>
> > > <BODY>
>
> > > <SCRIPT LANGUAGE="Javascript">
>
> > > function jtsort(){
>
> > > dist=document.encipher.cipher.value;
>
> > > dval = dist.split(",");
>
> > > countval= new Array();
>
> > > for (j=0;j<256;j++){
>
> > > countval[j]=0;
>
> > > }
>
> > > for (i=0;i<dval.length-1;i++){
>
> > >  temp=dval[i];
>
> > >  countval[temp]=countval[temp]+1;
>
> > > }
>
> > > temp2=0;
>
> > > valdist="";
>
> > > for (j=0;j<256;j++){
>
> > >   temp2=countval[j]
>
> > >   for (k=0;k<temp2;k++){
>
> > >    valdist=valdist+j+",";
>
> > >   }
>
> > > }
>
> > > document.dasort.distrib.value=valdist;
>
> > > }
>
> > > </SCRIPT>
>
> > > <BODY>
>
> > > <TABLE WIDTH=100%><TR><TD BGCOLOR=BLACK ALIGN=CENTER WITH=50%>
>
> > > <FONT COLOR=WHITE>
>
> > > <FORM NAME=dasort onSubmit="jtsort(); return false;">
>
> > > (n)sort ALGO
>
> > > <input type=submit value="SORT"><P>
>
> > > SORTED VALUES:
>
> > > <TEXTAREA TYPE=TEXT NAME=distrib COLS=40 ROWS=6></TEXTAREA><BR>
>
> > > </FORM>
>
> > > <FORM NAME=encipher onSubmit="encrypt(); return false;">
>
> > > VALUES TO SORT:
>
> > > <TEXTAREA NAME=cipher COLS=40
>
> > > ROWS=6>99,22,191,216,69,26,255,126,56,3,206,77,50,84,193,10,7,64,244,173,16
>
> > > 2
>
> > > ,
>
> > > 72,84,162,27,245,33,133,249,201,9,128,78,135,74,115,135,26,237,12,147,89,2
>
> > > 3
>
> > > 1,44,17,174,195,142,232,165,52,130,113,7,101,136,93,110,253,46,82,211,122,2
>
> > > 4
>
> > > 1,2,77,132,103,91,167,105,123,80,50,237,29,33,129,202,217,38,63,39,104,171,
>
> > > 1
>
> > > 0,133,65,109,230,142,59,79,43,83,80,159,47,185,96,177,126,155,82,29,122,92,
>
> > > 1
>
> > > 00,40,21,125,19,70,93,247,11,46,26,35,227,138,137,108,58,19,16,115,24,236,9
>
> > > 9
>
> > > ,
>
> > > 8,151,209,195,38,47,95,47,231,102,80,105,239,161,166,55,244,195,164,245,50 ,
>
> > > 218,158,136,143,99,97,144,69,68,196,141,144,208,125,79,213,135,36,148,38,62 ,
>
> > > 35,30,82,4,180,59,66,219,233,122,244,220,147,114,191,67,195,112,180,169,214 ,
>
> > > 112,170,44,170,168,163,6,90,132,124,156,76,29,52,38,237,138,177,14,130,248,
>
> > > 2
>
> > > 0,238,112,49,137,101,48,85,232,241,3,213,150,10,3,11,217,52,45,22,101,226,2
>
> > > 3
>
> > > ,
>
> > > 212,121,237,254,90,245,172,199,255,68,20,75,26,136,145,93,251,229,34,199,4
>
> > > 8
>
> > > ,
>
> > > 215,103,179,63,190,196,111,206,90,195,211,11,226,207,148,181,36,165,89,133 ,
>
> > > 71,247,207,237,251,159,129,125,209,105,239,100,242,102,116,169,166,70,37,96 ,
>
> > > 218,232,218,37,139,221,63,180,113,190,173,120,5,31,146,19,217,89,255,196,44 ,
>
> > > 125,204,218,129,97,141,101,53,143,127,245,142,66,112,96,128,87,61,106,217,2
>
> > > 1
>
> > > 7,98,71,184,115,182,247,25,131,165,226,4,186,132,16,101,130,223,56,238,149,
>
> > > 2
>
> > > 30,30,19,49,149,179,184,177,34,44,11,222,253,95,180,54,74,205,107,75,252,7,
>
> > > 1
>
> > > 15,226,209,70,132,70,88,108,152,167,89,17,217,99,22,191,216,69,26,255,126,5
>
> > > 6
>
> > > ,
>
> > > 3,206,77,50,84,193,10,7,64,244,173,162,72,84,162,27,245,33,133,249,201,9,1
>
> > > 2
>
> > > 8,78,135,74,115,135,26,237,12,147,89,231,44,17,174,195,142,232,165,52,130,1
>
> > > 1
>
> > > 3,7,101,136,93,110,253,46,82,211,122,241,2,77,132,103,91,167,105,123,80,50,
>
> > > 2
>
> > > 37,29,33,129,202,217,38,63,39,104,171,10,133,65,109,230,142,59,79,43,83,80,
>
> > > 1
>
> > > 59,47,185,96,177,126,155,82,29,122,92,100,40,21,125,19,70,93,247,11,46,26,3
>
> > > 5
>
> > > ,
>
> > > 227,138,137,108,58,19,16,115,24,236,99,8,151,209,195,38,47,95,47,231,102,8
>
> > > 0
>
> > > ,
>
> > > 105,239,161,166,55,244,195,164,245,50,218,158,136,143,99,97,144,69,68,196,
>
> > > 1
>
> > > 41,144,208,125,79,213,135,36,148,38,62,35,30,82,4,180,59,66,219,233,122,244 ,
>
> > > 220,147,114,191,67,195,112,180,169,214,112,170,44,170,168,163,6,90,132,124,
>
> > > 1
>
> > > 56,76,29,52,38,237,138,177,14,130,248,20,238,112,49,137,101,48,85,232,241,3 ,
>
> > > 213,150,10,3,11,217,52,45,22,101,226,23,212,121,237,254,90,245,172,199,255,
>
> > > 6
>
> > > 8,20,75,26,136,145,93,251,229,34,199,48,215,103,179,63,190,196,111,206,90,1
>
> > > 9
>
> > > 5,211,11,226,207,148,181,36,165,89,133,71,247,207,237,251,159,129,125,209,1
>
> > > 0
>
> > > 5,239,100,242,102,116,169,166,70,37,96,218,232,218,37,139,221,63,180,113,19
>
> > > 0
>
> > > ,
>
> > > 173,120,5,31,146,19,217,89,255,196,44,125,204,218,129,97,141,101,53,143,12
>
> > > 7
>
> > > ,
>
> > > 245,142,66,112,96,128,87,61,106,217,217,98,71,184,115,182,247,25,131,165,2
>
> > > 2
>
> > > 6,4,186,132,16,101,130,223,56,238,149,230,30,19,49,149,179,184,177,34,44,11 ,
>
> > > 222,253,95,180,54,74,205,107,75,252,7,115,226,209,70,132,70,88,108,152,167,
>
> > > 8
>
> > > 9,17,217,99,22,191,216,69,26,255,126,56,3,206,77,50,84,193,10,7,64,244,173,
>
> > > 1
>
> > > 62,72,84,162,27,245,33,133,249,201,9,128,78,135,74,115,135,26,237,12,147,89 ,
>
> > > 231,44,17,174,195,142,232,165,52,130,113,7,101,136,93,110,253,46,82,211,122 ,
>
> > > 241,2,77,132,103,91,167,105,123,80,50,237,29,33,129,202,217,38,63,39,104,17
>
> > > 1
>
> > > ,
>
> > > 10,133,65,109,230,142,59,79,43,83,80,159,47,185,96,177,126,155,82,29,122,9
>
> > > 2
>
> > > ,
>
> > > 100,40,21,125,19,70,93,247,11,46,26,35,227,138,137,108,58,19,16,115,24,236 ,
>
> > > 99,8,151,209,195,38,47,95,47,231,102,80,105,239,161,166,55,244,195,164,245,
>
> > > 5
>
> > > 0,218,158,136,143,99,97,144,69,68,196,141,144,208,125,79,213,135,36,148,38,
>
> > > 6
>
> > > 2,35,30,82,4,180,59,66,219,233,122,244,220,147,114,191,67,195,112,180,169,2
>
> > > 1
>
> > > 4,112,170,44,170,168,163,6,90,132,124,156,76,29,52,38,237,138,177,14,130,24
>
> > > 8
>
> > > ,
>
> > > 20,238,112,49,137,101,48,85,232,241,3,213,150,10,3,11,217,52,45,22,101,226 ,
>
> > > 23,212,121,237,254,90,245,172,199,255,68,20,75,26,136,145,93,251,229,34,199 ,
>
> > > 48,215,103,179,63,190,196,111,206,90,195,211,11,226,207,148,181,36,165,89,1
>
> > > 3...
>
> läs mer »

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