QuickSort Algorithm

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.:stuck_out_tongue:

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

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 :slight_smile:

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, :cool: (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 :smiley:

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! :slight_smile:

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! :slight_smile:

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! :cool:

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! :wink: Thank you very much for making me understand Applescript + programming more and more :slight_smile:

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 :frowning:

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 :frowning: ) 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!?!? :confused:

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 :wink:

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… :slight_smile: (** 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?! :smiley: (** 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! :smiley:
*
** 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

The quicksort algorithm really isn’t just a search engine, it is making comparisons.

You don’t say what you want to search either… is it an ordered list of the same datatype?

I wonder if Jens is thinking of a binary search, which is distantly related to QuickSort in that it’s a “divide and conquer” process. In AppleScript, you use ‘is in’ to determine which half of the list the item’s in, then which half of that half, and so on. It can be faster than checking each item from the beginning of the list, but not by very much. And (if I remember correctly) it depends on the length of the list and where the item actually is in it. An item near the beginning might be found more quickly by a linear search. And of course a binary search can use a lot of memory generating the half lists for checking.

on binarySearch(theList, value)
	script o
		property lst : theList
	end script
	
	set valueAsList to {value}
	set l to 1
	set r to (count theList)
	
	if (valueAsList is in theList) then
		repeat until (value is item l of o's lst)
			set l to l + 1
			set m to (l + r) div 2
			if (valueAsList is in items l thru m of o's lst) then
				set r to m - 1
			else
				set l to m + 1
			end if
		end repeat
		return l
	else
		return 0
	end if
end binarySearch

Any speed advantage comes from the fact that ‘is in’ loops through the list(s) and compares the items by means of its underlying C code, which is faster than the equivalent instructions at the AppleScript level. It has to be sufficiently faster here that, even when it’s done several times, and with all the other AppleScript commands involved, it’s still faster than looping through the list and comparing the items with AppleScript.