OT anyone know iterative quicksort?

[HERC777]

just paste the below into notepad, call it iqsort.html double click it
and your IE browser will run it. (neat! a universal programming
language we can all run!)

it falls out from the sort procedure. I got javascript quicksort
running, it's quick but it gets stack overflow after about 5000
elements.

Am I passing the array as a parameter alright? I think javascript
default is to pass pointers, that can be global.

Herc




<script language = "javascript">

l=0
r=0
stack=0
stuck = new Array
ARRAY_MAX = 10

function PUSH(l, r) {
stack++
stuck[stack] = l
stack++
stuck[stack] = r
}
function POP(l, r) {
r = stuck[stack]
stack--
l = stuck[stack]
stack--
}

function main()
{
i = 0
array1 = new Array
array2 = new Array

alert("The array is composed of the following values")

for(i=0; i<ARRAY_MAX; i++) {
array1 = parseInt(Math.random(1) * 100)
array2 = array1
}

alert (array1[1] + " " + array1[2] + " " + array1[3] + " " +
array1[4] + " " + array1[5])

iterative_qsort(array2, 0, ARRAY_MAX-1);

alert (array2[1] + " " + array2[2] + " " + array2[3] + " " +
array2[4] + " " + array2[5])

}


function iterative_qsort(tarray, left, right)
{

i=0
last=0
temp=0
position=0

if(left < right) {

/* Push -1's onto the stack as a signal to us in the
future that we've reached the bottom. */

PUSH(-1, -1);
PUSH(left, right);

finished = false
while (!finished) {

POP(left, right);

if((left == -1) && (right == -1)){
finished = true
}
else {

if(left < right) {
position = parseInt((left + right) / 2)

temp = tarray

;
tarray

= tarray[position];
tarray[position] = temp;

last = left;

for(i=left+1; i<=right; i++)
if(tarray < tarray

) {
last++;
temp = tarray[last];
tarray[last] = array;
tarray = temp;
}

temp = tarray

;
tarray

= tarray[last];
tarray[last] = temp;

PUSH(left, last-1);
PUSH(last+1, right);
}
}
}
}
}

main()

</script>​

​

​

 

[runonthespot]

Suggest reading this (very informative) article on quicksort
http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm
Which discusses the stack overflow problems often associated with
quicksorts, and how to mitigate them.

It's part of this good series on sorting in general.
http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/000_SortingOverview.htm

Also, cross-posting I believe is considered bad form..

 

[Fred Oz]

just paste the below into notepad, call it iqsort.html double click it
and your IE browser will run it. (neat! a universal programming
language we can all run!)

it falls out from the sort procedure. I got javascript quicksort
running, it's quick but it gets stack overflow after about 5000
elements.

Am I passing the array as a parameter alright? I think javascript
default is to pass pointers, that can be global.

Herc




<script language = "javascript">

The language attributes is depreciated, type is required.

<script type="text/javascript">

Ok, you got me. What is the point of this 'Quicksort'? I didn't work
at all, I could not be bothered to debug it. Below is a script that
uses 20 lines of code to generate an array of any length, with any
range, then sort it either ascending or descending. Tested it with
up to 100,000 terms.

The script is adapted from here:

<URL:http://www.coedu.usf.edu/wwwprog/sort_demo.html>

Incidentally, using the above link, a 'quicksort' requires over 5,000
compares and took nearly 20 seconds on my old laptop to sort 100
numbers. The 'jsSort' algorithm took 0.05 seconds to do 1,000
numbers in Firefox and 0.15 seconds in IE.

So the question remains: what is the point of a 'quicksort' except to
show how slow the algorithm is?

--
Fred

<script type="text/javascript">
function genArray(n,r) {
var a = [];
while(n--) {a[n] = Math.floor(Math.random() * r)}
return a;
}
function doSort(n,d,r) {
var z = genArray(n,r);
var start = new Date().getTime();
('a' == d)? z.sort(compA): z.sort(compD);
var end = new Date().getTime();
document.getElementById('result').innerHTML =
'That took ' + (end-start) + ' milliseconds<br>'
+ z.join(', ');
}
function compD(a,b) {
return ((a < b) ? 1 : ((a > b) ? -1 : 0));
}
function compA(a,b) {
return ((a < b) ? -1 : ((a > b) ? 1 : 0));
}
</script>
<form action="">
<input type="text" size="10" name="num">Number of terms<br>
<input type="text" size="10" name="range">Range of numbers<br>
<input type="button" value="Sort ascending" onclick="
doSort(this.form.num.value,'a',this.form.range.value);
">
<input type="button" value="Sort descending" onclick="
doSort(this.form.num.value,'d',this.form.range.value);
">
</form><br>
<span id="result">result goes here</span>

 

[googmeister]

Suggest reading this (very informative) article on quicksort

http://www.angelfire.com/pq/ja mesbarbetti/articles/sorting/0

01_Quicks...

The author of this article seems unaware of Bentley-McIlroy
3-way quicksort. Given that this is the modern quicksort
implementation in Java (for primitive types) and C (qsort),
this seems like a pretty serious omission. Like many sorting
algorithms, quicksort has some positive and some negative
features. If you want to learn about sorting, read Sedgewick's
Algorithms in X or Knuth.

 

