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.
- Get the names of the files/folders.
- Pad out any numerics in the names to a fixed width with leading zeros.
- 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
on padNumericsWithZeros(originalNames)
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
set padWidth to (count theZeros)
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
set pad to padWidth + i - j
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
set pad to padWidth + i - j - 1
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)
end padNumericsWithZeros
tell application "Finder" to set theSelection to the selection
set astid to AppleScript's text item delimiters
set selectionNames to getItemNames(theSelection)
set doctoredNames to padNumericsWithZeros(selectionNames)
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.
G’day Adam
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
-- Start with a Y seed position, to overcome
-- 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.
Enjoy your holiday!
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!
Hi, Kevin.
That “optimized pivot” idea looks very interesting. Thanks for posting it. I’m going to have a happy couple of days trying to analyse it to see if Arthur’s and my effort can benefit from it!
Meanwhile, I’ve taken the liberty of applying a couple of optimisations to your Qpartition() handler. Basically, they use existing variable values to reduce the number of times the list is accessed. There’s also an exploitation of an AppleScript quirk whereby “simple” comparisons are faster than “compound” ones. It’s faster to do this .
if a > b then
else
-- Do something.
end if
. than this:
if a ≤ b then
-- Do something.
end if
Similarly with ≥ and not. It’s faster to test their antitheses than to test them. The difference is minimal, but every little helps in a large sort!
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 -- We already have this as pivotValue.
set item pivot of bs's alist to item rightIndex of bs's alist
--set item rightIndex of bs's alist to temp -- No need to put it back in the list.
set tempIndex to leftIndex
repeat with pointer from leftIndex to (rightIndex - 1)
set temp to item pointer of bs's alist -- temp set here to save getting the item twice.
if temp > pivotValue then --≤ pivotValue then
else
--set temp to item pointer of bs's alist -- Moved up.
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 -- Already in pivotValue.
set item rightIndex of bs's alist to item tempIndex of bs's alist
set item tempIndex of bs's alist to pivotValue --temp
return tempIndex
end Qpartition
Funny you should mention. As I was writing this (and the other sorts - bubble, insertion, and merge) I found myself wondering if there was a difference, but I didn’t code it up to see if there was.
Thanks Nigel!
Hey everybody
as I’m not the perfect scripter as you guys, I’m having a hard time to transform the qsort routine into a qsort the would match my needs.
I’ve been using Kevins’s pivot version at the moment - and was also unsuccesfully trying to implement Nigel’s superfast version (I’m working in a tell application routine and I couldn’t call Nigel’s routine through that)
What I actually want to achieve is removing the duplicates, while sorting the list.
As I didn’t get that done, for the moment, I’m rearranging the sorted list like that:
set srtLst to my quickSort(Lst)
set lgthsrtLst to srtLst's length
set Lst to {}
repeat with x1 from 1 to lgthsrtLst
set TmpItm to item x1 of srtLst
if x1 < (lgthsrtLst) then
if TmpItm = item (x1 + 1) of srtLst then
else
set Lst to Lst & TmpItm
end if
end if
if x1 = (lgthsrtLst) then set Lst to Lst & TmpItm
end repeat
It would probably be much faster, if I’d erase the duplicates directly in the qsort handler.
could you give me a hint on how to get that done?
Thank you so very much!
And most important thank you so much for posting your wisdom in general!!
ekel75
PS. do you know which is faster, using a variable for 3 to 4 instances in a script
set lgthCalcNum to CalcNum's length
if (lgthCalcNum) > 6 then set CalcNum to (text 1 thru ((lgthCalcNum) - 6) of CalcNum) & "." & text ((lgthCalcNum) - 5) thru (lgthCalcNum) of CalcNum
or not!? ( like this )
if (CalcNum's length) > 6 then set CalcNum to (text 1 thru ((CalcNum's length) - 6) of CalcNum) & "." & text ((CalcNum's length) - 5) thru (CalcNum's length) of CalcNum
Model: Desktop G4 800MHz
AppleScript: AppleScript D1-1.9.3
Browser: Firefox 1.5.0.7
Operating System: Mac OS X (10.4)
Hi, ekel75.
I don’t think that combining a sort with removing the duplicates would actually be faster. Sorts do a large number of item comparisons “ often a very large number. The comparisons check if one item is greater or less than another. It would greatly increase the workload if each stage of the sort also included a check to see if the items were equal, and making a new list every time a duplicate was found would increase it even more. There may be an effective way to reduce the slow-down, but I can’t see it.
Your process of sorting the list first and then building another without the duplicates is probably the best way. I’d code it something like this:
-- A script object for speed of access to the lists.
script o
property sortedList : missing value
property prunedList : missing value
end script
-- Do the sort.
set o's sortedList to quickSort(myList)
-- Since the list has been sorted, equal values will be together, not randomly distributed.
-- Initialise a check value to the first item in the sortedList
set checkValue to item 1 of o's sortedList
-- Start off the pruned list with that value.
set o's prunedList to {checkValue}
repeat with i from 2 to (count o's sortedList)
set thisValue to item i of o's sortedList
if (thisValue is checkValue) then
-- If this value's a duplicate, skip it.
else
-- Otherwise, we've reached (a possible run of) a new value.
-- Append this value to the pruned list and make it the new check value.
set end of o's prunedList to thisValue
set checkValue to thisValue
end if
end repeat
set myList to o's prunedList
Another way, if the items in the list are all of the same class and you know when you write the script what that will be, is this:
-- A script object for speed of access to the list.
script o
property sortedList : missing value
end script
-- Do the sort.
set o's sortedList to quickSort(myList)
-- Since the list has been sorted, equal values will be together, not randomly distributed.
-- Initialise a check value to the first item in the sortedList
set checkValue to item 1 of o's sortedList
repeat with i from 2 to (count o's sortedList)
set thisValue to item i of o's sortedList
if (thisValue is checkValue) then
-- If this value's a duplicate, replace it with 'missing value'
set item i of o's sortedList to missing value
else
-- Otherwise, we've reached (a possible run of) a new value.
-- Make it the new check value.
set checkValue to thisValue
end if
end repeat
-- Assuming that this is a list of integers, return the integers (not the 'missing values').
set myList to o's sortedList's integers
I’ve just seen the addendum to your post. The version with the variable should be slightly faster, but the difference will be miniscule with just those two lines. Basically, retrieving a value from a variable is faster than calling a function or using a reference to work it out again.
Dear Nigel,
thank you very much for your quick response and all your effort!
I like your routine very much. My approach has the same basic principle but your’s just got that neatly programmed twist to it.
Simply pro! Thank you very much for making me understand Applescript + programming more and more
So now I’m trying to implement your second version, since it’s all the same class.
I tried it with an empty script and worked like a charm.
Trying to implement it doesn’t work too well though
I’m in a < tell application > routine, and some of the stuff from Applescript has to be handled differently from within < tell application, >
which I haven’t fully figured out yet. (Which is why I’m not using your quicksort ) Calling subroutines works fine though,
so I tried to put your script into a new handler and calling it up like that:
tell application "Adobe InDesign CS2"
activate
tell document 1
...
set Lst to my pruneList(Lst)
...
end tell
end tell
--
--Subroutines
on quickSort(theLst)
...
end quickSort
on pruneList(thePruneLst)
script o
property sortedList : missing value
end script
set o's sortedList to my quickSort(thePruneLst)
-- Initialise a check value to the first item in the sortedList
set checkValue to item 1 of o's sortedList
repeat with i from 2 to (count o's sortedList)
set thisValue to item i of o's sortedList
if (thisValue is checkValue) then
-- If this value's a duplicate, replace it with 'missing value'
set item i of o's sortedList to missing value
else
-- Otherwise, we've reached (a possible run of) a new value.
-- Make it the new check value.
set checkValue to thisValue
end if
end repeat
return o's sortedList's text
end pruneList
But somehow I’m not getting it right. Am I not allowed to call the quickSort handle from within a second handler ?
Are some values not transported right!?!?
thank you very much for your help!
ekel75
–
– FOUND IT !?!
I guess I found it myself, though I still don’t get why it worked before!
the list “Lst” is not actual text but a reference to text within an Indesign Document…
it looks like this
{text from character 1 to character 7 of cell id 0 of table id 853847 of cell id 26 of table id 853696 of cell id 2 of table id 853446 of text frame id 852504 of page id 852502 of spread id 852497 of document “testdoc.indd” of application “Adobe InDesign CS2”, …}
so I included this:
set Lst to (search with find attributes {applied character style:CharStyle})
repeat with x from 1 to (count of Lst)
set item x of Lst to item x of Lst as text
end repeat
set Lst to my pruneList(Lst)
what do you think? you probably have some slick coded idea up your sleeve right as you’re reading this
greetz e/
Hi, ekel75.
I’m afraid I don’t have InDesign and am not familiar with scripting it. But it looks as though what you’re doing is the way to do it: get the references, coerce to text, sort, prune. (The pruning method relies on the fact that the texts are sorted.) If Lst contains a large number of items, a script object might speed up the coercion loop a little too:
script o
property Lst : missing value
end script
set o's Lst to (search with find attributes {applied character style:CharStyle})
repeat with x from 1 to (count o's Lst)
set item x of o's Lst to item x of o's Lst as text
end repeat
set theList to my quickSort(o's Lst)
set theList to my pruneList(theList)
Hey Nigel,
thank you very much for your reply! Just found it after posting my last question… (** edit: deleted my last post**)
I changed the script in that way… every bit of a second counts with large lists!
- your quicksort is a perfect example (still can’t call it from within the main script :()
my prune script is now calling the quicksort so I only call prunelist from the mainscript.
(cause I can’t prune without sorting first anyway)
… do you have a hint for my last question?! (** edit: deleted my last post**)
helplessy yours,
ekel75
** edit
*
@Nigel:
I just noticed that your CustomQSort works as a handler, with which I’m not having problems calling from my main script!
So hoooooray! All my sort problems are gone again! Thank you sooo much!
Happy me!
*
** end of edit
*
This algorithm and its implementation is very nice !
I am using it often, but unfortunately I am not clever enough (okay, maybe too lazy …) to understand its structure.
It should be very easy to use this algorithm as a searching routine as well. As I understood the QuickSort algortihm, it is more less nothing other like a searching routine, or it should be quite easy to modify it for this use.
Is there anybody able and so kind to tell me how to use this QuickSort Algorith as a searching routine, i.e. searching for an item, giving out the (one and only, or first) index containig it ?
Best Regards
Jens