Re: Sorting IP addresses - Progress
Re: Sorting IP addresses - Progress
- Subject: Re: Sorting IP addresses - Progress
- From: Graff <email@hidden>
- Date: Sat, 20 Dec 2003 19:08:31 -0500
Believe it or not I already tried it. I sorted a 10,000 line list of
random IP numbers. My implementation of a merge sort took 131 seconds
on a dual 2 gHz G5, an AppleScript re-implementation of the quick sort
given on the web site I mentioned took 324 seconds. Now a quick sort
should be about the same speed as a merge sort (approximately O(n log
n)) so there is probably some other bottleneck in the quick sort
implementation I used. Maybe it nests the recursion a lot deeper than
the merge sort and that causes a slowdown.
I'll try your quick sort algorithm on my data set and see how long it
takes, it might be a better implementation of it.
- Ken
On Dec 20, 2003, at 6:09 PM, Andreas Amann wrote:
The sort I provided is basically a merge sort. A merge sort operates
as O(n log n), where a shell sort operates as O(n^2). This means that
given 2 lists, one with 10 items and one with 1000 items the merge
sort would take 100 log 100 times, or 200 times longer to sort the
1000 item list than the 10 item list. The shell sort would take
100^2, or 10,000 times longer to sort the 1000 item list than the 10
item list. So for long lists the merge sort is vastly faster than the
shell sort.
You can see the different types of sorts here:
<http://linux.wku.edu/~lamonml/algor/sort/sort.html>
- Ken
Maybe we should have a race about what sorting is the fastest - I am
using an AppleScript implementation of "quickSort" it scales with O(n
log n) as well so I would be curious how it compares to the merge
sort... Quoting from the above webpage: "With that said, in most cases
the quick sort is the best choice if speed is important"
Andreas Amann
on quickSort(theList)
(*
QuickSort was invented by C.A.R. Hoare in 1962 [Hoare, C.A.R.
Quicksort. Comp.J.5, No.1 (1962) 10-15, Hoare, C.A.R. Proof of a
Recursive Program: Quicksort. Comp.J.14, No.4 (1971) 391-395. While
asciiSort scales with n^2, where n=nuber of items to sort, quickSort
scales with nlog(n).
Original AppleScript implementation courtesy of Markus Kasper
*)
set r to the count of theList
if r > 0 then -- Andreas Amann, added for safety reasons in case list
is empty...
set i to 1
set j to r
set theComparer to the middle item of theList
repeat
-- in the front part of the list, find the first item larger than
theComparer
repeat
if item i of theList < theComparer then
set i to i + 1
else
exit repeat
end if
end repeat
-- in the back part of the list, find the first item smaller than
theComparer
repeat
if theComparer < item j of theList then
set j to j - 1
else
exit repeat
end if
end repeat
-- swap the two items
if i is less than or equal to j then
set theBuffer to item i of theList
set item i of theList to item j of theList
set item j of theList to theBuffer
set i to i + 1
set j to j - 1
end if
-- repeat until the front and back part of the list meet
if i > j then exit repeat
end repeat
-- sort the front part of the list (only if it contains more than 1
element)
if 1 < j then
set theFrontPart to quickSort((items 1 thru j of theList) as list)
else if j = 1 then
set theFrontPart to (the first item of theList) as list
else
set theFrontPart to {}
end if
-- store the middle part of the list (which contains only elements
identical to theComparer)
if j + 1 < i then
set theMiddlePart to items (j + 1) thru (i - 1) of theList
else
set theMiddlePart to {}
end if
-- sort the back part of the list (only if it contains more than 1
element)
if i < r then
set theBackPart to quickSort((items i thru r of theList) as list)
else if i = r then
set theBackPart to (the last item of theList) as list
else
set theBackPart to {}
end if
-- put it all together
set theList to (theFrontPart & theMiddlePart & theBackPart) as list
end if
return theList
end quickSort
_______________________________________________
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.