# QuickSort Algorithm

Except for pathological cases, Tony Hoare’s QuickSort algorithm is often used for sorting large lists and except for more complex algorithms is certainly among the fastest. Here’s an AppleScript version of QuickSort. On my machine (dual-core G5/2.3GHz) it will sort a list of 1686 items (3 concatinated sets of the words of “lorem ipsum”) in approximately 4.45 seconds. I’ll send my list on request.

To sort an entire list, set leftEnd to 1 and rightEnd to count List. These arguments are required because the alogorithm is recursive - it successively divides and conquers.

``````Qsort(yourList, 1, count yourList)
``````

The handler:

``````to Qsort(array, leftEnd, rightEnd) -- Hoare's QuickSort Algorithm
script A
property L : array
end script
set {i, j} to {leftEnd, rightEnd}
set v to item ((leftEnd + rightEnd) div 2) of A's L -- pivot in the middle
repeat while (j > i)
repeat while (item i of A's L < v)
set i to i + 1
end repeat
repeat while (item j of A's L > v)
set j to j - 1
end repeat
if (not i > j) then
tell A's L to set {item i, item j} to {item j, item i} -- swap
set {i, j} to {i + 1, j - 1}
end if
end repeat
if (leftEnd < j) then Qsort(A's L, leftEnd, j)
if (rightEnd > i) then Qsort(A's L, i, rightEnd)
end Qsort
``````

[EDIT: fixed last two lines, were sort(), now Qsort()]

That looks very similar to an early version of the qsort that Arthur Knapp and I wrote a couple of years ago. I suppose Arthur got the algorithm from the same source. It sorts the actual list passed to it, rather than leaving it as it is and returning a sorted copy. Some people have said they find this confusing, but we think it’s OK as long as potential users are aware of the fact.

We set out to write the fastest vanilla sort we could and included every AppleScript speed trim we could find. Arthur’s research also turned up the idea of switching to an insertion sort for the “fine tuning”. QuickSort is quite a coarse tool. It’s very effective in the early stages of imposing order on chaos, but as the list becomes more nearly sorted, QuickSort still does a lot of recursing and checking even though it has to move fewer and fewer items around in the list. An insertion sort, on the other hand, while less efficient in the early stages of a sort, does a lot less work when less needs to be done. The sort below stops the QuickSort recursions at levels where 10 or less items need to be sorted, and finishes off with an insertion sort of the entire, nearly-sorted list. On my 2.0 GHz, dual-processor G5, your Qsort sorts a list of 4000 random integers with values between 0 and 10,000 in about 23.5-24.5 seconds. This does the same job in about 0.39 to 0.44 seconds:

13th September 2010: I’ve uploaded a new version of this sort, as part of a collection, to ScriptBuilders.
19th November 2023: ScriptBuilders was discontinued a couple of weeks after I uploaded the collection, so the above links are no longer valid!

``````on qsort(theList, l, r)
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 -- nothing
end qsort

-- Demo: sort a list of 4000 integers between 0 and 10,000.
set l to {}
repeat with i from 1 to 4000
set end of my l to random number 10000
end repeat
set t to (GetMilliSec)
qsort(l, 1, -1)
((GetMilliSec) - t) / 1000
``````

Note that, having had more time for development, this handler also allows negative indices for the sort range parameters and the left or the right one can be specified first.

There’s also a CustomQsort version of this, if you’re interested, whose parameters include a script object containing handlers which do the actual comparisons for the sort and return whether one item is “greater” or “less” than the other. This isn’t quite as fast as qsort, but it’s very powerful. Depending on the handlers passed, CustomQsort can sort a list of lists by particular items in the lists, records by particular properties, etc. It can even do reverse sorts.

Later edit:

The main cause of the speed difference between the two handlers appears to be this line in yours:

``tell A's L to set {item i, item j} to {item j, item i} -- swap``

Apart from the “setting by list”, which detracts slightly from the speed, the ‘tell A’s L’ tells the result of getting the list to change those items. The list-in-a-script-object speed approach needs the reference to be told:

``tell (a reference to A's L) to set {item i, item j} to {item j, item i} -- swap``

I really “dug” the -1 argument rather than “count theList”. Why don’t I think of those things. (It doesn’t work on my version because it finds the middle by summing the beginning and end div 2, but that would be easy to fix)

With my test list of text to be ASCII sorted, yours and Arthur’s version is 10 times faster - an incredible speedup. With your random number sort which is several times larger than my list, the ratio is even more fantastic: 20 seconds for mine, approximately a third of a second for yours; 60:1. Wow. I think I’ll keep the Garvey/Knapp sort in place of mine.

I will say that in reading up on the recursive QuickSort, there were several algorithms like yours that switched to more direct sorting as the sort progressed. I note that you used a cutoff of 10, and others I saw used 8. I also note that you have tucked the entire algorithm inside the script rather than just the properties. I’ll play with that on my version just to see the effect.

I’ll remember that there is also a CustomQSort handler or if you think it worthwhile, perhaps you’ll post it here. In ScriptBuilders, Steve LoBasso has also posted “QuickSort 1.1” which seems to have many degrees of freedom. His is non-recursive to avoid large memory requirements.

Amazed as always, Nigel. It’s clear that as a latecomer to the scene (I started AppleScripting in February of last year) I missed all the fun.

Arthur and I thrashed out our version over several weeks of e-mail correspondence. We had plenty of time to come up with niceties like that.

Did you notice the later edit at the end of my post? There’s a line in your version that inadvertently bypasses the list-in-a-script-object reference. When that’s sorted out, the difference in speed between the two versions is very much less!

Arthur’s a professional scripter and more versed in the literature than I am. It was his reading that turned up the main algorithms we used. A few empirical tests suggested that 10 was a reasonable cut-off value. I think we decided that the “perfect” value probably depended on the length and original order of the list itself ” which of course can’t be known in advance.

I don’t think it makes any difference to the performance. It’s just a convenient way to have all the processes, including a recursive one, inside the same handler. It’s an approach that’s been criticised by some people, who feel it’s better practice to include the main handler in the script object rather than vice versa. I’m not persuaded it’s necessarily better, but this the basic shape of what they mean:

``````script qsort
property cutoff : 10
property p : missing value

on qsrt(l, r)
-- As in my earlier script.
end qsrt

on isrt(l, r)
-- As in my earlier script.
end isrt

on sort(theList, l, r)
set p to theList

-- Do everything that the qsort() handler does
-- in the earlier script, but don't mention 'o'!
if (r - l < cutoff) then
-- Skip the Quicksort if cutoff or less items
else
qsrt(l, r)
end if
isrt(l, r)
end sort
end script

tell qsort to sort(myList, 1, -1)
``````

I’ll post it later on. I’m having some more thoughts about it that I want to try out first.

I hope it’s not all over yet! :o

Here’s the CustomQsort handler I mentioned earlier. Sorts work by comparing items in a list and repositioning them according to their relative values. But comparing items directly isn’t always possible or desirable. You might want to sort a list of lists, or of records, or of files, or even of mixed classes. Or the sort order might need to be modified in some way. Each contingency requires a different method for determining which items are “greater” or “less” than others, which means having either several specialised sort handlers or a customisable one such as CustomQsort. CustomQsort does the physical work of moving items around in the list, but the comparisons are done by short handlers in a script object that’s passed to CustomQsort as a parameter.

Arthur and I had slightly different preferences for what the script object should contain, so this is just my version:

13th September 2010: I’ve uploaded a new version of this sort with an improved customisation regime, as part of a collection, to ScriptBuilders. The new version, though, will accept customisation scripts written for the one below, which has been around for quite a while now.

``````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

-- Inform the script object of 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
repeat with y from (x + 1) to z
if (compObj's isLess(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

-- Inform the script object of 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
if (compObj's isLess(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

-- Inform the script object of this insertion.
compObj's shift(j + 1, i)

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 -- nothing
end CustomQsort
``````

The compObj parameter should be a script object containing these four handlers and anything else that may be required:

isLess(a, b): decides if the value of a is “less” than the value of b or not. (Returns ‘true’ or ‘false’.)
isGreater(a, b): decides if the value of a is “greater” than the value of b, ditto.
swap(a, b): called by CustomQsort after each swap performed in the list being sorted. a and b are the indices of the swapped items. This handler would normally be left empty, but it could be used to do the same swap in another list.
shift(a, b): called by CustomQsort after each “insertion” performed in the list being sorted. The parameters indicate that item b of the list has been moved to position a after items a thru (b - 1) have been shifted uplist. This handler would also normally be left empty, but could be used to echo the moves in another list.

The idea is that you write your own script objects to control how the sort is done. For a straightforward sort similar to qsort’s, isLess() and isGreater() would do simple comparisons and swap() and shift() would do nothing:

``````script standardSort
on isLess(a, b)
(a < b)
end isLess

on isGreater(a, b)
(a > b)
end isGreater

on swap(a, b)
end swap

on shift(a, b)
end shift
end script

CustomQsort(myList, 1, -1, standardSort)
``````

If you wanted to sort one list and echo the moves in another ” say you had a list of files that had to be sorted in parallel with a list of corresponding modification dates ” you’d use the swap() and shift() handlers to perform the slave moves in the file list:

``````script slaveSort
property slaveList : missing value

on isLess(a, b)
(a < b)
end isLess

on isGreater(a, b)
(a > b)
end isGreater

-- Do the same swap in slaveList that CustomQsort has just done in the list it's sorting.
on swap(a, b)
tell item a of my slaveList
set item a of my slaveList to item b of my slaveList
set item b of my slaveList to it
end tell
end swap

-- Do the same shift and insertion in slaveList that CustomQsort has just done in the list it's sorting.
on shift(a, b)
tell item b of my slaveList
repeat with i from b - 1 to a by -1
set item (i + 1) of my slaveList to item i of my slaveList
end repeat
set item a of my slaveList to it
end tell
end shift
end script

set slaveSort's slaveList to myFileList
CustomQsort(myDateList, 1, -1, slaveSort)
--> myDateList sorted by the dates it contains
--> myFileList sorted so that the files still correspond to the dates
``````

For a spreadsheet-style sort, sorting a list of lists on, say, the third item in each list:

``````script listSort
property i : missing value

on isLess(a, b)
(a's item i < b's item i)
end isLess

on isGreater(a, b)
(a's item i > b's item i)
end isGreater

on swap(a, b)
end swap

on shift(a, b)
end shift
end script

set listSort's i to 3
CustomQsort(myListOfLists, 1, -1, listSort)
``````

For a reverse sort, simply lie to CustomQsort by swapping the contents of the isLess() and isGreater() handlers.

``````script reverseSort
on isLess(a, b)
(a > b)
end isLess

on isGreater(a, b)
(a < b)
end isGreater

on swap(a, b)
end swap

on shift(a, b)
end shift
end script

CustomQsort(myList, 1, -1, reverseSort)
``````

And so on.

Within the same script, handlers and properties that are common to different script objects can be shared. For example, if there’s a standard sort and a reverse sort in the same script, the amount of code in one of the script objects could be reduced by making it a child of the other:

``````script standardSort
on isLess(a, b)
(a < b)
end isLess

on isGreater(a, b)
(a > b)
end isGreater

on swap(a, b)
end swap

on shift(a, b)
end shift
end script

script reverseSort
property parent : standardSort

on isLess(a, b)
(a > b)
end isLess

on isGreater(a, b)
(a < b)
end isGreater
end
``````

With standardSort as its ‘parent’, reverseSort inherits all standardSort’s handlers (and would inherit its properties too, if it had any), so there’s no need to write out the swap() and shift() handlers in reverseSort itself. The other two handlers, though, have to be different and so are written out, which overrides the inheritance as far as they’re concerned. The two script objects thus have their own isLess() and isGreater() handlers, but share standardSort’s swap() and shift() handlers.

It’s possible to go even further with the above example, as reverseSort’s isLess() and isGreater() handlers are the same as standardSort’s isGreater() and isLess() handlers. These too can be shared by assigning them to the relevantly named variables in reverseSort. The full specification for the reverseSort script object would then be:

``````script reverseSort
property parent : standardSort

property isLess : standardSort's isGreater
property isGreater : standardSort's isLess
end script
``````

G’day

I’m new at scripting, and wanted a fast sort, and found this via Google.

Problem is, I’m having trouble working out how to call the Qsort routine.

I’ve tried My qsort, tell Qsort, and just Qsort, but nothing calls the routine.

Thanks, Santa

I’ve solved it.

Apparently in the transfer of the code something happened to the “Qsort” words.

Once I re-typed in the first & last lines, & renamed the routine, all was well, thanks.

BUT, I’ve got another problem you guys might be able to help with. I want to sort a list of path names that your routine won’t handle.

It’s in the form…

set thelist to (selection as list)
(Sort thelist alphabetically)

I can sort the of each item in thelist, but I need to keep the pathnames.

Regards

Santa

Hi Santa;

This is a simple replacement sort, but I wrote it so I could take three lists of the same length containing related data and sort on one of them while keeping the other two in the same order. (I think the original idea was Kai Edwards’). You can easily modify it for only two lists.

``````to sort_items(sortList, SecondList, thirdList)
script L
property srt : sortList
property sec : SecondList
property thd : thirdList
end script
tell (count L's srt) to repeat with i from (it - 1) to 1 by -1
set s to (L's srt)'s item i
set r to (L's sec)'s item i
set q to (L's thd)'s item i
repeat with i from (i + 1) to it
tell (L's srt)'s item i to if s > it then
set (L's srt)'s item (i - 1) to it
set (L's sec)'s item (i - 1) to (L's sec)'s item i
set (L's thd)'s item (i - 1) to (L's thd)'s item i
else
set (L's srt)'s item (i - 1) to s
set (L's sec)'s item (i - 1) to r
set (L's thd)'s item (i - 1) to q
exit repeat
end if
end repeat
if it is i and s > (L's srt)'s end then
set (L's srt)'s item it to s
set (L's sec)'s item it to r
set (L's thd)'s item it to q
end if
end repeat
end sort_items
``````

Updated by adding the internal script to speed it up

I’ve tagged a reply onto Santa’s thread in the OS X forum, pointing out the Finder’s sort command, which might be what’s needed.

G’day

I think I’ve found a bug in the Qsort routine.

When I sorted a list of only 149 items, it left the top (last) item unsorted.

It seems to think 89 if after 346

I’m finding the routine very, very useful thanks, but wonder if someone could fix it for me. The coding is way beyound me!

Regards

Santa

G’day again

I think there’s also a bug in the Hoare’s quicksort routine. I tried using it and it’s leaving large numbers stranded somewhere in the middle of the list.

I need a reliable sort that allows me to get the maximum & minimum from both ends, as well as the sorted list, in a single list.

All this just to place icons on the desktop or windows.

Thanks Nigel, that sort was what I needed, but I’d rather not restrict my icon sort routine just for 10.4, so I’ve opted for a slower method, if I can just get a sort that works!

Regards, Santa

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

G’day, Santa;

I don’t have a problem with the script in item 2 of this thread whether the sorted items are strings of characters or large numbers. Are you setting l to -1 and r to 1?

I suspect that Santa’s sorting files with names like “89.jpg” and “346.jpg” and wants them sorted numerically rather than lexically.

The handlers above are sensitive to the AppleScript string-handling environment, so in Tiger, you could use the new considering numeric strings attribute:

``````set myList to {"346.jpg", "4.jpg", "87.jpg"}
considering numeric strings
qsort(myList, 1, -1)
end considering

myList
--> {"4.jpg", "87.jpg", "346.pg"}
``````

To sort Finder items on systems before Tiger, there’s a script of mine in ScriptBuilders called FinderSort(), which imitates how I guessed sort would work in OS X when it was eventually reinstated. This sorts numeric strings numerically, but is a bit awkward to use and only works with collective Finder references, not with the list returned by the Finder’s selection. (I guessed wrong there.)

It’s possible to reproduce the considering numeric strings effect with systems earlier than Tiger, but it takes a lot more code. However, it’s quite fast.

1. Get the names of the files/folders.
2. Pad out any numerics in the names to a fixed width with leading zeros.
3. Use a slave-sort script object with CustomQsort to sort the doctored names lexically, copying the sort moves in the list of files.
``````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

-- Inform the script object of 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
repeat with y from (x + 1) to z
if (compObj's isLess(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

-- Inform the script object of 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
if (compObj's isLess(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

-- Inform the script object of this insertion.
compObj's shift(j + 1, i)

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 -- nothing
end CustomQsort

on getItemNames(theItems)
set AppleScript's text item delimiters to ":"
set theNames to {}
repeat with thisItem in theItems
set thisPath to thisItem as Unicode text
set thisName to text item -1 of thisPath
if ((count thisName) is 0) then set thisName to text item -2 of thisPath
set end of theNames to thisName
end repeat

return theNames
end getItemNames

set AppleScript's text item delimiters to return
set originalNames to originalNames as Unicode text
set theDigits to "0123456789" as Unicode text
set theZeros to "00000000" as Unicode text
script o
property doctoredNames : {}
end script
set i to 1
considering case
set numeric to (character i of originalNames is in theDigits)
repeat with j from 1 to (count originalNames)
set c to character j of originalNames
if (numeric) then
if (c is in theDigits) then
else
if (pad > 0) then set end of o's doctoredNames to text 1 thru pad of theZeros
set numeric to false
end if
else if (c is in theDigits) then
if (j > i) then set end of o's doctoredNames to text i thru (j - 1) of originalNames
set i to j
set numeric to true
end if
end repeat
if (numeric) then
if (pad > 0) then set end of o's doctoredNames to text 1 thru pad of theZeros
end if
if (i is not greater than j) then set end of o's doctoredNames to text i thru j of originalNames
end considering
set AppleScript's text item delimiters to ""

return paragraphs of (o's doctoredNames as Unicode text)

tell application "Finder" to set theSelection to the selection

set astid to AppleScript's text item delimiters
set selectionNames to getItemNames(theSelection)
set AppleScript's text item delimiters to astid

script slaveSort
property slaveList : missing value

on isLess(a, b)
(a < b)
end isLess

on isGreater(a, b)
(a > b)
end isGreater

-- Do the same swap in slaveList that CustomQsort has just done in the list it's sorting.
on swap(a, b)
tell item a of my slaveList
set item a of my slaveList to item b of my slaveList
set item b of my slaveList to it
end tell
end swap

-- Do the same shift and insertion in slaveList that CustomQsort has just done in the list it's sorting.
on shift(a, b)
tell item b of my slaveList
repeat with i from b - 1 to a by -1
set item (i + 1) of my slaveList to item i of my slaveList
end repeat
set item a of my slaveList to it
end tell
end shift
end script

set slaveSort's slaveList to theSelection
CustomQsort(doctoredNames, 1, -1, slaveSort)

theSelection
``````

If you’re more interested in the sorted names than in the sorted files/folders, substitute selectionNames for theSelection in the last three lines.

The above is very long (as you may have noticed!) but the CustomQsort handler can be saved as a separate script and loaded as a library.

Edit: Sorry. Although this works, it isn’t quite as fast as I’d thought when the list contains a very large number of Finder items. The sort itself is virtually instantaneous, but the preparation of the names takes a while.

G’day fellas.

Thanks for the replies. Here’s an extract from my script. (this is to the long (shorter time) version of Qsort)

``````
on mainCycle()
tell application "Finder"

set thelist to (selection as list)
set distribute to number of items in thelist
set thisItem to item 1 of thelist
set we_are_on_desktop to ((folder of thisItem as alias) is (path to desktop folder))
repeat with thisItem in thelist
if we_are_on_desktop then
set temp to desktop position of thisItem
else
set temp to position of thisItem
end if
set listofXY to listofXY & item 1 of temp & item 2 of temp as list
set Xdifflist to Xdifflist & item 1 of temp as list
set ydiffList to ydiffList & item 2 of temp as list
end repeat

my Qsort(Xdifflist, 1, (length of Xdifflist))
my Qsort(ydiffList, 1, length of ydiffList)

-- these are necessary 'cause Hoare's sort routine seems faulty!!!

set LargestX to 0
set SmallestX to 10000
set LargestY to 0
set SmallestY to 10000
repeat with x from 1 to length of Xdifflist
if LargestX < item x of Xdifflist then set LargestX to item x of Xdifflist
if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
end repeat
end tell
end mainCycle

``````

Note that the fault is intermittant. I had arranged a block of icons alphabetically, and chose (from my full script) to arrange alphabetically again. The second time the reult of the sort saw the icons occupy only half the number of original rows, because the largest value of Y had not trickled to the top.

I stopped the script, re-ran it and on the second run it sorted the values correctly, placing the largest value of Y at the top.

Hoarse’s just doesn’t seem to run numbers by it. I just assumed these routines would sort numbers.

Regards

Santa

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

I’ve used them to sort dates and it certainly sorts a list of numbers only correctly. I think Nigel’s “considering” clause is required if the list is mixed.

I definately think there’s a bug in the Hoaer’s Qsort Routine.

I’ve re-submitted my latest version of the icon arranger, but using a modified version of it I’ve been able to asertain there’s an error that’s reproducable.

I’ll post the modified version here, and hope it’s not too long.

Use it to arrange a window with lots of icons, alphabetically. It won’t beep on the first pass.

Now arrange alphabetically again, while the icons are still selected. You’ll get at least one beep (or at least, I can).

Rinse & Repeat

Fingers crossed it works for you as it does for me.

(Edit) I’ve just found it won’t beep if it’s run on a folder that’s been organized by name by the Finder. The icons have to be physically shifted by the routine, before it will beep. Play around with it, scrunch 'em up tight, then arrange 'em Alphabetically.

Regards, Santa

``````
--  ****************************
--  * Copyright 2006, Brian Christmas  *
--  *                                                    *
--  *   From the Sunny Land of Oz        *
--  *             Version 1.2                      *
--  *             31/07/06                        *
--  *                                                    *
--  *          bec9@tpg.com.au               *
--  ****************************
-- Qsort routine from MacScripter
-- http://bbs.applescript.net/viewtopic.php?id=17340

-- This script works best if some approximate
-- organizing is done first, otherwise
-- extra columns may be added.

-- Also note that if insufficient side margins are not allowed for when arranging a window,
-- the Finder may 'shake' the window from side to side, thereby altering the icon placement.

-- In addition, if you have a window open showing the desktop icons in it, DON'T  try to
-- arrange  the window. It only organizes the ACTUAL desktop. Hairy things happen to it.
-- Feedback appreciated, especially suggestions to speed this up.

global overlapFlag
global we_are_on_desktop
global seedValue
global AlphabetMin

-- *******************************
-- **** Set this as minimum amount ****
-- ****   allowed between columns     ****
-- *******************************
set seedValue to 100

-- *******************************
-- **** Set this as minimum amount ****
-- ****          of icons to offer             ****
--****          alphabet sorting             ****
-- *******************************
set AlphabetMin to 20

my mainCycle()

on mainCycle()
tell application "Finder"
set currX to 0
set LargestY to 0
set SmallestY to 0
set SmallestX to 0
set LargestX to 0
set listofXY to ""
set overlapFlag to 0
set Xdifflist to ""
set ydiffList to ""
set columnCount to ""

try
-- make array of positions

set thelist to (selection as list)
set distribute to number of items in thelist
--- ARE WE ON THE DESKTOP?
if distribute = 0 then
display dialog "There are no icons selected." & return & return & "Try selecting some, and running the script again." buttons {"OK"}

end if
set thisItem to item 1 of thelist
set we_are_on_desktop to ((folder of thisItem as alias) is (path to desktop folder))

-- Heaps of icons? then ask!
set AlphaFlag to false
if length of thelist > (AlphabetMin - 1) then
display dialog " there are " & length of thelist & " icons selected." & return & return & "Do you want to sort them alphabetically or normally?" & return & return & "(it takes a while with large numbers)" buttons {"Alphabetically please", "Normally thanks", "Cancel"}
set AlphaFlag to (the button returned of the result is "Alphabetically please")
end if

repeat with thisItem in thelist
if we_are_on_desktop then
set temp to desktop position of thisItem
else
set temp to position of thisItem
end if
set listofXY to listofXY & item 1 of temp & item 2 of temp as list
--set listofXY to listofXY & item 2 of temp as list
set Xdifflist to Xdifflist & item 1 of temp as list
set ydiffList to ydiffList & item 2 of temp as list
end repeat

my Qsort(Xdifflist, 1, (length of Xdifflist))
my Qsort(ydiffList, 1, length of ydiffList)

-- these are necessary 'cause Hoare's sort routine is faulty!!!

set LargestX to last item of Xdifflist
set SmallestX to 10000
set LargestY to 0
set SmallestY to 10000
repeat with x from 1 to length of Xdifflist
if LargestX < item x of Xdifflist then
beep
set LargestX to item x of Xdifflist
end if
if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
end repeat

if we_are_on_desktop then
set seedValueadd to ((label position of icon view options of window of desktop) = right)
else
set seedValueadd to ((label position of icon view options of window 1) = right)
end if

-- If text is on right, double the minimum spacing
if seedValueadd = true then set seedValue to seedValue * 2

-- Now the guessing part, what to distribute as column spacing?

set setX to seedValue
repeat with x from ((length of Xdifflist) - 1) to 1 by -1
set diff to ((item (x + 1) of Xdifflist) - (item x of Xdifflist))
if diff < (2 + ((LargestX - SmallestX) / 2)) then
if (diff > seedValue - 1) then
set setX to diff
end if
end if
end repeat
--Now, set width between columns

set columnSpaces to ((LargestX - SmallestX + (setX / 2)) div setX)

--Only 1 column? then set columnSpace to ....

if columnSpaces < 2 then set columnSpaces to columnSpaces + 1
set ColumnWidth to (LargestX - SmallestX) / columnSpaces
if ColumnWidth < seedValue then set ColumnWidth to seedValue
set columnCount to columnSpaces + 1
set columnCountStore to 0
repeat with x from 1 to columnSpaces
set columnCountStore to columnCountStore & 0
end repeat
repeat with x from 1 to columnCount
set minX to SmallestX + ((x - 1) * ColumnWidth) - (ColumnWidth / 2)
set maxX to SmallestX + ((x - 1) * ColumnWidth) + (ColumnWidth / 2)

repeat with thisItem in thelist
if we_are_on_desktop then
set temp to desktop position of thisItem
else
set temp to position of thisItem
end if
set tempY to item 2 of temp
set tempX to item 1 of temp
-- if icon falls in the range of column, add it up
if ((tempX = minX) or (tempX > minX)) and (tempX < maxX) then
set item x of columnCountStore to ((item x of columnCountStore) + 1)
end if
end repeat
end repeat

if AlphaFlag then --> Alphabet arrange set
set IconSpacing to (LargestY - SmallestY) / ((distribute / columnCount) div 1)
else

-- Now find Column with largest number of icons

set maxCount to 2 ---> to avoid division by zero if only one row
repeat with x from 1 to number of items in columnCountStore
if item x of columnCountStore > maxCount then
set maxCount to item x of columnCountStore
end if
end repeat
set IconSpacing to ((LargestY - SmallestY) / (maxCount - 1))
end if

if AlphaFlag then
my SortbyAlphabet(thelist, SmallestX, LargestX, SmallestY, ColumnWidth, IconSpacing)
else
-- Now place Icons
-- Loop ColumnCount times....
repeat with MoveColumns from 1 to columnCount
set tempList to ""
set minX to SmallestX + ((MoveColumns - 1) * ColumnWidth) - (ColumnWidth / 2)
set maxX to SmallestX + ((MoveColumns - 1) * ColumnWidth) + (ColumnWidth / 2)

repeat with thisItem in thelist
if we_are_on_desktop then
set temp to desktop position of thisItem
else
set temp to position of thisItem
end if
set tempX to item 1 of temp
if (((tempX = minX) or (tempX > minX)) and ((tempX < maxX) or (tempX = maxX))) then
--Build list of icon XY positions in column
if tempList = "" then
set tempList to tempX as list
set tempList to tempList & item 2 of temp
else
set tempList to tempList & tempX
set tempList to tempList & item 2 of temp
end if
end if
end repeat
-- This is the X value of the column
set tempX to SmallestX + ((MoveColumns - 1) * ColumnWidth)
--
-- Now go and shift a column of the little bastards around!
--
my ArrangeColumn(thelist, tempList, tempX, SmallestY, IconSpacing)

end repeat
end if
end try
if overlapFlag > 0 then
if overlapFlag = 1 then
set Errormessage to "There was an overlapping icon." & return & return & "I'll try running  the script again, as I've nudged it."
else
set Errormessage to "There were " & overlapFlag & " overlapping icons." & return & return & "I'll try running  the script again, as I've nudged them."
end if
display dialog Errormessage buttons {"OK", "Cancel"}
if (the button returned of the result is "OK") then
my mainCycle() -- Do the run around again
end if
end if
end tell
end mainCycle

-- =============================================================

on ArrangeColumn(thelist, tempList, currX, SmallestY, IconSpacing)
tell application "Finder"
set listofXY to ""
try
-- problem with 1 entry not seen as an item
set Ylist to 0
--
-- Now make list of Y positions
repeat with thisItem in thelist
repeat
if we_are_on_desktop then
set temp to desktop position of thisItem
else
set temp to position of thisItem
end if
if temp is in tempList then
if item 2 of temp is in Ylist then --> Oops! Some icons together!
set tempShift to item 1 of temp & ((item 2 of temp) + 1 + overlapFlag)
set overlapFlag to overlapFlag + 1
--Nudge overlapping icons
if we_are_on_desktop then
set desktop position of thisItem to tempShift
else
set position of thisItem to tempShift
end if
-- now reset templist Y position
set x to 2
repeat
if item x of tempList = item 2 of temp then
set item x of tempList to item 2 of tempShift
exit repeat
else
set x to (x + 2)
if x > number of items in tempList then exit repeat --> just in case
end if
end repeat
else
set Ylist to Ylist & item 2 of temp
exit repeat
end if
else
exit repeat
end if
end repeat
end repeat
--
-- Sort Y positions
my Qsort(Ylist, 1, length of Ylist)
--
-- Now position each
repeat with thisItemTwo in thelist
if we_are_on_desktop then
set temp to desktop position of thisItemTwo
if temp is in tempList then
set tempY to item 2 of temp
repeat with countdown from 2 to (number of items in Ylist)
if item countdown of Ylist = tempY then
set currY to SmallestY + ((countdown - 2) * IconSpacing)
set countdown to (number of items in Ylist)
end if
end repeat
set desktop position of thisItemTwo to {currX, currY}
end if
else
set temp to position of thisItemTwo
if temp is in tempList then
set tempY to item 2 of temp
repeat with countdown from 2 to (number of items in Ylist)
if item countdown of Ylist = tempY then
set currY to SmallestY + ((countdown - 2) * IconSpacing)
set countdown to number of items in Ylist
end if
end repeat
set position of thisItemTwo to {currX, currY}
end if
end if
end repeat
end try
end tell
end ArrangeColumn

on SortbyAlphabet(thelist, SmallestX, LargestX, SmallestY, ColumnWidth, IconSpacing)

tell application "Finder"
try
set tempList to ""
-- First, sort list of icons alphabetically
set xx to length of thelist
repeat with x from 1 to xx
set firstGo to name of item x of thelist as string
if tempList = "" then
set tempList to firstGo as list
else
set tempList to tempList & firstGo as list
end if
end repeat
my Qsort(tempList, 1, xx)
set iconPos to 1
repeat with mainCount from 1 to xx
set Xposition to SmallestX + ((iconPos - 1) * ColumnWidth)
set tempName to item mainCount of tempList
repeat with thisItem in thelist
if tempName = name of thisItem then
if we_are_on_desktop then
set desktop position of thisItem to {Xposition, SmallestY}
else
set position of thisItem to {Xposition, SmallestY}
end if
set iconPos to iconPos + 1
if iconPos > (((LargestX - SmallestX) / ColumnWidth) + 1) then
set iconPos to 1
set SmallestY to SmallestY + IconSpacing
end if
exit repeat
end if
end repeat
end repeat
end try
end tell
end SortbyAlphabet

to Qsort(array, leftEnd, rightEnd) -- Hoare's QuickSort Algorithm
script A
property L : array
end script
set {i, j} to {leftEnd, rightEnd}
set v to item ((leftEnd + rightEnd) div 2) of A's L -- pivot in the middle
repeat while (j > i)
repeat while (item i of A's L < v)
set i to i + 1
end repeat
repeat while (item j of A's L > v)
set j to j - 1
end repeat
if (not i > j) then
tell A's L to set {item i, item j} to {item j, item i} -- swap
set {i, j} to {i + 1, j - 1}
end if
end repeat
if (leftEnd < j) then Qsort(A's L, leftEnd, j)
if (rightEnd > i) then Qsort(A's L, i, rightEnd)
end Qsort

``````

(Edit) This was the bit that was modified

`````` set LargestX to last item of Xdifflist
set SmallestX to 10000
set LargestY to 0
set SmallestY to 10000
repeat with x from 1 to length of Xdifflist
if LargestX < item x of Xdifflist then
beep
set LargestX to item x of Xdifflist
end if
if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
end repeat

``````

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

This is really, really weird.

I’ve got 151 icons, arranged in a 12x12 grid, alphabetically, with an extra row of 7 across the bottom left.

If I re-sort alphabetically, using the script above, I get an error from the Hoare’s Qsort algorithm.

If I move any single icons of rows 1,2,3,4 or 6,7,8,9, or 11 or 12 of the far right column in just a fraction, I get no error.

If I move in icon 5 or 10, I still get an error in the sort. Repeatably.

Does this make any sense?

I’m heading to Europe on Wednesday, for 8 weeks hols, so someones got plenty of time to give me an answer. Anyone?

Bewilderdly yours, (an old fart in the sun)

Santa

(edit) I spread the icons out slightly, and now I’m getting errors (beeps) no matter what I do to the right column, or any of them.
I think there’s bad, bad gremlins hard at work in my processor, if I listen carefully I’m sure I can hear the little B*****ds hammering.
My icon arranging algorithim traps any errors, so it’s no big deal, just that things like this gnaw at my old, delicate nature

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

Hi, Brian.

The problem’s not with the sort routines. At the top of mainCycle(), you’ve intialised listofXY, Xdifflist, and ydiffList to empty strings, not to empty lists. Since you’re using concatenation to build up the lists, the first number that’s concatenated to each is coerced to string:

``````set Xdifflist to ""
set temp to {89, 40}

set Xdifflist to Xdifflist & item 1 of temp
--> "89"
``````

You coerce the result of that to list, so that thereafter, Xdifflist is a list and any further numbers will be coerced to list for concatenation to a list, rather than to string for concatenation to a string:

``````set Xdifflist to ""
set temp to {89, 40}

set Xdifflist to Xdifflist & item 1 of temp as list
--> {"89"}

set temp to {346, 40}
set Xdifflist to Xdifflist & item 1 of temp as list
--> {"89", 346}
``````

You’re thus sorting lists where one of the “numbers” is actually a string. It’s that which isn’t necessarily being sorted as you’d like. (The results of the number/numeric string comparisons within the sort depend on whether the number’s being compared with the string or the string with the number!)

So, you should initialise those three variables to empty lists instead:

``````set listofXY to {}
set Xdifflist to {}
seet ydiffList to {}
``````

It’s also more efficient to append items to lists, rather than concatenating them:

``````set end of Xdifflist to item 1 of temp
``````

The sort routines having been exonerated, any further problems with the script should properly be posted to the OS X forum.

Thank you very, very much Nigel.

It’s been driving me nuts, being a newbie.

A lesson well learnt.

Santa

Hey, glad to see this thread, it helped me a lot. I wrote my own version, using the “optimized pivot” method and got this code:

``````on quickSort(theList)
--public routine, called from your script
script bs
property alist : theList

on Qsort(leftIndex, rightIndex)
--private routine called by quickSort.
--do not call from your script!
if rightIndex > leftIndex then
set pivot to ((rightIndex - leftIndex) div 2) + leftIndex
set newPivot to Qpartition(leftIndex, rightIndex, pivot)
set theList to Qsort(leftIndex, newPivot - 1)
set theList to Qsort(newPivot + 1, rightIndex)
end if

end Qsort

on Qpartition(leftIndex, rightIndex, pivot)
--private routine called by quickSort.
--do not call from your script!
set pivotValue to item pivot of bs's alist
set temp to item pivot of bs's alist
set item pivot of bs's alist to item rightIndex of bs's alist
set item rightIndex of bs's alist to temp
set tempIndex to leftIndex
repeat with pointer from leftIndex to (rightIndex - 1)
if item pointer of bs's alist â‰¤ pivotValue then
set temp to item pointer of bs's alist
set item pointer of bs's alist to item tempIndex of bs's alist
set item tempIndex of bs's alist to temp
set tempIndex to tempIndex + 1
end if
end repeat
set temp to item rightIndex of bs's alist
set item rightIndex of bs's alist to item tempIndex of bs's alist
set item tempIndex of bs's alist to temp

return tempIndex
end Qpartition

end script

if length of bs's alist > 1 then bs's Qsort(1, length of bs's alist)
return bs's alist
end quickSort
``````

I’ve run it against Adam’s and Nigel’s versions and it performs in between the them. On my 450mhz iMac, Nigels took 2 seconds to sort 4000 numbers, Adam’s took 7 seconds (after I made Nigel’s fix for the “reference to”), and mine took 4. I was honestly surprised, as I figured the recursive nature of mine would hurt its performance, but it didn’t seem to.

The “optimized pivot” takes the pivot and actually puts it in the appropriate position before beginning to sort the sides.

Anyway, after I wrote mine, I went back and looked at Nigel’s and Adam’s and tweaked mine a bit to help it along. Moving my Qsort and Qpartition routines into the script object was a huge help!

The sharing of code is the single greatest advantage any of us have. I’m so glad we have MacScripter!