Sort at least 5 times faster then native and quicksort

jonas.t...@gmail.com

unread,

Oct 29, 2017, 12:27:47 AM10/29/17

to

My sort Algorithm is at least 5 time faster then native and quicks sort for densely populated samples "where numbers have 1 or more occurences".

But usual there is some weird aspect i can't find out what i do wrong, if you set startrange for the random numbergererator higher then 0 values will turn up undefined i don't get it.

But the timings are correct, 5 times faster for 100k of integers, and best of all the algorithm is linear, but it purely for sorting numbers.

You guys probably see right away what goes wrong, when you change the start range. I do not.

http://anybase.co.nf/jtsort.html

jonas.t...@gmail.com

unread,

Oct 29, 2017, 12:41:23 AM10/29/17

to

If you can see ways to make it faster i would like to hear.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 6:54:00 AM10/29/17

to

Den söndag 29 oktober 2017 kl. 05:27:47 UTC+1 skrev jonas.t...@gmail.com:

For 1 million values jtsort take 543 ms javascript 3948 ms so it is 8 time faster.

For 10 million values jtsort take 30474 ms "30 sec", native sort more then 207047 "3 minutes 27 sec".

jonas.t...@gmail.com

unread,

Oct 29, 2017, 7:33:15 AM10/29/17

to

For densely populated samples at least 5 times faster then javascript native sort and quicksort. Well it is just to sort numbers, but there is other approaches to sort strings, that are multiple times faster then quicksort and javascript native sort.
When script first load it takes time 5-10 sec because i generate and printout 99000 numbers to a form, if you chose more then 100000 values it will render out results alot faster but not the actual values generated and sorted.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 7:37:52 AM10/29/17

to

Den söndag 29 oktober 2017 kl. 05:27:47 UTC+1 skrev jonas.t...@gmail.com:

<HTML>
<HEAD><TITLE>SORT</TITLE></HEAD>
<BODY>

<TABLE BGCOLOR="WHITE" BORDER=1><TH>GENERATE RANDOM NUMBERS</TH> <TR><TD>
<FORM NAME=random onSubmit="newrandom(); return false;">
Smallest number <input type="text" name="startrange" value="0"><br>
Biggest number <input type="text" name="endrange" value="99000"><br>
Values to generate <input type="text" name="xvalues" value="99000"><P>
<input type="submit" value="GENERATE"><P>
VALUES TO SORT "PRINTOUT ONLY FOR ARRAY WITH LESS THEN 100000 ELEMENTS"<BR>
<TEXTAREA NAME=sort COLS=120 ROWS=8>
</TEXTAREA><BR>
</FORM>
</TD></TR></TABLE>

<TABLE BGCOLOR="WHITE" BORDER=!>
<TH>COMPARE SORT TIMINGS</TH>
<TR><TD>CHOOSE SORT ALGORITHM
<select id="mySelect" onchange="chosesort();">
<option value="index">JT_INDEXSORT</option>
<option value="javascript">javascript_sort</option>
<option value="quick">QUICKSORT</option>
</select>
<FORM NAME=sort onSubmit="chosesort(); return false;">
<input type=submit value="SORT"> TIME MS <input type="text" name="functime" value=""><br>
SORTED VALUES PRINTOUT "ONLY IF ARRAY HAS LESS THEN 100000 ELEMENTS":<BR>
<TEXTAREA TYPE=TEXT NAME=distrib COLS=120 ROWS=23>
</TEXTAREA><BR>
</FORM>
</TD></TR></TABLE>
</BODY>

<SCRIPT LANGUAGE="Javascript">
newrandom();
chosesort();

function newrandom(){
dval=new Array();
start=document.random.startrange.value;
end=document.random.endrange.value;
start=Number(start);
end=Number(end);
numberofvalues=document.random.xvalues.value;
//Generate random values
for (var i=0;i<numberofvalues;i++){
number=Math.floor(Math.random() * end) + start;
dval[i]=number;
}
if (dval.length<100000) {document.random.sort.value=dval;} else {document.random.sort.value=dval.length+" elements in array"};
}

