Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
JT

Posts: 1,148
Registered: 4/7/12
Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
Posted: Jan 8, 2013 1:32 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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?


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>
>
> > <HEAD><TITLE>SORT</TITLE></HEAD>
>
> > <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
>
> > 3,71,247,207,237,251,159,129,125,209,105,239,100,242,102,116,169,166,70,37,
>
> > 9
>
> > 6,218,232,218,37,139,221,63,180,113,190,173,120,5,31,146,19,217,89,255,196,
>
> > 4
>
> > 4,125,204,218,129,97,141,101,53,143,127,245,142,66,112,96,128,87,61,106,217 ,
>
> > 217,98,71,184,115,182,247,25,131,165,226,4,186,132,16,101,130,223,56,238,14
>
> > 9
>
> > ,
>
> > 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,89,17,217,99,22,191,216,69,26,255,126 ,
>
> > 56,3,206,77,50,84,193,10,7,64,244,173,162,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,5
>
> > 0
>
> > ,
>
> > 237,29,33,129,202,217,38,63,39,104,171,10,133,65,109,230,142,59,79,43,83,8
>
> > 0
>
> > ,
>
> > 159,47,185,96,177,126,155,82,29,122,92,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,50,218,158,136,143,99,97,144,69,68,19
>
> > 6
>
> > ,
>
> > 141,144,208,125,79,213,135,36,148,38,62,35,30,82,4,180,59,66,219,233,122,2
>
> > 4...
>
> läs mer »




Date Subject Author
1/3/13
Read My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/3/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/3/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/3/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/4/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
kiru.sengal@gmail.com
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
kiru.sengal@gmail.com
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
forbisgaryg@gmail.com
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
kiru.sengal@gmail.com
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/8/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
forbisgaryg@gmail.com
1/9/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
JT
1/9/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
kiru.sengal@gmail.com
1/9/13
Read Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
kiru.sengal@gmail.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.