Re: Sorting IP addresses - Progress
Re: Sorting IP addresses - Progress
- Subject: Re: Sorting IP addresses - Progress
- From: Nigel Garvey <email@hidden>
- Date: Sun, 21 Dec 2003 16:48:15 +0000
Graff wrote on Sat, 20 Dec 2003 20:10:33 -0500:
>
It turns out your quick sort implementation is better than the one I
>
adapted from that web site. Your quick sort sorted 10,000 items in 72
>
seconds as opposed to 349 seconds for the quick sort I adapted. Since
>
my merge sort took 131 seconds for the same data set this means that
>
your quick sort is indeed the quickest sorting implementation out of
>
all of them for large data sets.
Running under OS 10.2.8 on my PowerBook, Andreas's Quicksort averages
438.2 seconds for five 10,000-integer lists. (Obviously, my machine's not
as fast as yours.) On the same machine, Arthur Knapp's Quicksort
implementation - which has appeared in this forum several times in the
past - averages just 8.3 seconds with copies of the same lists. (Arthur's
implementation is slightly different in that it sorts "in place". Rather
than return a separate, sorted version of the list, it rearranges the
items in the original list.)
It so happens that over the past two or three weeks, Arthur and I have
been honing another idea of his that's even faster. Quicksort tends to
become less efficient as a list becomes more ordered, since less of the
work done actually results in any change. Insertion sorts, on the other
hand, are ideal for nearly-sorted lists. The less there is to do, the
quicker they don't do it. :-) Arthur's idea is to use a quicksort to
"nearly sort" the list, and then to finish the job with an insertion
sort. The "nearly" sort is achieved by the quicksort not recursing when
it would only have to deal with ten or less items.
On my machine, the implementation as it currently stands handles the
above test lists in an average of 5.6 seconds. We're still looking into
further speed tweaks and have yet to finalise the comments, but this is
essentially it:
-- Parameters:
-- a: the list
-- l: the index of the left-most item to include in the sort
-- r: the index of the right-most item to include in the sort
on qsort(a, l, r)
script o
-- The "don't recurse" limit for the quicksort
--
property kiQsortCutoff : 10
-- The list as a script property, for fast access to its items
--
property p : a
-- The Quicksort handler
--
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
-- (Testing '(i > j)' and branching if it's not true
-- is faster than testing 'not (i > j)' or '(i <= j)')
--
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
-- Subsort the lower values only if there are more than 10
--
if (j - l < kiQsortCutoff) then
else
qsrt(l, j)
end if
-- Subsort the higher values only if there are more than 10
--
if (r - i < kiQsortCutoff) then
else
qsrt(i, r)
end if
end qsrt
-- The insertion sort handler
--
on isrt(l, r)
-- qsrt() has placed at least one instance of the smallest item
-- in the list into the range l thru (l + kiQsortCutoff - 1).
-- We can grab it to use as a sentinel.
--
set x to l
set z to l + kiQsortCutoff - 1
if (z > r) then set z to r
-- Find the smallest value
--
set v to my p's item x
repeat with y from (x + 1) to z
tell my p's item y
if (it < v) then
set x to y
set v to it
end if
end tell
end repeat
-- Swap smallest item for first item
--
tell my p's item l
set my p's item l to v
set my p's item x to it
end tell
-- We already know that item (l + 1) >= item l, so start
-- by comparing item (l + 2) with item (l + 1).
--
set u to my p's item (l + 1) -- the "previous" list item value
repeat with i from (l + 2) to r
set v to my p's item i -- the "current" list item value
if (v < u) then
-- If the current item is less than the previous one,
-- Shift the previous item to the right
--
set my p's item i to u
-- Go backwards through the list, shifting items to the right
-- until an item is found that is <= the "current" value.
-- Insert the current value to its right.
--
repeat with j from (i - 2) to l by -1
tell my p's item j
if (v < it) then
set my p's item (j + 1) to it
else
set my p's item (j + 1) to v
exit repeat
end if
end tell
end repeat
-- The "previous" value has moved to the "current" position
-- so u will still be the "previous" value in the next
iteration
else
-- Otherwise, make the current value the next "previous"
value
--
set u to v
end if
end repeat
end isrt
end script
o's qsrt(l, r) --> sort sub-groups of 11 or more items
o's isrt(l, r) --> finish with insertion-sort
end qsort
set myList to [a randomly ordered list]
qsort(myList, 1, count myList)
myList -- now sorted
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.