function chosesort(){

selectedsort = document.getElementById("mySelect").value;
if (selectedsort=="index"){jtindexsort();}
else if (selectedsort=="javascript"){javascriptNativesort();}
else if (selectedsort=="bubble"){bubbleSort();}
else if (selectedsort=="quick"){ quickSort(dval,0,numberofvalues);}
if (dval.length<100000) {printout();} else {document.sort.distrib.value=dval.length+" sorted in array"};
}

function quickSort(arr, left, right)
{
var starttime = new Date().getTime();
var i = left;
var j = right;
var tmp;
pivotidx = (left + right) / 2;
var pivot = parseInt(arr[pivotidx.toFixed()]);
/* partition */
while (i <= j)
{
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}

/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
var endtime = new Date().getTime();
var timed = endtime - starttime;
document.sort.functime.value=timed;
return arr;
}

function javascriptNativesort(){
var starttime = new Date().getTime();
dval = dval.sort(sortNumber);
var endtime = new Date().getTime();
var timed = endtime - starttime;
document.sort.functime.value=timed;
}

function sortNumber(a, b)
{
return a - b;
}

function jtindexsort(){
var starttime = new Date().getTime();
countval= new Array();
//Initiate array range
for (j=start;j<end;j++){
countval[j]=0;
}
var temp;

//Put them on correct index
for (var i=0;i<numberofvalues;i++){
temp=dval[i];
countval[temp]=countval[temp]+1;
}
p=0;
dval = [];

for (var j=start;j<end;j++){
temp=countval[j]
for (var k=0;k<temp;k++){
dval[p]=j;
p++;
}
}

var endtime = new Date().getTime();
var timed = endtime - starttime;
document.sort.functime.value=timed;
}

function printout(){
valdist="";
for (var j=0;j<numberofvalues;j++){
valdist+=dval[j]+",";
}
document.sort.distrib.value=valdist;
}
</SCRIPT>

</HTML>

Ben Bacarisse

unread,

Oct 29, 2017, 8:10:59 AM10/29/17

to

jonas.t...@gmail.com writes:

> My sort Algorithm is at least 5 time faster then native and quicks
> sort for densely populated samples "where numbers have 1 or more
> occurences".

It's not really your algorithm, it's your implementation of a well-known
algorithm.

> But usual there is some weird aspect i can't find out what i do wrong,
> if you set startrange for the random numbergererator higher then 0
> values will turn up undefined i don't get it.

You don't zero the right number of elements in countval. This, in turn,
is because you do

number=Math.floor(Math.random() * end) + start;

so the numbers range from start to start+end-1.

> But the timings are correct, 5 times faster for 100k of integers, and
> best of all the algorithm is linear, but it purely for sorting
> numbers.

Quoting a factor is not very helpful. It's likely that you are doing
some form of counting sort, so you can make it any number of times
faster simply by sorting a larger set. Equally, you can probably make
it lower by choosing a small set with a huge range.

--
Ben.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 8:53:38 AM10/29/17

to

Well it is my algorithm invented out of bucket sort that was known in the 80's. This was not known because back then the dinosaurs did think different because of memory requirment and so on. But you see average Joe did it already back then because they did not understand better and when they saw that it was really good for big samples with a small range they knew it was faster and better then quicksort. But it was never appreciated.

So it really is my algorithm "although one can't own algorithms i invented it", i was stupid enough to implement it to sort integers on a spectrum.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 9:01:27 AM10/29/17

to

Well it could been a pet using basic in the 70's

jonas.t...@gmail.com

unread,

Oct 29, 2017, 9:07:07 AM10/29/17

to

Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:

Can you understand the bug that occur when the sample range start is not zero Ben?
I tried to figure it out but i just do not seem to find why and where it occur, i suspect it occur when the values written to the array somehow, but i really do not get it.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 9:23:29 AM10/29/17

to

Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:

Well i can agree it is funny "although albeit a bit worrying" when the strawmans approaches tend to be so much faster then the experts LoL

Ben Bacarisse

unread,

Oct 29, 2017, 10:37:26 AM10/29/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:

<snip>

>> > But usual there is some weird aspect i can't find out what i do wrong,
>> > if you set startrange for the random numbergererator higher then 0
>> > values will turn up undefined i don't get it.
>>
>> You don't zero the right number of elements in countval. This, in turn,
>> is because you do
>>
>> number=Math.floor(Math.random() * end) + start;
>>
>> so the numbers range from start to start+end-1.

<snip>

