Wrote this quick sort routine in AppleScript. Works ok, but only for very small lists? So 6 elements is ok, but 7 bombs with a stack overflow…
Is the stack in AppleScript really so small. Anybody know how I can find out its real size? or indeed change it maybe?
set theList to {1, 2, 7, 4, 1, 9, 2, 3}
set theLast to count (theList)
set theFirst to 1
set theSort to sort(theList, theFirst, theLast)
on sort(theList, theLeft, theRight)
set i to 1
set j to (count theList)
--display dialog "left " & i & " right " & j
set v to item ((theLeft + theRight) div 2) of theList -- pivot
--display dialog "the v " & v
repeat while (j > i)
repeat while (item i of theList < v)
set i to i + 1
end repeat
repeat while (item j of theList > v)
set j to j - 1
end repeat
if (not i > j) then
tell theList to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (theLeft < j) then sort(theList, theLeft, j)
if (theRight > i) then sort(theList, i, theRight)
end sort
Model: MacBook Pro
AppleScript: AppleScript 2.2.1
Browser: Safari 534.55.3
Operating System: Mac OS X (10.7)
on quickSort(theList, theLeft, theRight)
set i to theLeft
set j to theRight
set v to item ((theLeft + theRight) div 2) of theList -- pivot
repeat while (j > i)
repeat while (item i of theList < v)
set i to i + 1
end repeat
repeat while (item j of theList > v)
set j to j - 1
end repeat
if (not i > j) then
tell theList to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (theLeft < j) then quickSort(theList, theLeft, j)
if (theRight > i) then quickSort(theList, i, theRight)
end quickSort
I customized this quicksort handler, just a tad, to sort on a chosen item in a sublist. the sublists are of course not ragged!
set ml to {{1, "Pettersen"}, {9, "Olavsen"}, {3, "Davidsen"}}
quickSortL(ml, 1, 3, 2)
log ml
on quickSortL(theList, theLeft, theRight, itemNo)
set i to theLeft
set j to theRight
set v to item itemNo of item ((theLeft + theRight) div 2) of theList -- pivot
repeat while (j > i)
repeat while (item itemNo of item i of theList < v)
set i to i + 1
end repeat
repeat while (item itemNo of item j of theList > v)
set j to j - 1
end repeat
if (not i > j) then
tell theList to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (theLeft < j) then quickSortL(theList, theLeft, j, itemNo)
if (theRight > i) then quickSortL(theList, i, theRight, itemNo)
end quickSortL
It’s possible to write customisable sorts which take “plug-in” customisations. They’re not quite as fast as fully custom-written ones, but they do save having to write full custom sorts for every contingency. You only have to write script objects containing the required comparison processes:
set ml to {{1, "Pettersen"}, {9, "Olavsen"}, {3, "Davidsen"}}
script sortListsByItemI -- Script object which compares items with the same index in two lists.
property i : missing value
on isGreater(a, b)
(a's item i > b's item i)
end isGreater
end script
set sortListsByItemI's i to 2 -- Customise the customiser (!) to compare item 2 of each list.
CustomQuicksort(ml, 1, 3, sortListsByItemI)
log ml
on CustomQuicksort(theList, theLeft, theRight, CustomObj)
set i to theLeft
set j to theRight
set v to item ((theLeft + theRight) div 2) of theList -- pivot
repeat while (j > i)
repeat while CustomObj's isGreater(v, item i of theList)
set i to i + 1
end repeat
repeat while CustomObj's isGreater(item j of theList, v)
set j to j - 1
end repeat
if (not i > j) then
tell theList to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (theLeft < j) then CustomQuicksort(theList, theLeft, j, CustomObj)
if (theRight > i) then CustomQuicksort(theList, i, theRight, CustomObj)
end CustomQuicksort
Since the demise of this site’s ScriptBuilders section, my own collection of sort handlers has wound up here. (Which reminds me, I must update it with my recently written ternary merge sorts!)
I just didn’t see that way to do it, last night, I just wanted something simple, a comparator object was on my list, but I have seen your handlers, which is something I want to use when I need the speed they give. But honestly, they seem abit complex to implement, that is why I tinkered this one in the first place! Sheer laziness!
As for scriptbuilders, I guess the wayback machine works, I use it, when there are links at apple, that have disappeared, like the guidebook, and such! It is very cool if you haven’t used it, you can click on links, and at least on some links, it works like the links was here today
The other factor is, that I am looking for a uniform way to tell handlers to work on an item in a sublist, or the sublist itself. (I guess I won’t be able to generalize that fully anyway, maybe I’ll end up with a combination of item numbers specified, or a swap handler, togetether with the comparator, in order to avoid to much overhead in the handlers)
Thinking of specifying an itemno of 0 to treat simple lists. There is no problem of doing that towards the comparator object. Which is easier than doing it in, for instance the quicksort routine, but what to do with those cases where there are needed more than swapping of sublists, or returning of sublist items, like swapping items between sublists by the handler, that I haven’t figured out yet. But I guess it can be easily dealt with in a swapper handler, in those cases.
An interesting link. Thanks. It didn’t get Scriptbuilders in the short time between the upload of my sorts and the appearance of the “Under Construction” placeholder, but it’s one to remember for possible future use.
On my HD, Nigel, your “A Dose of Sorts” folder weighs in at about 842KB. If you use Dropbox and have headroom in your 2GB free allowance, you could share that from Dropbox.
I don’t think you need that link that much, but for the newer of us; when getting to links that doesn’t exist anymore .It is sent from heaven! I recently wanted to get back to the code in the “GuideBook” at Apple, and it worked like a charm!
I just didn’t see that way to do it, last night, I just wanted something simple, a comparator object was on my list, but I have seen your handlers, which is something I want to use when I need the speed they give. But honestly, they seem abit complex to implement, that is why I tinkered this one in the first place! Sheer laziness! 