[Douglas Crockford]

just paste the below into notepad, call it iqsort.html double click it

and your IE browser will run it. (neat! a universal programming
language we can all run!)

it falls out from the sort procedure. I got javascript quicksort
running, it's quick but it gets stack overflow after about 5000
elements.

Am I passing the array as a parameter alright? I think javascript
default is to pass pointers, that can be global.

Some of the browsers have pretty shallow stacks.

 

[HERC777]

my codes buggy, so's yours, so's theirs.

is the last box using an inbuilt Javascript sort function?

Herc

 

[Fred Oz]

my codes buggy, so's yours, so's theirs.

Mine's buggy? I'll cop that if you tell me why you think so. I ran
a 100,000 element array with a range of 10,000 and it worked fine.

OK, Firefox complained about a script taking too long to run, but
otherwise, fine. I think I only tested IE up to 10,000 - but who is
using 10,000 element arrays in JavaScript?.

is the last box using an inbuilt Javascript sort function?

Which 'last box'? In mine, you put a value in the number of elements
(say 10000) and the range (say 1000 or 100000).

 

[KBH]

just paste...into notepad, call it iqsort.html double click it

The following is not a quicksort but here is an example of the 'KBH Integer
Sort':

For i:= lw To hg Do
Begin
c[a]:= c[a] + 1;
End

where the un-sorted data is in the a-array .


And here is demonstration code of the 'KBH Integer Sort' :

Var
ag: string;
i, ii, t, lw, hg: integer;
a, c: array [0..999999] of integer;

begin
WriteLn('KBH Integer Sort');
WriteLn;
lw:= 0;
hg:= 999999;
Randomize;

For ii:= lw To hg Do
Begin
a[ii]:= Random(1000000);
End;

{Presrt;}
{Presrt determines smallest and largest a-array values if necessary and
applies translation relative to c-array declaration if necessary}

Write(' Enter any letter to begin sort: ');
ReadLn(ag);
WriteLn;

For i:= lw To hg Do
Begin
c[a]:= c[a] + 1;
End;

WriteLn(' [ Sort completed ]');
WriteLn;

{For t:= lw To hg Do
Begin
For j:= 1 To c[t] Do
Begin
WriteLn(t:5);
End;
End;}

For t:= lw To hg Do
Begin
If (c[t] <> 0) Then
Begin
WriteLn(' [ The first sorted number is: ', t:10, ' ]');
WriteLn(' [ There are ', c[t], ' of these numbers consecutive ]');
Break;
End;
End;

WriteLn;

For t:= hg DownTo lw Do
Begin
If (c[t] <> 0) Then
Begin
WriteLn(' [ The last sorted number is: ', t:10, ' ]');
WriteLn(' [ There are ', c[t], ' of these numbers consecutive ]');
Break;
End;
End;

ReadLn;
end.


And here is a link to the 'KBH Integer Sort' :

http://www.kbhscape.com/sort.htm

And that web page is due some editing...

 

[Lee]

KBH said:

just paste...into notepad, call it iqsort.html double click it

The following is not a quicksort but here is an example of the 'KBH Integer
Sort':

For i:= lw To hg Do
Begin
c[a]:= c[a] + 1;
End

where the un-sorted data is in the a-array .

Isn't that a Bucket Sort with a bucket size of 1?

 

[HERC777]

it didn't do anything on my IE 5.5. copied it twice.

the 'last box' on the URL you gave, says it uses javascript sort(),
what does that mean?

if you put a big text file in it it stuffs up and keeps stuffing up,
even on the 10 countries example..

Herc

 

[HERC777]

i think you're missing a line.

The KBH Integer Sort: b(a(i)) = a(i)
The array assignment count: c(a(i)) = c(a(i)) + 1

All you're doing is incrementing all the values, the second line above,
you don't even have a comparison operator anywhere.

Herc

 

[KBH]

i think you're missing a line.

The KBH Integer Sort: b(a(i)) = a(i)
The array assignment count: c(a(i)) = c(a(i)) + 1

No, b(a(i)) = a(i) is the fundamental operation. Combining the array
assignment count with the fundamental operation lead to the sophistication
of using
c(a(i)) = c(a(i)) + 1 entirely alone...which means that the two operations
have the fundamental relation.

All you're doing is incrementing all the values, the second line above,
you don't even have a comparison operator anywhere.

No, I'm not incrementing values. I'm counting the a(i) values and holding
the count at the a(i) value subscript location of the c-array...

A comparison operator is not needed. What is needed is a destination array
for the sort operation and the inherent structure of the array...Simple
output follows immediately after development of the c-array and this by
using only the logic of the c-array.

-----------------------------------------------------

Of course the random number generation that loaded the a-array were integers
0 <= n < upperbound .

Floats of the form of x.0 can be truncated to integers and translated to the
c-array declaration if they are larger than programming language integers.
Also, smaller floats could be multiplied by 10^n and truncated to integers.
And that leads to sorting by the truncated integer part of a float and then
sorting by a scaled and truncated previously fractional part of the float.

