Re: QuickSort
Re: QuickSort
- Subject: Re: QuickSort
- From: Nigel Garvey <email@hidden>
- Date: Thu, 15 Jul 2004 14:57:06 +0100
Graff wrote on Wed, 14 Jul 2004 18:56:31 -0400:
>
Quicksort is potentially the fastest sort out there for large,
>
completely unordered data sets. If the data is semi-ordered then a
>
quicksort can be sub-optimal.
Arthur Knapp's qsort is pretty mean. It's a dual-process affair that
starts off with his already very fast QuickSort then switches to an
insertion sort when the list is nearly ordered. (That is, the Quicksort
doesn't recurse for subgroups of less than 10 items.) There are a couple
of variations on it for various reasons, but the basic one is:
-- Knapp/Garvey qsort
-- Sorts (a region of) a list.
-- Params: the list, the left and right indices of the region to be
sorted.
-- qsort(myList, 1, count myList) -- sort a whole list
-- --> Nothing returned, but myList is now sorted.
on qsort(theList, l, r)
script o
property cutoff : 10
property p : theList
on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)
repeat while (j > i)
set u to my p's item i
repeat while (u < v)
set i to i + 1
set u to my p's item i
end repeat
set w to my p's item j
repeat while (w > v)
set j to j - 1
set w to my p's item j
end repeat
if (i > j) then
else
set my p's item i to w
set my p's item j to u
set i to i + 1
set j to j - 1
end if
end repeat
if (j - l < cutoff) then
else
qsrt(l, j)
end if
if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt
on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r
set v to my p's item x
repeat with y from (x + 1) to z
if (my p's item y < v) then
set x to y
set v to my p's item y
end if
end repeat
tell my p's item l
set my p's item l to v
set my p's item x to it
end tell
set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (v < u) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
if (v < my p's item j) then
set my p's item (j + 1) to my p's item j
else
set my p's item (j + 1) to v
exit repeat
end if
end repeat
else
set u to v
end if
end repeat
end isrt
end script
if l > r then
set temp to l
set l to r
set r to temp
end if
o's qsrt(l, r)
o's isrt(l, r)
end qsort
NG
_______________________________________________
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.