• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag
 

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: QuickSort
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.


  • Prev by Date: Scripting TextEdit
  • Next by Date: Filemaker
  • Previous by thread: Re:Quicksort
  • Next by thread: replacing an image in photoshop
  • Index(es):
    • Date
    • Thread