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:

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”.

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.

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.

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

Hi peavine.

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

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"}}

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

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


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.


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