Re: quicksorts [Re: List sorting dilemma]
Re: quicksorts [Re: List sorting dilemma]
- Subject: Re: quicksorts [Re: List sorting dilemma]
- From: "Arthur J. Knapp" <email@hidden>
- Date: Mon, 29 Jul 2002 16:45:41 -0400
>
Date: Sat, 27 Jul 2002 12:52:15 +0200
>
From: "Serge Belleudy-d'Espinose" <email@hidden>
>
Subject: Re: quicksorts [Re: List sorting dilemma]
Wow, the listserver was really busy over the weekend... ;-)
>
I've been mostly away but never totally off, and when you say the
>
magic words I can come back (I don't know who coined the 'Serge
>
technique' expression but I feel the greatest gratitude everytime
>
this technique or my name are mentioned...)
My ability to pronounce French is terrible, I wouldn't know how
to "mention" your name without sounding silly. ;-)
>
Ok, I spent a few hours comparing the codes from has and Arthur to
>
mine.
So did I, on Friday. Unfortunatly, I didn't have time to complete
and post my results.
>
... First, let me say that my code will always be slower:
In several of my tests, your sort was way faster than mine. See below.
>
... the
>
quickSort mod is intended to have a rich feature set so there will
>
always be a somewhat noticeable overhead when values are checked and
>
passed all around. This slowness is a design decision :) However this
>
is all a matter of ticks, not seconds.
Right. Your quickSort 3.0 is a brilliant full featured script, allowing
for "weighted" sorting, etc. I highly recommend it:
<
http://www.applemods.com/getMod.php?script_ID=33>
>
So I trimed my quickSort to the very core and the results are
>
amazing. It seems Arthur is the winner but the situation is complex.
Yes, it is very complex. If you look though Serge's comments, you will
see a reference to the "Dutch flag" variation. In a traditional quicksort,
a list, (or part of a list), is divided into two halfs surrounding a
"pivot" item. Then, those items that are less than, (should be sorted
before), the pivot are moved to the left, and those greater are moved to
the right. In a Dutch flag quicksort, the sublist is divided into three
parts, with the center sublist capturing all items that are equal to the
pivot. The advantage is that such an algorithm should be faster at sorting
lists with lots of duplicates.
And then there is the issue of ordered lists, (or nearly ordered lists),
a situation that comes up a lot in programming, where the list happens to
already be close to sorted. Some quicksorts do not perform well in this
case, as compared to an insertion sort or other basic sorts.
>
The respective performances depend on the test list. Here are my
>
results; each sample expresses the average time for each (Jon's
>
ticks) plus the % gain of speed of has vs mine and Arthur vs mine. I
>
didn't test Emmanuel's revised code since I suspect the results will
>
be very close. Average of ten tests.
I prefer not to use Jon's ticks, as I often don't trust AppleScript
to be accurate below a single second. I had to run my test at two
thousand items or more to obtain significant results with "seconds".
I also obtained the average of 10 runs.
Has's sort, (the one at the bottom of the message):
<
http://lists.apple.com/mhonarc/applescript-users/msg25963.html>
My own:
<
http://lists.apple.com/mhonarc/applescript-users/msg25965.html>
Emmanual's, (as posted by Paul):
<
http://lists.apple.com/mhonarc/applescript-users/msg25966.html>
Serge's:
<
http://www.applemods.com/getMod.php?script_ID=33>
d = duplicates
|-----------------------------|-------------------|
| 2000 | 10000 |
|---------|---------|---------|---------|---------|
| ordered | random | reverese| ordered | random |
|---------|---------|---------|---------|---------|
| | d | | d | | d | | d | | d |
|----|----|----|----|----|----|----|----|----|----|
Ajk | 1.7| 2.4| 3 | 3.3| 1.9| 2.4|11 |14 |18.6|19.5|
|----|----|----|----|----|----|----|----|----|----|
Has | 2.4| 2.7| 3.4| 3.1| 2.6| 2.7|17.5|18.2|22.6|21.7|
|----|----|----|----|----|----|----|----|----|----|
Emm | 3 | 2.9| 3.8| 4.1| 2.6| 2.9|19.1|19.2|28.2|26.5|
|----|----|----|----|----|----|----|----|----|----|
Ser | 3 | 2.2| 3.9| 3.2| 2.7| 2.2|20.3|16.2|28.6|22.3|
|----|----|----|----|----|----|----|----|----|----|
>
The fun stuff is that even with the averaging, results can vary from
>
one serie of tests to another.
I also found this. In particular, increasing or decreasing the number
of duplicate items had a profound effect.
2000 random duplicates
|------|------|------|------|
| 2 | 10 | 100 | 500 | --> number of possible
|------|------|------|------| values for each item,
Ajk | 4.5 | 4.8 | 4 | 4 | ie: a smaller number
|------|------|------|------| indicates a larger
Has | * | 22.8 | 5 | 3 | number of duplicates
|------|------|------|------|
Emm | * | * | 5 | 4 |
|------|------|------|------|
Ser | 0.2 | 0.9 | 2 | 3 |
|------|------|------|------|
* = "Stack overflow."
>
.. The random generator must be tired
>
sometimes...
Aren't we all... ;-)
{ Arthur J. Knapp, of <
http://www.STELLARViSIONs.com>
a r t h u r @ s t e l l a r v i s i o n s . c o m
}
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.