> Can you understand the bug that occur when the sample range start is
> not zero Ben?

Yes. What did you not understand in the explanation?

(Please try trimming quoted material in your posts.)

<snip>
--
Ben.

Ben Bacarisse

unread,

Oct 29, 2017, 10:47:14 AM10/29/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:
>>
>> > My sort Algorithm is at least 5 time faster then native and quicks
>> > sort for densely populated samples "where numbers have 1 or more
>> > occurences".
>>
>> It's not really your algorithm, it's your implementation of a well-known
>> algorithm.

<snip>

> Well it is my algorithm invented out of bucket sort that was known in
> the 80's. This was not known because back then the dinosaurs did think
> different because of memory requirment and so on. But you see average
> Joe did it already back then because they did not understand better
> and when they saw that it was really good for big samples with a small
> range they knew it was faster and better then quicksort. But it was
> never appreciated.

I don't see how you can claim to know the literature well enough to make
grandiose claims like this. Knuth (in TAOCP) says it was invented in
the early 1950s. I knew it well in 1970s though I could not have told
you then how invented it.

I think you should speak to someone you trust about these thoughts.
It's not normal for someone starting out in a field to believe they have
invented significant things hitherto not spotted by "the dinosaurs" but
which, nonetheless, go unappreciated.

<snip>
--
Ben.

Ben Bacarisse

unread,

Oct 29, 2017, 10:51:02 AM10/29/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:
>>
>> > My sort Algorithm is at least 5 time faster then native and quicks
>> > sort for densely populated samples "where numbers have 1 or more
>> > occurences".
>>
>> It's not really your algorithm, it's your implementation of a well-known
>> algorithm.

<snip>

> Well i can agree it is funny "although albeit a bit worrying" when the
> strawmans approaches tend to be so much faster then the experts LoL

Who are you agreeing with? Did someone say it was funny. If you don't
know what the experts know, of course you might think it's something
new. That's not worrying for the experts.

--
Ben.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:13:23 AM10/29/17

to

You are silly Ben the 1950's computers used transistor and radio tubes, the memories was mercury delay line programs and data was either on card or switches.

Well you can ask the guys that renovated Edsac to implement my algorithm, they have to be very fast flipping the switches read the data in LoL

Well your a funny guy Ben, not that bright but funny ;)

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:35:47 AM10/29/17

to

http://www.cs.cmu.edu/~adityaa/211/Lecture12AG.pdf

Ben Bacarisse

unread,

Oct 29, 2017, 11:46:47 AM10/29/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 15:47:14 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:
>>
>> > Den söndag 29 oktober 2017 kl. 13:10:59 UTC+1 skrev Ben Bacarisse:
>> >> jonas.t...@gmail.com writes:
>> >>
>> >> > My sort Algorithm is at least 5 time faster then native and quicks
>> >> > sort for densely populated samples "where numbers have 1 or more
>> >> > occurences".
>> >>
>> >> It's not really your algorithm, it's your implementation of a well-known
>> >> algorithm.
>> <snip>
>> > Well it is my algorithm invented out of bucket sort that was known in
>> > the 80's. This was not known because back then the dinosaurs did think
>> > different because of memory requirment and so on. But you see average
>> > Joe did it already back then because they did not understand better
>> > and when they saw that it was really good for big samples with a small
>> > range they knew it was faster and better then quicksort. But it was
>> > never appreciated.
>>
>> I don't see how you can claim to know the literature well enough to make
>> grandiose claims like this. Knuth (in TAOCP) says it was invented in
>> the early 1950s. I knew it well in 1970s though I could not have told
>> you then how invented it.

<snip>

> You are silly Ben the 1950's computers used transistor and radio
> tubes, the memories was mercury delay line programs and data was
> either on card or switches.

No, it's silly of you to question a very well-researched work like
Knuth's TAOCP. Harold Seward's in 1954 PhD thesis is even available
online. You can see the algorithm there as pain as day. You think your
limited knowledge of computer history is all there is. Some algorithms
were even invented before there were digital computers.

> Well you can ask the guys that renovated Edsac to implement my
> algorithm, they have to be very fast flipping the switches read the
> data in LoL

You don't need a computer to have an algorithm, but as it happens,
Harold Seward's work was motivated by having very little fast memory.
You therefore need a method that works well with very slow memory. A
counting sort is very good for that situation.

