Sorting a list of lists by the length of the first item of the list

OK, this is related to other sorting scripts that have come up. In this case I have a script that is doing a series of finds/changes using a list of lists with two items each.

The nature of the data is that it would work best if the script starts with the longest (count of characters) find, goes on to the shortest.

The source of the list is a MyriadTables user entry.

When the list is displayed in MT it should be sorted alphabetically based on the first item (to make it easier for the user to find entries).

When the list is used to do the find/changes it should be sorted numerically, descending.

Any suggestions? (I have one solution that sorts based on the length, and another based on a substring, but in this case it needs to do the length of a substring).

A while back I needed to sort a list of lists and used a bubble sort. I thought there might be a better ASObjC approach but Shane said that wasnā€™t the case.

I modified my bubble sort to sort on the length of the first item of each list, and it appears to work OK. I ran some timing tests with Script Geek, and the sort-by-length script took less than a millisecond to sort a list of 10 lists but 22 milliseconds to sort a list of 50 lists. So, the script slows very quickly. My knowledge of sort routines is poor, so I suspect thereā€™s a much better way of doing this, and Iā€™ll look forward to other responses.

set theList to {{"dd", "d"}, {"cccc", "c"}, {"a", "a"}, {"bbb", "b"}}

-- sort alphabetically on first item of each list
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", "a"}, {"bbb", "b"}, {"cccc", "c"}, {"dd", "d"}}

