OT anyone know iterative quicksort?

[HERC777]

Right, got it going! I thought all sort algorithms had square
complexity worst case, and the recursive ones (quicksort, mergesort..)
had log linear average case.

That only works for a discrete range of values, but I adapted it using
a 2D array to store pointers to the file I'm sorting, sorting on line
length.

for (i=0;i<line;i++) {
ll = lines.length
linarr[ll] [full[ll]] = i
full[ll]++
}

Same as yours but it stores an array of pointers for each size so it
keeps track of the elements it sorted, instead of just counting them.

Then I just grab the elements back out in order.

sfile = ""
for (i=0;i<linesize;i++) {
for (j=0;j<full;j++) {
sfile += lines[linarr[j]]
}
}

Single pass sorting, 1,000s of times faster than my 1st attempt with
bubblesort.

Herc

 

[Lee]

KBH said:

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

In the general case, in which you have duplicate values, your
sort uses nested loops to read the values back out of the
buckets. Your Bucket-1 Sort is optimized for the extremely
limited case of nearly consecutive, non-repeating integers.

 

[Lasse Reichstein Nielsen]

What are you putting in your buckets ?

The numbers. Except that because only one value fits in each bucket,
and the value is just the integer, you can optimize it to only
remembering the count.

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.

The "assignment sort" is equvialent to the count sort where the only
values of the count are 0 and 1 (it's just that 1 is represented by
the value - a bit vector would probably be more efficient).

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.

The "digit sorts" (e.g., Radix Sort
<URL:http://en.wikipedia.com/wiki/Radix_sort>) are just generalizations.
Your integer sort is a trivial radix sort with a radix large enough
to hold all values to be sorted, and therefore requireing only one
round.

You can get away with only counting instances, instead of adding
the elements to be sorted to buckets, because you are only sorting
integers themselves. If you needed to sort more general elements
with integers as keys, you would need buckets too.

/L

 

[Lasse Reichstein Nielsen]

A web search for Bucket Sort and for Counting Sort finds that they both have
nested loops and I am not nesting loops.

Counting sort has no nested loops:
<URL:http://en.wikipedia.org/wiki/Counting_sort>
It corresponds to your integer sort.

/L

 

[stephen]

:> A web search for Bucket Sort and for Counting Sort finds that they both have
:> nested loops and I am not nesting loops.

: Counting sort has no nested loops:
: <URL:http://en.wikipedia.org/wiki/Counting_sort>
: It corresponds to your integer sort.

Apparently the name "Bucket Sort" is used inconsistently. Web searches
turn up examples where the name is used to describe the above Counting Sort, and
also to describe variations that use linked lists and secondary sorts.

Stephen

 

[Paul E. Black]

Apparently the name "Bucket Sort" is used inconsistently.

"Bucket sort" is a general type of sort. Counting sort is one kind.
http://www.nist.gov/dads/HTML/countingsort.html

Histogram sort is another kind.

-paul-

 

[HERC777]

http://www.freewebs.com/namesort

does this work? works in IE 5.5 but someone said it does nothing.

Herc

 

[HERC777]

nobody can test this for me? takes 2 clicks. the link and the sort
button.

http://www.freewebs.com/nameso­rt

 

[Jeremy Boden]

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">

....

Why does it only work for a Microsoft browser?
Is it because this invalid HTML?

 

[HERC777]

I dumped the quicksort and am using this but so far only works on IE5.5

http://www.freewebs.com/nameso­­rt

no one will even tell me if it works on their browser, oh well, 1000
gumbies posing as computer gurus. you can all rot in hell, and I"m
Adam so I'll see to it.

Herc

 

[Lasse Reichstein Nielsen]

nobody can test this for me? takes 2 clicks. the link and the sort
button.

I clicked the link (then corrected it) and then clicked the button.
Test was successful.

http://www.freewebs.com/nameso­rt

There's no "-" in "sort"

/L

 

[HERC777]

OK, sounds like you're using IE he must be using the
fireoperanavigatorlinux rubbish.

Herc

 

[Jeremy Boden]

I dumped the quicksort and am using this but so far only works on IE5.5

http://www.freewebs.com/nameso­­rt

no one will even tell me if it works on their browser, oh well, 1000
gumbies posing as computer gurus. you can all rot in hell, and I"m
Adam so I'll see to it.

Herc

OK:-
If I respell that link as http://www.freewebs.com/namesort (no ----)
then I get a web page with a rather poor font and an invitation to paste
some text.
I do this and do a "Domain sorting made Easy".
Unfortunately I do not possess a list of domains and so when I press the
"sort" button, nothing happens.

P.S. I use the Firefox browser.
Better luck next time.
Rot in hell etc...

 

[HERC777]

no ones trembling at my wrath.. hell is in preproduction stage so watch
out for it. some browsers don't like freewebs so the code is fine in
IE, thanks one and all.

a note to all the non web programmers out there.. freewebs is an
excellent point and click free web builder. just click on join...
beginner style... pick a template for your site, add a menu button,
fill in the details.. add a paragraph. Highly recomended for non
programmers to get stuff on the web.

and no ads on a free service, I think there's a small link at the end
of the page, free web servers are great, just leave it and come back in
a few years, remind your password and the site is still going... most
of my hosted sites died at one point or another, free hosting is the
way to go.

tip #2. use form2email.com and use that for your email sig.. and to
get super traffic to your site, have a Partner Sites on your main page
with about 20 links, and a form2email with the link to your site and
they fill in details on their site where they linked to you. one guys
making $80,000 a year and he gets 30 emails a day with the details of
where people linked to him, of course he's got 100,000 links going in
and only 30 going out so he just ignores it. But don't autolink
because google penalises you for being a link farm, but Partner Sites
is allowed!

that's about all I know

Herc

 

[Lasse Reichstein Nielsen]

OK, sounds like you're using IE he must be using the
fireoperanavigatorlinux rubbish.

Who are you talking to (and about what)?

It might be me, in which case you are wrong.
/L