• 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: Sort a List with Integers & Letters
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Sort a List with Integers & Letters


  • Subject: Re: Sort a List with Integers & Letters
  • From: "Nigel Garvey" <email@hidden>
  • Date: Tue, 3 Apr 2007 20:33:52 +0100

Jon Pugh wrote on Tue, 3 Apr 2007 09:01:47 -0700:

>At 9:57 PM +0100 4/2/07, kai wrote:
>>Fortunately, from AppleScript 1.10 (Mac OS X version 10.4), a new
>considering/ignoring attribute was added - allowing numeric strings to be
>collated by their numeric value.
>
>Your sort is a bubble sort, which is about the slowest sort known to man.
>Here's a merge sort, which is among the fastest.  I posted this a while ago
>but have added the considering attribute kai mentions to get the behavior
>you want.

Both handlers could be made more flexible by putting the considering
attributes round the calls rather than incorporating them into the sort code.

Jon's merge sort isn't quite twice as fast as kai's sort (which I imagine
was posted more to show the attribute use than to provide a heavy-lifting
sort handler). On my machine, kai's handler sorts 1000 random integers in
2.088 seconds, Jon's in 1.138 seconds. But Jon's sort seems to be a
literal translation from C. If it were optimised for AppleScript, it
could be a lot faster. For instance, the latest version of the merge sort
I posted last month in reply to Jon sorts 1000 integers in 0.108 seconds
- only a whisker behind Arthur Knapp's and my Quicksort/insertion sort
combination of a few years ago. (0.096 seconds.)

  on mergesort(theList, l, r)
    script o
      property lst : theList
      property extract : missing value

      on msort(l, r)
        set m1 to (l + r) div 2
        set m2 to m1 + 1

        if (m1 - l > 1) then
          msort(l, m1)
        else
          set leftVal to item l of my lst
          set rightVal to item m1 of my lst
          if (rightVal < leftVal) then
            set item l of my lst to rightVal
            set item m1 of my lst to leftVal
          end if
        end if

        if (r - m2 > 1) then
          msort(m2, r)
        else if (r > m2) then
          set leftVal to item m2 of my lst
          set rightVal to item r of my lst
          if (rightVal < leftVal) then
            set item m2 of my lst to rightVal
            set item r of my lst to leftVal
          end if
        end if

        set my extract to items l thru r of my lst

        set leftIdx to 1
        set leftLen to m2 - l
        set rightIdx to leftLen + 1
        set extractLen to r - l + 1

        set leftVal to beginning of my extract
        set rightVal to item rightIdx of my extract
        repeat with i from l to r
          if (rightVal < leftVal) then
            set item i of my lst to rightVal
            if (rightIdx < extractLen) then
              set rightIdx to rightIdx + 1
              set rightVal to item rightIdx of my extract
            else
              repeat with i from (i + 1) to r
                set item i of my lst to item leftIdx of my extract
                set leftIdx to leftIdx + 1
              end repeat
              exit repeat
            end if
          else
            set item i of my lst to leftVal
            if (leftIdx < leftLen) then
              set leftIdx to leftIdx + 1
              set leftVal to item leftIdx of my extract
            else
              exit repeat
            end if
          end if
        end repeat
      end msort
    end script

    set listLen to (count TheList)
    if (listLen > 1) then
      if (l < 0) then set l to listLen + l + 1
      if (r < 0) then set r to listLen + r + 1

      if (r = l) then
      else
        if (l > r) then
          set temp to l
          set l to r
          set r to temp
        end if

        o's msort(l, r)
      end if
    end if

    return -- nothing
  end mergesort

  -- Demo:
  set l to {}
  repeat with i from 1 to 1000
    set end of my l to (random number 1000)
  end repeat

  set t to (GetMilliSec)
  mergesort(l, 1, -1) -- Sort items 1 thru -1 of l
  l
  ((GetMilliSec) - t) / 1000


NG

 _______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list      (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users

This email sent to email@hidden

  • Follow-Ups:
    • Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
      • From: Bill Hernandez <email@hidden>
    • Re: Sort a List with Integers & Letters
      • From: Bill Hernandez <email@hidden>
  • Prev by Date: Re: basic scripting with Excel
  • Next by Date: RE: basic scripting with Excel
  • Previous by thread: Re: Sort a List with Integers & Letters
  • Next by thread: Re: Sort a List with Integers & Letters
  • Index(es):
    • Date
    • Thread