-- sort on length of first item of each list
repeat with i from (count theList) to 2 by -1
	repeat with j from 1 to i - 1
		if (count (item 1 of item j)) of theList < (count (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 --> {{"cccc", "c"}, {"bbb", "b"}, {"dd", "d"}, {"a", "a"}}

BTW, the forum wouldnā€™t let me post the link to the thread mentioned above, and I couldnā€™t find any AppleScript tags. Iā€™ll research this.

1 Like

Just precede the script with three ticks (`) on a line, and follow it with the same. Iā€™ll edit your post.

If Ed doesnā€™t mind installing a library script:

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>
use scripting additions

set theList to {{"dd", "d"}, {"cccc", "c"}, {"a", "a"}, {"bbb", "b"}}

script onFirstItemAlphabetically
	on isGreater(a, b)
		return (a's first item > b's first item)
	end isGreater
end script

script onFirstItemByDescendingLength
	on isGreater(a, b)
		return (a's first item's length < b's first item's length)
	end isGreater
end script

-- Sort items 1 thru -1 of theList in place using the relevant custom comparer:
tell sorter to sort(theList, 1, -1, {comparer:onFirstItemAlphabetically})
log theList --> (*a, a, bbb, b, cccc, c, dd, d*)

tell sorter to sort(theList, 1, -1, {comparer:onFirstItemByDescendingLength})
log theList --> (*cccc, c, bbb, b, dd, d, a, a*)

That works, nice and quick.

Would it be possible to see more examples as to how the lib script could be used? (I do a lot of sorting!)

Hi Ed.

Glad itā€™s of use. As youā€™ll have seen, itā€™s an in-place sort, so if you want a sorted copy of the list, you have to make a copy and pass that.

The four parameters are the list itself, two range indices, and a record specifying the sort customisation. As in AppleScript range specifiers, the two indices can be either positive or negative and donā€™t have to be in the right order.

The customisation record can have ā€˜comparerā€™ and/or ā€˜slaveā€™ properties, both of which are optional. The ā€˜comparerā€™ value is a script object (or the script itself) containing an isGreater() handler. This handler receives two items from the sort as parameters and returns true or false according to whether or not the first item should go after the second. The idea of course is that you write this handler yourself to achieve the kind of sort you want.

The ā€˜slaveā€™ value is a list of lists to be rearranged in parallel with the main list, which can sometimes be useful.

If the customisation recordā€™s left empty, a straight sort of the main list is done.

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>
use scripting additions

script onFirstItemByDescendingLengthSubsortingAlphbetically -- For want of a snappier label!
	on isGreater(a, b)
		set a1 to a's first item
		set b1 to b's first item
		if (a1's length < b1's length) then return true
		return ((a1's length = b1's length) and (a1 > b1))
	end isGreater
end script

-- Sort descending by first item's length, but alphabetically within equal lengths.
set theList to {{"zz", "z"}, {"yyyy", "y"}, {"dd", "d"}, {"cccc", "c"}, {"xx", "x"}, {"a", "a"}, {"bbb", "b"}}
tell sorter to sort(theList, 1, -1, {comparer:onFirstItemByDescendingLengthSubsortingAlphbetically})
theList --> {{"cccc", "c"}, {"yyyy", "y"}, {"bbb", "b"}, {"dd", "d"}, {"xx", "x"}, {"zz", "z"}, {"a", "a"}}

-- Same thing, rearranginging another list in parallel.
set theList to {{"zz", "z"}, {"yyyy", "y"}, {"dd", "d"}, {"cccc", "c"}, {"xx", "x"}, {"a", "a"}, {"bbb", "b"}}
set anotherList to {1, 2, 3, 4, 5, 6, 7} -- Same length as theList
-- NB. Despite its singular label, 'slave' must be a /list/ of lists.
tell sorter to sort(theList, 1, -1, {comparer:onFirstItemByDescendingLengthSubsortingAlphbetically, slave:{anotherList}})
anotherList --> {4, 2, 7, 3, 5, 1, 6}

-- Sort items 3 thru 6 of anotherList. Straight sort.
tell sorter to sort(anotherList, 3, 6, {})
anotherList --> {4, 2, 1, 3, 5, 7, 6}

Thanks, where would I find the various options for comparers?

comparer:onFirstItemByDescendingLengthSubsortingAlphbetically

For example, I tried: comparer:onSecondItemByDescendingLengthSubsortingAlphbetically

script onSecondItemByDescendingLengthSubsortingAlphbetically
	on isGreater(a, b)
		set a1 to a's first item
		set b1 to b's first item
		if (b1's length < a1's length) then return true
		return ((a1's length = b1's length) and (b1 > a1))
	end isGreater
end script

set theList to {{"zz", "z"}, {"yyyy", "yyyy"}, {"dd", "dd"}, {"cccc", "ccccc"}, {"xx", "x"}, {"a", "aaa"}, {"bbb", "bbbbbb"}}
tell sorter to sort(theList, 1, -1, {comparer:onSecondItemByDescendingLengthSubsortingAlphbetically})
theList -->{{"a", "aaa"}, {"zz", "z"}, {"xx", "x"}, {"dd", "dd"}, {"bbb", "bbbbbb"}, {"yyyy", "yyyy"}, {"cccc", "ccccc"}}

That result seems to be sorted on length of first item smaller to larger/reverse alpha?

Also Iā€™m not sure about this part of that line:

ā€¦ (a1 > b1)

should that be

(a1ā€™s length > b1ā€™s length)

Or is that how you get the a two part search (length/alpha)

In this case, a1 and b1 have to be set respectively to aā€™s ab bā€™s second items.

Rather than writing a separate script object for this, a smart move would be to have just one script object with a property which the main script can set to the required index before the sort:

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>
use scripting additions

-- Comparer for a sort descending by item i's length, with an ascending alphabetical subsort.
-- Call it whatever you like.
script myCustomComparer
	property i : missing value -- To be set by the main script.
	
	on isGreater(a, b)
		set a1 to a's item i
		set b1 to b's item i
		return ((a1's length < b1's length) or ((a1's length = b1's length) and (a1 > b1)))
	end isGreater
end script

set theList to {{"zz", "z"}, {"yyyy", "y"}, {"dd", "d"}, {"cccc", "c"}, {"xx", "x"}, {"a", "a"}, {"bbb", "b"}}

-- Sort descending by the first items' lengths, but alphabetically within equal lengths.
set myCustomComparer's i to 1
tell sorter to sort(theList, 1, -1, {comparer:myCustomComparer})
theList --> {{"cccc", "c"}, {"yyyy", "y"}, {"bbb", "b"}, {"dd", "d"}, {"xx", "x"}, {"zz", "z"}, {"a", "a"}}

-- Ditto using the second items.
set myCustomComparer's i to 2
tell sorter to sort(theList, 1, -1, {comparer:myCustomComparer})
theList --> {{"a", "a"}, {"bbb", "b"}, {"cccc", "c"}, {"dd", "d"}, {"xx", "x"}, {"yyyy", "y"}, {"zz", "z"}}

The preceding (a1ā€™s length < b1ā€™s length) returns true if the lengths have that relationship, in response to which the sort will move the sublist with the shorter first item to after the sublist with the longer first item. Otherwise if the lengths are the same, the criterion is the itemsā€™ alphabetical order. Otherwise, the first itemā€™s longer than the second, meaning the items are in the required order already, so the handler returns false.

This is very odd. Iā€™m trying to sort a list of lists two different ways using Nigelā€™s library (thanks!).

First it sorts a list alphabetically, and stores it in a variable (alphaList)
Then it sorts a list by length, and stores that in different variable (lengthList)

But when it completes the second sort it changes the value of the first sortā€™s variable.

Iā€™m guessing thereā€™s some kind of reference happening but Iā€™m not sure how to fix.

use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions
use sorter : script "Custom Iterative Ternary Merge Sort"

--SortingLists

set theList to {{"dd", "d"}, {"cccc", "c"}, {"a", "a"}, {"bbb", "b"}}

set alphaList to SortAListByFirstItemAlphabetacally(theList)
log alphaList -->(*a, a, bbb, b, cccc, c, dd, d*) >>>Correct<<<

set lenghtList to SortAListByLengthOfFirstItem(theList)
log alphaList -- >(*cccc, c, bbb, b, dd, d, a, a*) >>>What?<<<
log lenghtList -- >(*cccc, c, bbb, b, dd, d, a, a*)

on SortAListByFirstItemAlphabetacally(anyList)
	script onFirstItemAlphabetically
		on isGreater(a, b)
			return (a's first item > b's first item)
		end isGreater
	end script
	
	tell sorter to sort(anyList, 1, -1, {comparer:onFirstItemAlphabetically})
	return anyList
end SortAListByFirstItemAlphabetacally

on SortAListByLengthOfFirstItem(anyList)
	script onFirstItemAlphabetically
		on isGreater(b, a)
			return (a's first item > b's first item)
		end isGreater
	end script
	
	script onFirstItemByDescendingLength
		on isGreater(a, b)
			return (a's first item's length < b's first item's length)
		end isGreater
	end script
	
	-- Sort items 1 thru -1 of theList in place using the relevant custom comparer:
	tell sorter to sort(anyList, 1, -1, {comparer:onFirstItemAlphabetically})
	tell sorter to sort(anyList, 1, -1, {comparer:onFirstItemByDescendingLength})
	return anyList
end SortAListByLengthOfFirstItem

Donā€™t have time to dig in Nigelā€™s code but here is a workaround:

set theListA to {{"dd", "d"}, {"cccc", "c"}, {"a", "a"}, {"bbb", "b"}}
set theListB to items of theListA

set alphaList to SortAListByFirstItemAlphabetacally(theListA)
set lenghtList to SortAListByLengthOfFirstItem(theListB)
1 Like

Hi Ed. Yes. My sort rearranges the actual list passed to it rather than returning a sorted copy. If you want two copies sorted differently, you either have to make copies using the ā€˜copyā€™ command or get their ā€˜itemsā€™ as per Jonasā€™s suggestion. If you need ā€œdeepā€ copies, use ā€˜copyā€™.

1 Like