> Well your a funny guy Ben, not that bright but funny ;)

Have you heard of the Dunning-Kruger effect?

--
Ben.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:50:00 AM10/29/17

to

Nope should i?

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:53:02 AM10/29/17

to

You see Ben one do not invent algorithms that superior and never use them and teach them.

That is how i know it "BULL" so to speak, well you get what i mean....

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:58:56 AM10/29/17

to

You see this is so easy a 10 year old could implement it, and it is way faster but it was never teached to anyone so noone ever used it to sort LoL

The general problem for you ENTP guys doing problem solving is you lack the ability to think outside the box. You can only build your knowledge on already existing approaches that you master. You are the caretakers om information theoretical approaches...... Not the invontors......
Yeah you make sense Ben, "BULL" sense

Ben Bacarisse

unread,

Oct 29, 2017, 12:18:35 PM10/29/17

to

jonas.t...@gmail.com writes:
<snip>

> You see this is so easy a 10 year old could implement it, and it is
> way faster but it was never teached to anyone so noone ever used it to
> sort LoL

What? Now you claim to know what is taught. It is in TAOPC and it was
taught in the university I taught at. Unlike you, I can't claim to be
an expert in what other universities teach.

> The general problem for you ENTP guys doing problem solving is you
> lack the ability to think outside the box. You can only build your
> knowledge on already existing approaches that you master. You are the
> caretakers om information theoretical approaches...... Not the
> invontors...... Yeah you make sense Ben, "BULL" sense

And you now claim to know if I am or am not creative. Is there really
no limit to what you think you know?

--
Ben.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 12:36:28 PM10/29/17

to

Well Ben i actually thought you knew about Myer Briggs, maybe you should check it out. Well i have no fear for my intellects i know my shortcomings i am sloppy but intelligent far above Mensa qualities. More like on in a million.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 12:48:12 PM10/29/17

to

Den söndag 29 oktober 2017 kl. 17:18:35 UTC+1 skrev Ben Bacarisse:

The thing is you do not make sense Ben, what you say do not make sense, that is why i call it bull Ben. If there is a faster algorithm that is at least a multiple of times faster then Quicksort and so easy to learn that you could teach it to a 10 year old. Why isn't it used, why was it not used i have done my share of record sorting using quicksort you should know.

So i know it wasn't teached and noone i saw used it at university.

Ben Bacarisse

unread,

Oct 29, 2017, 2:02:08 PM10/29/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 17:18:35 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:
>> <snip>
>> > You see this is so easy a 10 year old could implement it, and it is
>> > way faster but it was never teached to anyone so noone ever used it to
>> > sort LoL
>>
>> What? Now you claim to know what is taught. It is in TAOPC and it was
>> taught in the university I taught at. Unlike you, I can't claim to be
>> an expert in what other universities teach.

<snip>

> So i know it wasn't teached and noone i saw used it at university.

How do you know that?

--
Ben.

jonas.t...@gmail.com

unread,

Oct 29, 2017, 11:51:47 PM10/29/17

to

Den söndag 29 oktober 2017 kl. 19:02:08 UTC+1 skrev Ben Bacarisse:
> jonas.t...@gmail.com writes:
>
> > Den söndag 29 oktober 2017 kl. 17:18:35 UTC+1 skrev Ben Bacarisse:
> >> jonas.t...@gmail.com writes:
> >> <snip>
> >> > You see this is so easy a 10 year old could implement it, and it is
> >> > way faster but it was never teached to anyone so noone ever used it to
> >> > sort LoL
> >>
> >> What? Now you claim to know what is taught. It is in TAOPC and it was
> >> taught in the university I taught at. Unlike you, I can't claim to be
> >> an expert in what other universities teach.
> <snip>
> > So i know it wasn't teached and noone i saw used it at university.
>
> How do you know that?
>
> --
> Ben.

Well we had one or two algorithm classes, when it come to speed there was nothing else then quicksort and maybe bucketsort in rare cases.

Ben Bacarisse

unread,

Oct 30, 2017, 5:31:45 AM10/30/17

to

jonas.t...@gmail.com writes:

