• 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: Sorting IP addresses - Progress
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.

References: 
 >Re: Sorting IP addresses - Progress (From: Graff <email@hidden>)

  • Prev by Date: Re: checking if variable is defined
  • Next by Date: Re: checking if variable is defined
  • Previous by thread: Re: Sorting IP addresses - Progress
  • Next by thread: Re: Sorting IP addresses - Progress
  • Index(es):
    • Date
    • Thread