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: Fri, 26 Jul 2002 15:09:17 -0400
>
Date: Fri, 26 Jul 2002 14:24:46 +0100
>
From: has <email@hidden>
>
Subject: quicksorts [Re: List sorting dilemma]
>
Ethan wrote:
>
> I'm able to access the list of files, but in attempting to use a quicksort
>
> implementation (posted a while back by Arthur Knapp-not that he's
>
The quicksort code you posted was faulty. Due to their recursive nature,
>
all quicksort algorithms will eventually suffer stack overflows if given a
>
large enough list, but thanks to a couple bugs this one was getting stuck
>
in an infinitely recursing loop. Here's the fixed version:
Thanks, Has.
>
to quicksort(Lst, a, z)
>
copy {a, z, Lst's item ((a + z) div 2)} to {l, r, val}
[snip]
Wow, I forgot about that version. This handler was constructed on
the assumption that single-line-multiple-variable setting operations
were faster than normal one-per-line assignments, (I suspect that
this may have been true in a much early version of AppleScript).
Shane Stanely pointed out that this was not true, however, and I have
entirely stopped the practice.
>
While we're on the topic, here is possibly the ugliest AS quicksort routine
>
yet devised. Similarities to Serge's earlier quicksorts should be obvious
>
enough, but I've reworked the loops to improve speed another 5-10%. Ahh,
>
the evil we do in the name of speed...
>
on _quickSort(theList)
[snip]
I hate to do this to you, Has, but my more recent quicksorts are
considerably faster than the one you posted above:
on QuickSort(a, l, r)
(*
* Sorts "in-place":
*
* set a to { 2, 3, 1 }
*
* QuickSort( a, 1, a's length ) -- no return value
*
* get a --> { 1, 2, 3 }
*)
local i, j, v --> SD debugging
(* Much thanks to Serge Belleudy-d'Espinose for that
* extra surge of speed. :)
*)
script o
property p : a
end script
set i to l
set j to r
set v to o's p's item ((l + r) div 2)
repeat while (j > i)
repeat while (o's p's item i < v)
set i to i + 1
end repeat
repeat while (o's p's item j > v)
set j to j - 1
end repeat
if (not i > j) then
(* set { i, j } to { j, i }
*)
set o_s_p_s_item_i to o's p's item i
set o's p's item i to o's p's item j
set o's p's item j to o_s_p_s_item_i
set i to i + 1
set j to j - 1
end if
end repeat
if (l < j) then QuickSort(o's p, l, j)
if (r > i) then QuickSort(o's p, i, r)
end QuickSort
Of course, no matter how fast we make them, all vanilla sorting
routines are still pretty darn slow for large lists. :(
{ 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.