Sunday, June 13, 2021

#1 2021-03-04 12:15:08 pm

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 910

Sorting a List of Lists

I'm revising a script that utilizes a list of lists, and it includes a handler that sorts the list based on the first item in each individual list. Right now I do this with a bubble sort:

Applescript:

set theList to {{"c", "3"}, {"b", "2"}, {"a", "1"}}

repeat with i from (count theList) to 2 by -1
   repeat with j from 1 to i - 1
       if item 1 of item j of theList > item 1 of item (j + 1) of theList then
           set {item j of theList, item (j + 1) of theList} to {item (j + 1) of theList, item j of theList}
       end if
   end repeat
end repeat
theList --> {{"a", "1"}, {"b", "2"}, {"c", "3"}}

For learning purposes, I'd like an ASObjC solution if available and thought the following might work but couldn't figure out what should go in place of "self".

Applescript:

use framework "Foundation"

set theList to {{"c", "3"}, {"b", "2"}, {"a", "1"}}

set theArray to current application's NSArray's arrayWithArray:theList
set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:"self" ascending:true selector:"localizedCaseInsensitiveCompare:"
(theArray's sortedArrayUsingDescriptors:{theDescriptor}) as list

Just as an aside, the number of individual lists in the containing list does not exceed 10 and in this particular case execution speed--within reasonable bounds--is not of great importance. Thanks.


2018 Mac mini - macOS Catalina

Offline

 

#2 2021-03-04 05:49:00 pm

Shane Stanley
Member
From:: Australia
Registered: 2002-12-07
Posts: 6651

Re: Sorting a List of Lists

There is no ASObjC solution to this. It's tempting to use a key of "firstObject", but it doesn't work.

The problem is that when you pass a key to sortWithDescriptor:ascending:selector:, it does the sorting by calling valueForKey: on each item, and then sorting the results.

However, calling valueForKey: on an array is different to calling it on, say, a string — with an array, it gets called on each object in the array (the shortcut often used to avoid repeat loops).

So you end up effectively calling firstObject on each value in each array, and that fails because the values are strings and hence don't recognize firstObject.


Shane Stanley <sstanley@myriad-com.com.au>
www.macosxautomation.com/applescript/apps/
latenightsw.com

Offline

 

#3 2021-03-04 06:15:41 pm

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 910

Re: Sorting a List of Lists

Thanks Shane. It's always good to know when something won't work, as it saves a lot of time researching.


2018 Mac mini - macOS Catalina

Offline

 

#4 2021-03-04 06:55:47 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 5391

Re: Sorting a List of Lists

Hi peavine.

It's possible to use a customisable sort written in the core language, should you happen to come across one: say heresmile  (It's a lot of code, but it's fast and can be hidden away as a library.)

Applescript:

use AppleScript version "2.3.1" -- OS X 10.9 (Mavericks) or later.
use sorter : script "Custom Iterative Ternary Merge Sort" -- <https://macscripter.net/viewtopic.php?pid=194430#p194430>

-- Script object with a handler to compare passed lists by their first items.
script listsByFirstItem
   on isGreater(a, b)
       return (a's first item > b's first item)
   end isGreater
end script

set theList to {{"c", "3"}, {"b", "2"}, {"a", "1"}}
-- Sort items 1 thru -1 of theList in place, using the above script object to do the comparisons.
tell sorter to sort(theList, 1, -1, {comparer:listsByFirstItem})

return theList
--> {{"a", "1"}, {"b", "2"}, {"c", "3"}}


NG

Offline

 

#5 2021-03-05 07:13:46 am

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 910

Re: Sorting a List of Lists

Thanks Nigel. Bubble sort can be abysmally slow, and its great to have a fast alternative.


2018 Mac mini - macOS Catalina

Offline

 

#6 2021-03-05 09:49:35 am

robertfern
Member
Registered: 2011-11-29
Posts: 110

Re: Sorting a List of Lists

I have a "quick-sort" routine that can sort a list of lists.
It can even sort ascending and descending on a per item basis.

Let me know if you want me to post it?

**EDIT** - I found it and decided to post it anyways

Enjoy

BTW - Generating the list takes awhile. Sorting is very fast

Applescript:


use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions

on run
   set bList to generateListMulti(2048, 3) -- generates a list of lists with 3 items
   set sortList to {2, -3} -- list of items to sort by, a negative value means sort descending
   -- "2" tells it to sort first by the second item ascending, and "-3" tells it to sub-sort by item 3 descending
   quickSortMulti(bList, sortList)
   get bList
end run


on generateListMulti(maxCount, numItems)
   script mL
       property nlist : {}
       property glist : {}
   end script
   repeat numItems times
       set end of mL's nlist to 0
   end repeat
   repeat maxCount times
       repeat with i from 1 to numItems
           set item i of mL's nlist to random number from 1 to maxCount
       end repeat
       copy mL's nlist to end of mL's glist
   end repeat
   return mL's glist
end generateListMulti

on quickSortMulti(alist, sortList) -- Non-Recursive FASTEST
   local px, lo, hi, j, L, H, sw, c, comp -- px means 'Pivot Index'
   script mL
       property nlist : alist
       property sList : {}
       property oList : {}
       property stack : {}
   end script
   repeat with j in sortList
       if j > 0 then -- if positive, sort ascending
           set end of mL's sList to (contents of j)
       else -- if negative,sort descending
           set end of mL's sList to -(contents of j)
       end if
       set end of mL's oList to (j > 0)
   end repeat
   set end of mL's stack to {1, count of mL's nlist}
   repeat until (count of mL's stack) = 0 --sc
       set lo to item 1 of item 1 of mL's stack
       set hi to item 2 of item 1 of mL's stack
       -- partitionHoare
       set px to item ((hi + lo) div 2) of mL's nlist
       set L to lo
       set H to hi
       repeat
           set comp to true
           repeat while comp
               repeat with j from 1 to count of mL's sList -- do multiple comparisons
                   set c to item j of mL's sList
                   set comp to false
                   if item c of item L of mL's nlist < item c of px then
                       if item j of mL's oList then set comp to true -- ascending
                       exit repeat
                   else if item c of item L of mL's nlist > item c of px then
                       if not (item j of mL's oList) then set comp to true --descending
                       exit repeat
                   end if
               end repeat
               if comp then set L to L + 1
           end repeat
           
           set comp to true
           repeat while comp
               repeat with j from 1 to count of mL's sList -- do multiple comparisons
                   set c to item j of mL's sList
                   set comp to false
                   if item c of item H of mL's nlist > item c of px then
                       if item j of mL's oList then set comp to true -- ascending
                       exit repeat
                   else if item c of item H of mL's nlist < item c of px then
                       if not (item j of mL's oList) then set comp to true --descending
                       exit repeat
                   end if
               end repeat
               if comp then set H to H - 1
           end repeat
           
           if L ≥ H then
               exit repeat
           end if
           set sw to item L of mL's nlist
           set item L of mL's nlist to item H of mL's nlist
           set item H of mL's nlist to sw
           set L to L + 1
           set H to H - 1
       end repeat
       set px to H -- end of partitionHoare
       set mL's stack to rest of mL's stack
       if px + 1 < hi then
           set beginning of mL's stack to {px + 1, hi}
       end if
       if lo < px then
           set beginning of mL's stack to {lo, px}
       end if
   end repeat
end quickSortMulti

**Edit 2**  Here is a second version that uses ApplescriptObjC to generate the random numbers for list generation.  Much faster.

Applescript:


use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions
use framework "GamePlayKit"

on run
   set bList to generateListMulti(2048, 3) -- generates a list of lists with 3 items
   display alert "List generated." giving up after 1
   set sortList to {2, -3} -- list of items to sort by, a negative value means sort descending
   -- "2" tells it to sort first by the second item ascending, and "-3" tells it to sub-sort by item 3 descending
   quickSortMulti(bList, sortList)
   get bList
end run

on generateListMulti(maxCount, numItems)
   local randomSource, randItem
   script mL
       property nlist : {}
       property glist : {}
   end script
   set randomSource to current application's GKRandomSource's alloc()'s init()
   set randItem to current application's GKGaussianDistribution's alloc()'s initWithRandomSource:randomSource lowestValue:"1" highestValue:(maxCount as text)
   
   repeat numItems times
       set end of mL's nlist to 0
   end repeat
   repeat maxCount times
       repeat with i from 1 to numItems
           set item i of mL's nlist to (randItem's nextInt()) as integer
       end repeat
       copy mL's nlist to end of mL's glist
   end repeat
   return mL's glist
end generateListMulti

on quickSortMulti(alist, sortList) -- Non-Recursive FASTEST
   local px, lo, hi, j, L, H, sw, c, comp -- px means 'Pivot Index'
   script mL
       property nlist : alist
       property sList : {}
       property oList : {}
       property stack : {}
   end script
   repeat with j in sortList
       if j > 0 then -- if positive, sort ascending
           set end of mL's sList to (contents of j)
       else -- if negative,sort descending
           set end of mL's sList to -(contents of j)
       end if
       set end of mL's oList to (j > 0)
   end repeat
   set end of mL's stack to {1, count of mL's nlist}
   repeat until (count of mL's stack) = 0 --sc
       set lo to item 1 of item 1 of mL's stack
       set hi to item 2 of item 1 of mL's stack
       -- partitionHoare
       set px to item ((hi + lo) div 2) of mL's nlist
       set L to lo
       set H to hi
       repeat
           set comp to true
           repeat while comp
               repeat with j from 1 to count of mL's sList -- do multiple comparisons
                   set c to item j of mL's sList
                   set comp to false
                   if item c of item L of mL's nlist < item c of px then
                       if item j of mL's oList then set comp to true -- ascending
                       exit repeat
                   else if item c of item L of mL's nlist > item c of px then
                       if not (item j of mL's oList) then set comp to true --descending
                       exit repeat
                   end if
               end repeat
               if comp then set L to L + 1
           end repeat
           
           set comp to true
           repeat while comp
               repeat with j from 1 to count of mL's sList -- do multiple comparisons
                   set c to item j of mL's sList
                   set comp to false
                   if item c of item H of mL's nlist > item c of px then
                       if item j of mL's oList then set comp to true -- ascending
                       exit repeat
                   else if item c of item H of mL's nlist < item c of px then
                       if not (item j of mL's oList) then set comp to true --descending
                       exit repeat
                   end if
               end repeat
               if comp then set H to H - 1
           end repeat
           
           if L ≥ H then
               exit repeat
           end if
           set sw to item L of mL's nlist
           set item L of mL's nlist to item H of mL's nlist
           set item H of mL's nlist to sw
           set L to L + 1
           set H to H - 1
       end repeat
       set px to H -- end of partitionHoare
       set mL's stack to rest of mL's stack
       if px + 1 < hi then
           set beginning of mL's stack to {px + 1, hi}
       end if
       if lo < px then
           set beginning of mL's stack to {lo, px}
       end if
   end repeat
end quickSortMulti

Last edited by robertfern (2021-03-06 11:45:29 am)

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)