QuickSort Algorithm

Hi, Adam.

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

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

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

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.

Could someone please help out a newbie.

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.

Can anyone help please?

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

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