Of Scripts and Script Libraries and Sorting Algorithms

Ericnepean · November 19, 2023, 12:56am

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 · November 19, 2023, 5:33am

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 · November 19, 2023, 11:56am

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 · November 19, 2023, 9:27pm

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 · November 20, 2023, 5:50am

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 · November 20, 2023, 9:56am

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!

Fredrik71 · November 20, 2023, 11:00am

My conclusion after some benchmark of different sorting algorithm. (Other post of mine)
AppleScript vanilla version of some sorting algorithm could only compete with Objective-C approach if the list has less 300 items.

It was very clear to me when I did a tests based on how many item I could sort in 1 second.

It makes me to believe Objective-C method use multiply thread when AppleScript use single.
In other words like mordern Metal and Vulkan API vs OpenGL (1 thread per context).

robertfern · November 20, 2023, 12:30pm

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 · November 20, 2023, 7:23pm

Hi @Fredrik71.

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

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

Nigel_Garvey · November 20, 2023, 7:24pm

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 · November 20, 2023, 7:34pm

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)

Fredrik71 · November 20, 2023, 8:44pm

@Nigel_Garvey
Or maybe the reson to use AppleScript is to make it more difficult. You could make Objective-C framework of an sorting algorithm.

If you have problem to sleep tonight you could read this. haha
https://www.diva-portal.org/smash/get/diva2:839729/FULLTEXT02

Fredrik71 · November 21, 2023, 12:11am

@Nigel_Garvey
Here is example in Python to use merge sort algorithm that use 4 threads.
10.000 numbers in random order from 0 - 100.000 sorted on my machine in 10ms.

I used python 3.11 its 10 times faster and older versions.

#!/usr/bin/env python3

import threading
import time
import random

# number of elements in array
MAX = 10000

# number of threads
THREAD_MAX = 4

a = [0] * MAX
part = 0

# merge function for merging two parts
def merge(low, mid, high):
	left = a[low:mid+1]
	right = a[mid+1:high+1]
	
	# n1 is size of left part and n2 is size
	# of right part
	n1 = len(left)
	n2 = len(right)
	i = j = 0
	k = low
	
	# merge left and right in ascending order
	while i < n1 and j < n2:
		if left[i] <= right[j]:
			a[k] = left[i]
			i += 1
		else:
			a[k] = right[j]
			j += 1
		k += 1
		
	while i < n1:
		a[k] = left[i]
		i += 1
		k += 1
		
	while j < n2:
		a[k] = right[j]
		j += 1
		k += 1
		
# merge sort function
def merge_sort(low, high):
	if low < high:
		# calculating mid point of array
		mid = low + (high - low) // 2
		
		merge_sort(low, mid)
		merge_sort(mid + 1, high)
		
		# merging the two halves
		merge(low, mid, high)
		
# thread function for multi-threading
def merge_sort_threaded():
	global part
	
	# creating 4 threads
	for i in range(THREAD_MAX):
		t = threading.Thread(target=merge_sort, args=(part*(MAX//4), (part+1)*(MAX//4)-1))
		part += 1
		t.start()
		
	# joining all 4 threads
	for i in range(THREAD_MAX):
		t.join()
		
	# merging the final 4 parts
	merge(0, (MAX // 2 - 1) // 2, MAX // 2 - 1)
	merge(MAX // 2, MAX // 2 + (MAX - 1 - MAX // 2) // 2, MAX - 1)
	merge(0, (MAX - 1) // 2, MAX - 1)
	
# Driver Code
if __name__ == '__main__':
	# generating random values in array
	for i in range(MAX):
		a[i] = random.randint(0, 100000)
		
	# t1 and t2 for calculating time for
	# merge sort
	t1 = time.perf_counter()
	
	merge_sort_threaded()
	
	t2 = time.perf_counter()
	
	print("Sorted array:", a)
	print(f"Time taken: {t2 - t1:.6f} seconds")