Of Scripts and Script Libraries and Sorting Algorithms

[Ericnepean]

Over the years Nigel Garvey and others have published some scripts with very fast and sophisticated sorting algorithms.
Over the last few years I’ve had several tries at incorporating his 2010 combined QuickSort+InsertionSort script into my other works but have previously had to give it up due strange behaviour and lack of debugging time.
Now that I am retired and have more time and focus, I have identified the issue.

In 2015 I started using a script library which I implemented as follows:

use U : script “Utilities_1501.scpt”

The script that I copied from Nigel Garvey has a “qsort()” handler (of course), within that handler there is a Script “o”, and within that script several handlers that use the variable “u” and assign various things to it.

 on qsort(theList, l, r) 	script o
 		property cutoff : 10 -- The Quicksort will ignore ranges containing this number of items or fewer.
 		property lst : theList
 		
		on qsrt(l, r) -- The Quicksort handler.
 			set pivot to my lst's item ((l + r) div 2)
 			
 			set i to l
 			set j to r
 			repeat until (i > j)
 				set u to my lst's item i   
-----               ^ here is the problem

Once qsort() has run, the handlers in the Utilities Library script aren’t accessible any more, and for example executing U’s GetTick_Now() results in the bizarre error message:
“5298 doesn’t understand GetTick_Now()”

On careful reading, it seems that this use of use statement creates a property

The fix is simple, a “local U” statement at the beginning of qsort() - I took it two steps further.

 on qsort(theList, l, r)
 	local M, C, G, l, P, U -- hide my Script Library Designators from qsort()
 	local cutoff, lst -- hide script o's properties from outside
	
	script o
 		property cutoff : 10 -- The Quicksort will ignore ranges containing this number of items or fewer.
 		property lst : theList
 		
		on qsrt(l, r) -- The Quicksort handler.
 			local pivot, i, j, u, w --protect the local variables
 			set pivot to my lst's item ((l + r) div 2)

[Ericnepean]

I probably should have all of the documentation. If I had followed Nigel’s advice below the problem would have never occured.

– Say you’ve decided to use qsort and it’s in a folder called “Sorts” in your user “Scripts” folder.

set sorter to (load script file ((path to scripts folder as text) & "Sorts:qsort.scpt"))
tell sorter to sort(myList, 1, -1) -- ie. sort items 1 thru -1 of myList.

[Nigel_Garvey]

Hi @Ericnepean.

Thanks for your interest in Arthur’s and my Quicksort. I’m glad you were able to work out the cures for the problem you were having by yourself. Nowadays, of course, it’s possible to load the script with the “Libraries” system and a use command in the same way as you load your “Utilities_1501.scpt”, but I still use load script myself occasionally. By the way, the “.scpt” suffix can be omitted from the script name in a use line.

The link to ScriptBuilders in the 2010 addendum to my 2006 post is, as you may already have discovered, no longer valid. ScriptBuilders was a sister site to MacScripter where one could upload actual working files instead of just posting source code as here in Code Exchange. But literally two weeks after I uploaded my sort scripts to it, MacScripter’s then owner discontinued it and the scripts ended up (without my foreknowledge or permission) on some third-party software download site — of which I’ve long since lost track!

[Ericnepean]

Hi Nigel
I belive that after Scriptbuilder went offline, you did update your Macscripters Quicksort post; I got that and I was also lucky enough to download and keep your “Dose of Sorts” compendium before it vanished.

Regarding the third-party software site with your stuff from ScriptBuilders, even Google can’t find that site, which I think is the modern day version of oblivion. Serves them right.

[robertfern]

Is your qsort routine recursive. If so it will run into a recursion limit at around 510, so it would have problems with large lists.
I have a version that doesn’t use recursion and can handle lists of any size.

[Nigel_Garvey]

Hi Robert.

The version referred to above is indeed recursive, but leaves out the deepest few recursion levels, finishing off instead with an insertion sort of the entire sort range. An alternative, which may be slightly faster, is to do individual insertion sorts of the ranges for which recursion isn’t performed. Another alternative is to use recursion only on one of the two partitions at each level (preferably the shorter) and simply to repeat with changed range values for the other.

Quicksort’s recursion doesn’t go straight down, of course. It’s a “divide and conquer” algorithm, so recursion only covers part of the sort range at any one time. There’s a lot of to-ing and fro-ing between levels, but the depth of the deepest level isn’t necessarily as great as one might suppose. I’ve tested all my sorts with lists containing many thousands of items and none of the fully recursive ones have ever hit a recursion limit. The main sticking point has been generating such huge lists in the first place!

But please post your version here in Code Exchange if you think it’s any good. I’d be interested to see it if it’s both in-place and a fully iterative Quicksort as I was never able to produce such a thing myself!

[robertfern]

Here it is…

on quickSort for blist -- Non-Recursive FASTEST
	local px, stack, lo, hi, L, H, sw -- px means 'Pivot Index'
	script mL
		property alist : blist
		property stack : {{1, count blist}}
	end script
	repeat until (count mL's stack) = 0
		set lo to item 1 of item 1 of mL's stack
		set hi to item 2 of item 1 of mL's stack
		set px to item ((hi + lo) div 2) of mL's alist -- start partitionHoare
		set L to lo
		set H to hi
		repeat
			repeat while item L of mL's alist < px
				set L to L + 1
			end repeat
			repeat while item H of mL's alist > px
				set H to H - 1
			end repeat
			if L ≥ H then exit repeat
			set sw to item L of mL's alist
			set item L of mL's alist to item H of mL's alist
			set item H of mL's alist to sw
			set L to L + 1
			set H to H - 1
		end repeat
		set px to H -- end of partitionHoare
		set mL's stack to rest of mL's stack --items 2 thru -1 of stack
		if px + 1 < hi then set beginning of mL's stack to {px + 1, hi}
		if lo < px then set beginning of mL's stack to {lo, px}
	end repeat
end quickSort

[Nigel_Garvey]

@Fredrik71

AppleScript vanilla version of some sorting algorithm could only compete with Objective-C approach if the list has less 300 items.

Hi @Fredrik71.

For speed maybe, yes. The main reasons for using an AppleScript sort nowadays would be:

1. You need an in-place sort.
2. You need a customised sort that can’t be done with ASObjC.
3. You just find the algorithm fascinating.

[Nigel_Garvey]

@robertfern

Here it is…

Hi @robertfern.

Yes. That’s certainly an in-place iterative Quicksort! — although it’s arguably recursive by proxy, since it implements its own LIFO stack to store range indices instead of using the program stack. It’s not as fast as the Quicksort to which Ericnepean linked above, probably because of the building and breaking up of the stack and the fact it doesn’t have the insertion sort optimisation. But since your purpose is mainly to avoid any possible recursion limit, that’s probably not important to you.

[robertfern]

You are correct, SIR! ( to be read in the voice of Ed McMahon)

I also have a version that will sort a list of lists where you send it a sort list parameter that contains the item indexes to sort on and also add a minus sign to the ones you want sorted in reverse order. (I.e. descending)