---------------------------------------------------------

 

[RobG]

it didn't do anything on my IE 5.5. copied it twice.

Ah, IE 5.

As far as I know, there are bits of JavaScript sort() not implemented
in IE 5. I can't tell you what they are, I don't have IE 5 and don't
have any links to info for you. :-(

I think the scripts here are OK for IE 5 (but I can't test them):

the 'last box' on the URL you gave, says it uses javascript sort(),
what does that mean?

It uses the same JavaScript sort algorithm that I used. The others
use 'manual' sorting algorithms implemented in JavaScript.

if you put a big text file in it it stuffs up and keeps stuffing up,
even on the 10 countries example..

I think it's your browser - all works fine for me (Firefox and IE 6).
Can you upgrade to a newer version of Firefox or Mozilla if IE 6
isn't an option?

 

[stephen]

:> just paste...into notepad, call it iqsort.html double click it

: The following is not a quicksort but here is an example of the 'KBH Integer
: Sort':

: For i:= lw To hg Do
: Begin
: c[a]:= c[a] + 1;
: End

: where the un-sorted data is in the a-array .

How does this differ from a Bucket sort?

Stephen

 

[KBH]

: The following is not a quicksort but here is an example of the 'KBH

Integer
: Sort':

: For i:= lw To hg Do
: Begin
: c[a]:= c[a] + 1;
: End

: where the un-sorted data is in the a-array .

How does this differ from a Bucket sort?

What are you putting in your buckets ?

I call b[a]:= a an assignment sort but I must call
c[a]:= c[a] + 1 a count sort...but not "the counting sort" as that is
something different.

In either case I am assigning or counting programming language integers and
I call it the 'KBH Integer Sort' because other so-called integer sorts are
really digit sorts and that is also something different.

 

[stephen]

:> : The following is not a quicksort but here is an example of the 'KBH
:> Integer
:> : Sort':
:>
:> : For i:= lw To hg Do
:> : Begin
:> : c[a]:= c[a] + 1;
:> : End
:>
:> : where the un-sorted data is in the a-array .

:>
:> How does this differ from a Bucket sort?
:>

: What are you putting in your buckets ?

The "buckets" contain the number of occurrences of each
item.

: I call b[a]:= a an assignment sort but I must call
: c[a]:= c[a] + 1 a count sort...but not "the counting sort" as that is
: something different.

That is a bucket sort. For example, see
http://www.brpreiss.com/books/opus4/html/page74.html

They use
++buckets[a]
which is equivalent to your
c[a:=c[a] + 1

: In either case I am assigning or counting programming language integers and
: I call it the 'KBH Integer Sort' because other so-called integer sorts are
: really digit sorts and that is also something different.

Your 'KBH Integer Sort' is better known as Bucket Sort.

Stephen

 

[KBH]

: The following is not a quicksort but here is an example of the 'KBH

Integer
: Sort':

: For i:= lw To hg Do
: Begin
: c[a]:= c[a] + 1;
: End

: where the un-sorted data is in the a-array .

How does this differ from a Bucket sort?

A web search for Bucket Sort and for Counting Sort finds that they both have
nested loops and I am not nesting loops. A web search for Integer Sort turns
up the Radix Sort and that is what I call a digit sort...

 

[stephen]

:> : The following is not a quicksort but here is an example of the 'KBH
:> Integer
:> : Sort':
:>
:> : For i:= lw To hg Do
:> : Begin
:> : c[a]:= c[a] + 1;
:> : End
:>
:> : where the un-sorted data is in the a-array .
:>
:> How does this differ from a Bucket sort?
:>

: A web search for Bucket Sort and for Counting Sort finds that they both have
: nested loops and I am not nesting loops. A web search for Integer Sort turns
: up the Radix Sort and that is what I call a digit sort...


Bucket Sort does not have nested loops, unless you count
the loop to print out the sorted values, but your code has
the same nested loops.

Stephen

 

[KBH]

:> : The following is not a quicksort but here is an example of the 'KBH

:> Integer
:> : Sort':
:>
:> : For i:= lw To hg Do
:> : Begin
:> : c[a]:= c[a] + 1;
:> : End
:>
:> : where the un-sorted data is in the a-array .
:>
:> How does this differ from a Bucket sort?
:>

: A web search for Bucket Sort and for Counting Sort finds that they both
have
: nested loops and I am not nesting loops. A web search for Integer Sort
turns
: up the Radix Sort and that is what I call a digit sort...


Bucket Sort does not have nested loops, unless you count
the loop to print out the sorted values, but your code has
the same nested loops.

Let's just continue to disagree.

One Bucket Sort link mentions combination with an Insertion Sort. So the
idea seems to be a finished array that only requires ordinary logic for a
later output. (The insertion step must be building a finished array from an
intermediate array with both of those arrays just different portions of the
same array.)

My finished array requires requires a particular logic for later output but
not additional sorting.

 

[HERC777]

OK, now I understand bucket sort I'll use that in future, as long as
the range of values of known. Thanks for the links I have enough info
now.

Herc