QUicksort für Listen in Applescript

[fyysh]

Hi, ich bin grad über ein interessantes Script gestoßen und wollte das mit euch sharen.

Es geht darum: Musstet ihr schon mal eine Liste in Applescript sortieren und habt dann enttäuscht festgestellt: "möööh das geht ja gar nicht" (per default).

Nun, entweder man besorgt sich ne Scripting Addition, die das für einen erledigt oder man macht es anders, z.B. so:

1. Erstell ein Script mit folgendem Inhalt und speichere es entweder unter "~/Library/Scripts" oder unter "/Library/Scripts" mit dem Namen "QuickSortList.scpt" (Quelle):

--originally posted by kevin bradley on http://macscripter.net/viewtopic.php?id=24766
on run (theList)
	quickSort(theList)
end run


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

Das ist ein Quicksort-Algorithmus , freundlicherweise von Kevin Bradley auf MacScripter.net veröffentlicht (danke Kevin - muss man schon mal nicht selber schreiben )


Jetzt stellen stellt euch vor ihr hättet ein Script in dem ihr eine Liste sortieren müsst. Das geht jetzt ganz einfach. Hier ein Beispielscript, welches eine Liste mit 10 Items aus random Nummern zw. 1 und 100 erstellt und diese Liste dann sortiert. Am Schluss gibt es ein Alert aus, in dem man oben die sortierte Liste und unten die ursprüngliche Liste sieht:

--falls das script in ~/Library/Scripts gespeichert ist:
set qsScript to (((path to scripts folder) & "QuickSortList.scpt") as string) as alias
--sollte das script in Library/Scripts gespeichert sein, kommentiere die vorherige zeile und unkommentiere die nächste
--set qsScript to (((path to scripts folder from local domain) & "QuickSortList.scpt") as string) as alias


--generieren der liste, die sortiert werden soll
set myList to {}
repeat until (count of myList) = 10
	set rndNumber to random number from 1 to 100
	if not (myList contains rndNumber) then
		set myList to myList & rndNumber
	end if
end repeat

--sortieren der liste mit dem externen script
set resultList to (run script qsScript with parameters myList)


--alert dialog strings generieren
set ATD to AppleScript's text item delimiters
set AppleScript's text item delimiters to ","
set myListString to myList as text
set resultListString to resultList as text
set AppleScript's text item delimiters to ATD

display alert "resultList:" & return & resultListString message "myList:" & return & myListString as warning -- ;)

Da kommt dann sowas raus:

Nice, oder? Jetzt braucht man sich eigentlich nur noch die ersten Zeilen merken (kommt drauf an, wo man das Script hingelegt hat) und wie man das Script aufruft und schon bekommt man effizient und effektiv sortierte Listen. Quicksort ist nämlich, wie der Name schon sagt, recht fix.

Wenn man sein Script als Bundle speichert, könnte man das Script theoretisch auch in das Bundle mit reinlegen und von da aus zugreifen. Dann wäre es sogar portabel.


Ich hoffe der Tipp ist jemandem von Nutzen.

Greetz
fyysh