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 1:54 AM

On 8 Jan, 07:47, Kiru Sengal <kiru.sen...@gmail.com> wrote:
> On Tuesday, January 8, 2013 1:32:47 AM UTC-5, JT 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.
>
> Ok, JTsort has no aftersort.  Not sure how I offended you as I never mentioned JT having an after.
>
>
>

> > 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.
>
> 1) What if you are not sorting integers?

You will have todo a binary conversion of the string.

> 2) What if the range of integers is O(inputsize^3 ) ?
The range if of no importance in the pointer implementation, since it
do not allocate memory and indecing empty buckets. What is important
is the average digit size and the number of unique members in dataset.
_
x digit* S(unique members)=memory requirments.

> 3) What about cache hits/misses when you bounce around in your bucket (sorry, what do you call these? JT units?) array for every input integer read?
I am not sure what you going at here.
>
>
>
>
>
>
>
>
>
>

> > > > 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.
>
> How did they use the tabulating machine to help with U.S. census before you were born?
>
>
>
>
>
>
>
>
>

> > > > //**********************************************
>
> > > > //                        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
>
> > > > ,...
>
> 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