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

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,166
Registered: 4/7/12
Re: My sorting algorithm that counts in values in arrays, JTsort or Countsort
Posted: Jan 8, 2013 2:06 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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?
> 2) What if the range of integers is O(inputsize^3 ) ?
> 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 asking there is no hits misses? Since there is
no comparissons, you just find out how many digits in the element to
sort and index it into the pointer structure using the recursive
algorithm.
It works just like the array implementation without the limits of it.
There is no hits misses in the array implementation just counted
occurences..... or what do you mean you just have to keep track of
numbers of digits togo and if it is a zero or one to read in.
>
>
>
>
>
>
>
>
>
>

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