I need to sort list of list.
Example {{“New York”, “USA”}, {“Paris”, “France”}} specifyng the “column” to sort.
Actually I use QuickSort but the routine works only for single list.
Anyone has the solution? The routine must be the fastest as possible (like QSort…).
Thanks in advance.
Steve H.
Model: MacBook Pro
Browser: Safari 531.9
Operating System: Mac OS X (10.5)
The trick is to split the list of lists into two separate lists in the same order, then keep them registered as you sort on one of them. Unless you’re prepared to do some heavy lifting with QSort, this might suffice. It simple sorts the first argument while keeping the second argument in register (making the same moves). Easy to expand to more lists. Original script by Kai Edwards. If your lists are very long, this is speeded substantially by making the lists part of a script object.
to sort2Lists(|sortlist|, SecondList)
tell (count |sortlist|) to repeat with i from (it - 1) to 1 by -1
set s to |sortlist|'s item i
set r to SecondList's item i
repeat with i from (i + 1) to it
tell |sortlist|'s item i to if s > it then
set |sortlist|'s item (i - 1) to it
set SecondList's item (i - 1) to SecondList's item i
else
set |sortlist|'s item (i - 1) to s
set SecondList's item (i - 1) to r
exit repeat
end if
end repeat
if it is i and s > |sortlist|'s end then
set |sortlist|'s item it to s
set SecondList's item it to r
end if
end repeat
return {|sortlist|, SecondList}
end sort2Lists
Regulus6633 has also put together a neat list of lists sorter that you might modify for your use that uses QSort:
set initialListOfLists to {{1, 2, 3, 7, 10}, {1, 3, 4, 10, 11}, {9, 3, 5, 11}}
-- first make the list of lists into one list so we can sort it
set combinedList to {}
repeat with aList in initialListOfLists
set combinedList to combinedList & aList
end repeat
-- sort the combined list
Qsort(combinedList, 1, -1)
-- iterate the sorted list and compile the number of times each value occurs
set countOfList to count of combinedList
set i to 1
set finalStats to {}
repeat until i is greater than countOfList
set thisValue to item i of combinedList
if (i + 1) is greater than countOfList then -- this happens if the last value is unique
set end of finalStats to {thisValue, 1}
exit repeat
else
repeat with j from (i + 1) to countOfList
if item j of combinedList is not equal to thisValue then exit repeat
if j is countOfList then -- this happens if the last value is not unique
set j to j + 1
exit repeat
end if
end repeat
end if
set end of finalStats to {thisValue, (j - i)}
set i to j
end repeat
-- sort the final stats and reverse it so the highest number of occurrences is shown first in the finalStats
set sortedFinalStats to sortListofLists(finalStats, 2)
set theReverse to reverse of sortedFinalStats
(*========== SUBROUTINES ============*)
on sortListofLists(array, sortItemNum) --> I modified a bublesort routine to make it work with a list of lists
repeat with i from length of array to 2 by -1 -- go backwards
repeat with j from 1 to i - 1 -- go forwards
if (item sortItemNum of (item j of array)) > (item sortItemNum of (item (j + 1) of array)) then
tell array to set {item j, item (j + 1)} to {item (j + 1), item j}
end if
end repeat
end repeat
return array
end sortListofLists
on Qsort(theList, l, r)
-- Qsort sorts a list
-- the authors of Qsort are Arthur Knapp and Nigel Garvey
-- the script can be found in item 2 of http://bbs.applescript.net/viewtopic.php?id=17340
script o
property cutoff : 10
property p : theList
on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)
repeat while (j > i)
set u to my p's item i
repeat while (u < v)
set i to i + 1
set u to my p's item i
end repeat
set w to my p's item j
repeat while (w > v)
set j to j - 1
set w to my p's item j
end repeat
if (i > j) then
else
set my p's item i to w
set my p's item j to u
set i to i + 1
set j to j - 1
end if
end repeat
if (j - l < cutoff) then
else
qsrt(l, j)
end if
if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt
on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r
set v to my p's item x
repeat with y from (x + 1) to z
if (my p's item y < v) then
set x to y
set v to my p's item y
end if
end repeat
tell my p's item l
set my p's item l to v
set my p's item x to it
end tell
set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (v < u) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
if (v < my p's item j) then
set my p's item (j + 1) to my p's item j
else
set my p's item (j + 1) to v
exit repeat
end if
end repeat
else
set u to v
end if
end repeat
end isrt
end script
set listLen to (count theList)
if (listLen > 1) then -- otherwise the handler will error
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
if (l > r) then
set temp to l
set l to r
set r to temp
end if
if (r - l < o's cutoff) then
-- Skip the Quicksort if cutoff or less items
else
o's qsrt(l, r)
end if
o's isrt(l, r)
end if
end if
return -- the original name of your list is the returned value
end Qsort
Another approach is to make a list of row numbers of the original list {1, 2, 3, …}
Then sort that list of row numbers using a custom LT (less than) function that determines if one row is “less than” another.
e.g. {“New York”, “USA”} is “less than” {“Paris”, “France”} if we are using column 1, but {“Paris”, “France”} is “less than” {“New York”, “USA”} if we are using column 2
Then use the sorted list of row numbers to build a sortedList from the original.
This example uses a bubble sort (to avoid obscuring the “sort by reference list” concept), but a quick sort could be used to sort orderOfList
global unSortedList, orderOfList
set unSortedList to {{"New York", "USA"}, {"Paris", "France"}, {"Minas Tirith", "Gondor"}, {"Black Rock", "Nevada"}}
set comparisonColumn to 2
-- make list of indexes
set orderOfList to {}
repeat with i from 1 to (count of unSortedList)
copy i to end of orderOfList
end repeat
--Bubble Sort the list of indexes
repeat with i from 1 to ((count of orderOfList) - 1)
repeat with j from i + 1 to count of orderOfList
if LT(j, i, comparisonColumn) then
set {item i of orderOfList, item j of orderOfList} to {item j of orderOfList, item i of orderOfList}
end if
end repeat
end repeat
--make sortedlist from original according to custom sorted orderOfList
set sortedList to {}
repeat with i from 1 to count of orderOfList
copy item (item i of orderOfList) of unSortedList to end of sortedList
end repeat
return sortedList
on LT(a, b, columnToCompare)
set aItem to item columnToCompare of (item (item a of orderOfList) of unSortedList)
set bItem to item columnToCompare of (item (item b of orderOfList) of unSortedList)
return aItem < bItem
end LT
My inexerience with AppleScript tripped me up. The indexing list is not needed. (Its a good technique for 2 dimesional arrays, but Applescript’s List class doesn’t support two index arrays.)
A custom LT function will suffice.
The idea of a custom LT function is that at the heart of many sort routines (including Bubble and Quick) is the statment “if A < B then swap A and B”
Instead of using the comparison < , one can write a boolean function LT and replace that line with “if LT(A,B) then swap A and B”
This example uses a bubble sort, but you can substitute LT(A,B) for A < B in your existing QuickSort.
set myList to {{"New York", "USA"}, {"Paris", "France"}, {"Minas Tirith", "Gondor"}, {"Black Rock", "Nevada"}}
set comparisonColumn to 1
-- Bubble Sort
repeat with i from 1 to ((count of myList) - 1)
repeat with j from i + 1 to count of myList
if LT(item j of myList, item i of myList, comparisonColumn) then
set {item i of myList, item j of myList} to {item j of myList, item i of myList}
end if
end repeat
end repeat
return myList
-- custom less than function
on LT(aRay, bRay, columnToCompare)
set aTerm to item columnToCompare of aRay
set bterm to item columnToCompare of bRay
return aTerm < bterm
end LT
Presumably, then, your list of lists is quite long. The version of Qsort in Adam’s quote of regulus6633’s script has a sibling called CustomQsort, whose value comparisons are done for it by handlers in a passed script object. For your purpose, where the values are lists, it could be passed handlers that compare particular items of those lists. The sortListsByNthItem handler in the script below sets up the script object and calls CustomQsort. You call it with the list of lists and the relevant index number.
-- CustomQsort by Arthur Knapp and Nigel Garvey.
-- Sort items l thru r of theList using the customising handlers in the script object compObj.
on CustomQsort(theList, l, r, compObj)
script o
property cutoff : 10
property p : theList
on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)
repeat while (j > i)
set u to my p's item i
repeat while (compObj's isLess(u, v))
set i to i + 1
set u to my p's item i
end repeat
set w to my p's item j
repeat while (compObj's isGreater(w, v))
set j to j - 1
set w to my p's item j
end repeat
if (i > j) then
else
set my p's item i to w
set my p's item j to u
-- Perform any additional actions that may be required after this swap.
compObj's swap(i, j)
set i to i + 1
set j to j - 1
end if
end repeat
if (j - l < cutoff) then
else
qsrt(l, j)
end if
if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt
on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r
set v to my p's item x
set u to v
repeat with y from (x + 1) to z
tell my p's item y
if (compObj's isLess(it, v)) then
set x to y
set v to it
end if
end tell
end repeat
set my p's item x to u
set my p's item l to v
-- Perform any additional actions that may be required after this swap.
compObj's swap(l, x)
set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (compObj's isLess(v, u)) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
tell my p's item j
if (compObj's isLess(v, it)) then
set my p's item (j + 1) to it
else
set my p's item (j + 1) to v
-- Perform any additional actions that may be required after this insertion.
compObj's shift(j + 1, i)
exit repeat
end if
end tell
end repeat
else
set u to v
end if
end repeat
end isrt
end script
set listLen to (count theList)
if (listLen > 1) then -- otherwise the handler will error
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
if (l > r) then
set temp to l
set l to r
set r to temp
end if
if (r - l < o's cutoff) then
-- Skip the Quicksort if cutoff or less items
else
o's qsrt(l, r)
end if
o's isrt(l, r)
end if
end if
return -- nothing
end CustomQsort
on sortListsByNthItem(listOfLists, n)
script o
on isGreater(a, b)
(item n of a > item n of b)
end isGreater
on isLess(a, b)
(item n of a < item n of b)
end isLess
-- These two handlers aren't used in the current context,
-- but have to exist to match the calls in CustomQsort.
on swap(i, j)
end swap
on shift(i, j)
end shift
end script
CustomQsort(listOfLists, 1, -1, o)
end sortListsByNthItem
set listOfLists to {{"New York", "USA"}, {"Paris", "France"}}
sortListsByNthItem(listOfLists, 2) -- Sort by second item in each list.
listOfLists --> {{"Paris", "France"}, {"New York", "USA"}}
Hi Nigel,
Again, thanks for the solution. Previous examples posted didn’t solved “exactly” the problem.
You are “Sorting Guru”.
I will study the routine to implement last feature: sort ascending or descending (for numbers and dates) with additional parameter
For now many thanks again.
Steve H.
One of the nice things about CustomQsort is that it’ll do a reverse sort if the contents of the isGreater and isLess handlers are swapped. I don’t know what kind of parameter you want to use to signify ascending or descending sorts. If it was, say, 1 for ascending sorts and -1 for descending sorts, you could modify my sortListsByNthItem handler and the top-level code something like this:
-- CustomQsort handler needed too.
on sortListsByNthItem(listOfLists, n, direction)
script o -- Script object for forward (ascending) sort.
on isGreater(a, b)
(item n of a > item n of b)
end isGreater
on isLess(a, b)
(item n of a < item n of b)
end isLess
-- These two handlers aren't used in the current context,
-- but have to exist to match the calls in CustomQsort.
on swap(i, j)
end swap
on shift(i, j)
end shift
end script
script r -- Script object for reverse (descending) sort.
property parent : o -- Inherit all the properties (inc. handlers) of o.
-- Swap the isGreater and isLess handlers.
property isGreater : o's isLess
property isLess : o's isGreater
end script
CustomQsort(listOfLists, 1, -1, item direction of {o, r})
end sortListsByNthItem
set listOfLists to {{"New York", "USA"}, {"Tallinn", "Estonia"}, {"Riga", "Latvia"}, {"Paris", "France"}}
sortListsByNthItem(listOfLists, 2, -1) -- Sort by second item in each list, reverse sort.
listOfLists --> {{"New York", "USA"}, {"Riga", "Latvia"}, {"Paris", "France"}, {"Tallinn", "Estonia"}}
Hi Nigel,
I executed some test and the “magic” routine is very fast. To sort a list of list of 10,000 item (where each item is composed by string, number and date items) take about 2.5 sec (!!!)
Somebody say: “Nigel is excellent for AppleScript speed. Maybe the best in the world.” I confirm.
Below your complete script with a routine to generate a Tab-Text file useful for test speed.
Thanks again.
property listOfLists : missing value – to speedup the access to list generation using “my” term
– Generate the Tab-Textfile to test
set filePathTest to “Leopard:Users:steve:Desktop:tableTest.txt”
set fileRef to open for access file filePathTest with write permission
set eof of fileRef to 0
repeat with j from 1 to 10000
set filePath to “Macintosh HD:Users:steve:Test:image_” & (random number from 10000 to 90000)
set fileSize to random number from 100000 to 500000
set creationDate to (current date) + (random number from 5000 to 500000)
write (filePath & tab & fileSize & tab & creationDate & return) as «class utf8» to fileRef
end repeat
close access fileRef
– Read the Tab-Text file and convert it into List of List
set fileRef to open for access file filePathTest
set listOfLists to read fileRef using delimiter return as «class utf8»
close access fileRef
repeat with j from 1 to count my listOfLists
set AppleScript’s text item delimiters to tab
set textItemsTmp to text items of item j of my listOfLists
set AppleScript’s text item delimiters to “”
set item 2 of textItemsTmp to (item 2 of textItemsTmp) as integer
set item 3 of textItemsTmp to date (item 3 of textItemsTmp)
set item j of my listOfLists to textItemsTmp
end repeat
set t1 to current date
sortListsByNthItem(listOfLists, 3, 1) – {List, column to sort, flag 1 for ascending, -1 for descending}
set t2 to current date
set t3 to t2 - t1
on sortListsByNthItem(listOfLists, n, direction)
script o – Script object for forward (ascending) sort.
on isGreater(a, b)
(item n of a > item n of b)
end isGreater
on isLess(a, b)
(item n of a < item n of b)
end isLess
-- These two handlers aren't used in the current context,
-- but have to exist to match the calls in CustomQsort.
on swap(i, j)
end swap
on shift(i, j)
end shift
end script
script r -- Script object for reverse (descending) sort.
property parent : o -- Inherit all the properties (inc. handlers) of o.
-- Swap the isGreater and isLess handlers.
property isGreater : o's isLess
property isLess : o's isGreater
end script
CustomQsort(listOfLists, 1, -1, item direction of {o, r})
end sortListsByNthItem
on CustomQsort(theList, l, r, compObj)
script o
property cutoff : 10
property p : theList
on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)
repeat while (j > i)
set u to my p's item i
repeat while (compObj's isLess(u, v))
set i to i + 1
set u to my p's item i
end repeat
set w to my p's item j
repeat while (compObj's isGreater(w, v))
set j to j - 1
set w to my p's item j
end repeat
if (i > j) then
else
set my p's item i to w
set my p's item j to u
-- Perform any additional actions that may be required after this swap.
compObj's swap(i, j)
set i to i + 1
set j to j - 1
end if
end repeat
if (j - l < cutoff) then
else
qsrt(l, j)
end if
if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt
on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r
set v to my p's item x
set u to v
repeat with y from (x + 1) to z
tell my p's item y
if (compObj's isLess(it, v)) then
set x to y
set v to it
end if
end tell
end repeat
set my p's item x to u
set my p's item l to v
-- Perform any additional actions that may be required after this swap.
compObj's swap(l, x)
set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (compObj's isLess(v, u)) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
tell my p's item j
if (compObj's isLess(v, it)) then
set my p's item (j + 1) to it
else
set my p's item (j + 1) to v
-- Perform any additional actions that may be required after this insertion.
compObj's shift(j + 1, i)
exit repeat
end if
end tell
end repeat
else
set u to v
end if
end repeat
end isrt
end script
set listLen to (count theList)
if (listLen > 1) then -- otherwise the handler will error
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
if (l > r) then
set temp to l
set l to r
set r to temp
end if
if (r - l < o's cutoff) then
-- Skip the Quicksort if cutoff or less items
else
o's qsrt(l, r)
end if
o's isrt(l, r)
end if
end if
return -- nothing
end CustomQsort
Using the test data creator above which creates a tab delimited file
with 10,000 records.
The above code sorts on the b or file size column. If you change
the letter to ‘a’ then it will sort on the file path column and
to ‘c’ will sort on the date column.
To reverse the results you add ‘.reverse’ to the end like so.
You can sort on multiple columns. This will sort on the ‘b’
column first and then by the ‘c’ column.
Wow!!!
Even if you “changed” language (at the moment Nigel is the winner using AS) the performances are impressive!!!
But you need to explain me how to call the ruby script from AS. I presume with do shell script… and if the data are returned
And the returned data are string or list of list like AS?
At this point I need to start from my “list of list” that I manage inside ASS and pass the “list of list” to Ruby Script that need to sort and return me the same list of list sorted
I ask you last effort. It’s impressive how few line of code Ruby require!
Steve H.
If you are using this inside ASS then I would stick with Nigel’s version.
BTW, if you are using this list in a table you get sorting for free in ASS.
Hi Craig,
Yes, I know about sorting table using Table View in ASS. But sometimes is useful to have an independent routine to sort list or list of list for others use.
Thanks anyway for the faster Ruby script.
Steve