Re: Sorting IP addresses - Progress
Re: Sorting IP addresses - Progress
- Subject: Re: Sorting IP addresses - Progress
- From: Paul Berkowitz <email@hidden>
- Date: Sun, 21 Dec 2003 01:05:19 -0800
Just wait for Nigel...
--
Paul Berkowitz
>
From: Graff <email@hidden>
>
Date: Sat, 20 Dec 2003 20:10:33 -0500
>
To: Andreas Amann <email@hidden>
>
Cc: <email@hidden>
>
Subject: Re: Sorting IP addresses - Progress
>
>
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.
>
>
- 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.
>
_______________________________________________
>
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.
_______________________________________________
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.