> Den söndag 29 oktober 2017 kl. 19:02:08 UTC+1 skrev Ben Bacarisse:
>> jonas.t...@gmail.com writes:
>>
>> > Den söndag 29 oktober 2017 kl. 17:18:35 UTC+1 skrev Ben Bacarisse:
>> >> jonas.t...@gmail.com writes:
>> >> <snip>
>> >> > You see this is so easy a 10 year old could implement it, and it is
>> >> > way faster but it was never teached to anyone so noone ever used it to
>> >> > sort LoL
>> >>
>> >> What? Now you claim to know what is taught. It is in TAOPC and it was
>> >> taught in the university I taught at. Unlike you, I can't claim to be
>> >> an expert in what other universities teach.
>> <snip>
>> > So i know it wasn't teached and noone i saw used it at university.
>>
>> How do you know that?
>

> Well we had one or two algorithm classes, when it come to speed there
> was nothing else then quicksort and maybe bucketsort in rare cases.

Oh, sorry. You only meant that you weren't taught it? I thought you
where making a more general point with "it was never teached to anyone".
Anyway, I think you were short-changed by those algorithm courses.
There's a lot more to sorting the quicksort and bucket sort. Rest
assured that many students are taught about counting sort. In fact it
is soften used as as the sort function for the buckets in a bucket sort.

--
Ben.

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:14:14 AM10/30/17

to

No i tell you noone have ever been taught it... Because it was to simple and to fast, so it would have killed the dinosaurs.

Ben Bacarisse

unread,

Oct 30, 2017, 6:31:49 AM10/30/17

to

> No i tell you noone have ever been taught it... Because it was to
> simple and to fast, so it would have killed the dinosaurs.

Well I can't stop you telling me this but (a) I was taught it, and (b)
it is trivial to find lots of sets of course notes online that include
counting sort in the content. What is it in your character that lets
you deny such an obviously verifiable fact?

BTW, how are you getting on with the bug you could not find?

--
Ben.

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:32:46 AM10/30/17

to

I could try do something that sort data not just numbers, but then it would be nice if someone could point me to the fastest implemented algorithm so far. "That is somewhat general purpose for any dataset".

So i know where to set the bar.

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:35:24 AM10/30/17

to

It is not a bug in the algorithm Ben it is a feature to be able to optimise the algorithm by setting the range of the input data. But it is a bug in my script for sure.

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:37:24 AM10/30/17

to

By implementation i mean in javascript, i do not intend to implement someone else wheel....

I prefer my own.

Wally W.

unread,

Oct 30, 2017, 6:40:11 AM10/30/17

to

On Mon, 30 Oct 2017 03:14:10 -0700 (PDT), jonas.t...@gmail.com
wrote:

Everything that could be taught was covered in "one or two algorithm
classes," right?

We don't need quicksort, bucket sort, heap sort, etc., anymore because
you have overcome the "dinosaurs" by publicizing the counting sort,
right?

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:44:43 AM10/30/17

to

So would you like the imput range of data to be possible to parametrise/parameterise ?

Should one think that the input range of elements in dataset "min max bitwidth" is known and inputs to the algorithm?

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:48:40 AM10/30/17

to

To be honest Wally i keep bucketsort, it is good when the range is spreadout and the datapoints separated "i like keyed buckets" , all glory to bucketheads.

As long you do not make the buckets gravitate to effect eachother.

jonas.t...@gmail.com

unread,

Oct 30, 2017, 6:50:34 AM10/30/17

to

Yeah the bugs they keep coming, fortunately there is people more driven than me to find them and correct them.

Ben Bacarisse

unread,

Oct 30, 2017, 10:19:47 AM10/30/17

to

jonas.t...@gmail.com writes:

> Den måndag 30 oktober 2017 kl. 11:31:49 UTC+1 skrev Ben Bacarisse:

<snip>

>> BTW, how are you getting on with the bug you could not find?

<snip>

> It is not a bug in the algorithm Ben

Yes, I know. In fact I know exactly what the bug.

<snip>
--
Ben.

jonas.t...@gmail.com

unread,

Nov 2, 2017, 5:38:59 PM11/2/17

to

I too, i don't know why i put it there because it wasn't there to start with, but now it is gone.

jonas.t...@gmail.com

unread,

Nov 2, 2017, 5:42:06 PM11/2/17

to

Well the bug was that I reinitialised the array, now it is probably 10 times faster. In a dense dataset population where each entry has at least 1 entry/member.