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

It occurred to me that this task might be accomplished by using an array of dictionaries, and I’ve included the script below. The timing results with 10, 100, and 500 subarrays were 2, 15, and 60 milliseconds.

use framework "Foundation"

set theArray to current application's NSArray's arrayWithArray:{{"e", "1"}, {"a", "5"}, {"d", "2"}, {"b", "3"}, {"c", "4"}}
set sortedArray to getSortedArray(theArray)

on getSortedArray(theArray)
	set dictArray to current application's NSMutableArray's new() -- an array of dictionaries for sorting
	repeat with anArray in theArray
		set aDict to (current application's NSDictionary's dictionaryWithObjects:anArray forKeys:{"keyOne", "keyTwo"})
		(dictArray's addObject:aDict)
	end repeat
	set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:"keyTwo" ascending:true selector:"compare:" -- edit sort key and selector as desired
	dictArray's sortUsingDescriptors:{theDescriptor}
	set sortedArray to current application's NSMutableArray's new() -- the sorted array of arrays
	repeat with aDict in dictArray
		(sortedArray's addObject:{aDict's valueForKey:"keyOne", aDict's valueForKey:"keyTwo"})
	end repeat
	return sortedArray
end getSortedArray

I was curious how my script would work with a larger number of objects in each subarray. The timing result with 100 subarrays with four objects in each subarray was 21 milliseconds.

use framework "Foundation"

set theArray to current application's NSArray's arrayWithArray:{{"a", 1, "y", 11}, {"c", 3, "x", 13}, {"b", 2, "z", 12}}
set sortedArray to getSortedArray(theArray, 1) -- 1 is the subarray index number to sort on

on getSortedArray(sourceArray, keyNumber)
	set dictArray to current application's NSMutableArray's new()
	repeat with s in sourceArray
		set aDict to (current application's NSDictionary's dictionaryWithObjects:s forKeys:{"k1", "k2", "k3", "k4"})
		(dictArray's addObject:aDict)
	end repeat
	set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:("k" & keyNumber) ascending:true selector:"compare:"
	dictArray's sortUsingDescriptors:{theDescriptor}
	set sortedArray to current application's NSMutableArray's new()
	repeat with d in dictArray
		(sortedArray's addObject:{d's valueForKey:"k1", d's valueForKey:"k2", d's valueForKey:"k3", d's valueForKey:"k4"})
	end repeat
	return sortedArray
end getSortedArray

Have you timed it with the native AppleScript version I put above.
When I test it, the native version is much faster than the AppleScriptObjC version using a list of 2048.
With 100 subarrays with four objects in each subarray, Native was less than 8 milliseconds

Robert. I tested our scripts as you suggest, but I used a timing script to eliminate the time it took to create the test list. The results were 90 milliseconds for your script and 200 milliseconds for my script.

I also created a list with 140 sublists in the format shown below and tested our scripts with Script Geek. The results were 11 milliseconds for your script and 24 milliseconds for my script:

set bList to {{"Peavine", "Peabody", 33}, {"John", "Doe", 22}, {"Jane", "Smith", 63}, {"Joe", "Anderson", 11}, {"Margaret", "Smith", 37}, {"Eva", "Cassidy", 38}, {"John", "Wright", 44}, {"Jolly", "John", 88}, {"Kathryn", "Toomy", 39}} -- shortened for brevity

BTW, I think our scripts are written to address different use scenarios. My script is relatively compact and reasonably quick when dealing with moderate amounts of data. In contrast, your script is written for speed but certainly is not compact. Both scripts have their place.

Hi.

Here’s a shorter and more flexible (with regard to possible subarray length) variation on peavine’s idea. I haven’t compared the two scripts for speed.

use framework "Foundation"

set theArray to current application's NSArray's arrayWithArray:{{"a", 1, "y", 11}, {"c", 3, "x", 13}, {"b", 2, "z", 12}}
set sortedArray to getSortedArray(theArray, 1) -- 1 is the subarray index number to sort on

on getSortedArray(sourceArray, keyNumber)
	set dictArray to current application's NSMutableArray's new()
	repeat with s in sourceArray
		set aDict to (current application's NSDictionary's dictionaryWithObjects:{s's objectAtIndex:(keyNumber - 1), s} forKeys:{"sortVal", "arrayVal"})
		(dictArray's addObject:aDict)
	end repeat
	set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:"sortVal" ascending:true selector:"compare:"
	dictArray's sortUsingDescriptors:{theDescriptor}
	return dictArray's valueForKey:"arrayVal"
end getSortedArray
1 Like

Thanks Nigel–your suggestion works great and can’t be beat for speed and compactness. The timing results with a list of lists that contained 100 sublists with 4 items in each sublist were:

Robert - 8 milliseconds
Nigel - 10
Peavine - 20

I also tested your script with Robert’s list suggestion with 2048 sublists, and the timing results were:

Robert - 90 milliseconds
Nigel - 107
Peavine - 200

Odd, when I run it thru script geek, using 100 items, mine run at 10 milliseconds and peavine’s at 36 milliseconds. (did 1000 iterations)
When i use 2048 items, mine gets 264 milliseconds, peavine’s gets 2,759 milliseconds (did 100 iterations because it was slower)

On a Mac Mini 2018 i7-3.2Ghz Monterey

I used a timing script when testing with 2048 items, because I didn’t think the time it takes to create the list should be included in the result. My testing is on a 2023 Mac mini running Sonoma.

use framework "Foundation"
use scripting additions

-- untimed code
set bList to generateListMulti(2048, 3) -- generates a list of lists with 3 items
set bList to current application's NSArray's arrayWithArray:bList

-- start time
set startTime to current application's CACurrentMediaTime()

-- timed code
set sortedArray to getSortedArray(bList, 2)

-- elapsed time
set elapsedTime to (current application's CACurrentMediaTime()) - startTime
set numberFormatter to current application's NSNumberFormatter's new()
(numberFormatter's setFormat:"0")
set elapsedTime to ((numberFormatter's stringFromNumber:(elapsedTime * 1000)) as text) & " milliseconds"

-- result
elapsedTime --> 205 milliseconds
# sortedArray as list --> as expected
# count sortedArray --> 2048

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 getSortedArray(sourceArray, keyNumber)
	set dictArray to current application's NSMutableArray's new()
	repeat with s in sourceArray
		set aDict to (current application's NSDictionary's dictionaryWithObjects:s forKeys:{"k1", "k2", "k3"})
		(dictArray's addObject:aDict)
	end repeat
	set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:("k" & keyNumber) ascending:true selector:"compare:"
	dictArray's sortUsingDescriptors:{theDescriptor}
	set sortedArray to current application's NSMutableArray's new()
	repeat with d in dictArray
		(sortedArray's addObject:{d's valueForKey:"k1", d's valueForKey:"k2", d's valueForKey:"k3"})
	end repeat
	return sortedArray
end getSortedArray

The test with 100 items:

Mine doesn’t have the time of list creation in the script. It reads a pre-built list from a preference file, so each iteration is using the same unsorted list.

Hi Fredrik71.

You’re of course right that Objective-C methods use 0-based indexing and I agree that if a published or public-facing handler takes both an NSArray and an index, that index should ideally be 0-based to avoid confusion. It’s perhaps not so important in a script cobbled together for one’s own use, or a private handler in a library, but there should be adequate comments to explain what’s what in order to aid any future editing!

In a public-facing handler, I myself would normally treat AppleScript as the language of the main script and pass a list and a 1-based index to the handler, performing any conversion’s to/from ASObjC within the handler itself. But again, it would depend on the circumstances.

To add to the confusion, it’s possible to use AppleScript index specifiers with NSArrays — and in fact they perform slightly faster than objectAtIndex:. :smile: This line in my post #12 script:

set aDict to (current application's NSDictionary's dictionaryWithObjects:{s's objectAtIndex:(keyNumber - 1), s} forKeys:{"sortVal", "arrayVal"})
		(dictArray's addObject:aDict)

… would thus be:

set aDict to (current application's NSDictionary's dictionaryWithObjects:{s's item keyNumber, s} forKeys:{"sortVal", "arrayVal"})
		(dictArray's addObject:aDict)

I’ve included below a version of Nigel’s handler that inputs and outputs a list of lists. I thought this might be helpful to those looking for a ready-to-use solution. The timing result with 100 sublists with 4 items in each sublist was 10 milliseconds.

It should be noted that the script uses a compare selector, which is necessary for sorting on numbers but is case sensitive. If numbers are not being sorted on, and a case-insensitive sort is desired, localizedStandardCompare is a good all-around choice.

use framework "Foundation"
use scripting additions

set theList to {{"b", 1}, {"d", 3}, {"c", 2}, {"a", 4}}
set sortedList to getSortedList(theList, 1) -- 1 is the sublist item to sort on

on getSortedList(theList, itemNumber)
	set theArray to current application's NSArray's arrayWithArray:theList
	set dictionaryArray to current application's NSMutableArray's new()
	repeat with aSubarray in theArray
		set aDictionary to (current application's NSDictionary's dictionaryWithObjects:{aSubarray's objectAtIndex:(itemNumber - 1), aSubarray} forKeys:{"sortValue", "arrayValue"})
		(dictionaryArray's addObject:aDictionary)
	end repeat
	set theDescriptor to current application's NSSortDescriptor's sortDescriptorWithKey:"sortValue" ascending:true selector:"compare:" -- consider localizedStandardCompare instead of compare
	dictionaryArray's sortUsingDescriptors:{theDescriptor}
	return (dictionaryArray's valueForKey:"arrayValue") as list
end getSortedList

The following incorporates both sort and subsort parameters. The timing result with 100 sublists with 4 items in each sublist was 14 milliseconds.

use framework "Foundation"
use scripting additions

set theList to {{"a", 2}, {"b", 1}, {"a", 1}, {"b", 2}}
set sortedList to getSortedList(theList, 1, 2) -- 1 and 2 are the sublist items to sort and subsort on

on getSortedList(theList, itemOne, itemTwo)
	set theArray to current application's NSArray's arrayWithArray:theList
	set dictionaryArray to current application's NSMutableArray's new()
	repeat with aSubarray in theArray
		set aDictionary to (current application's NSDictionary's dictionaryWithObjects:{aSubarray's objectAtIndex:(itemOne - 1), aSubarray's objectAtIndex:(itemTwo - 1), aSubarray} forKeys:{"sortOne", "sortTwo", "arrayValue"})
		(dictionaryArray's addObject:aDictionary)
	end repeat
	set descriptorOne to current application's NSSortDescriptor's sortDescriptorWithKey:"sortOne" ascending:true selector:"compare:"
	set descriptorTwo to current application's NSSortDescriptor's sortDescriptorWithKey:"sortTwo" ascending:true selector:"compare:"
	dictionaryArray's sortUsingDescriptors:{descriptorOne, descriptorTwo}
	return (dictionaryArray's valueForKey:"arrayValue") as list
end getSortedList
1 Like

Wow, way faster. Nice job

1 Like