Submit Hint Search The Forums LinksStatsPollsHeadlinesRSS
14,000 hints and counting!


Click here to return to the 'Sort lists in AppleScript using the Unix sort command' hint
The following comments are owned by whoever posted them. This site is not responsible for what they say.
Sort lists in AppleScript using the Unix sort command
Authored by: DougAdams on May 17, '04 03:16:04PM
Bubblesort is a good ol' good one, but it is intolerably slow. Compare the original post's UNIX handler and the BubbleSort handler using this as your list:
tell application "iTunes" to set the_list to (get name of every file track of library playlist 1)
It's no contest.

[ Reply to This | # ]
Sort lists in AppleScript using the Unix sort command
Authored by: jonn8n on May 17, '04 07:45:32PM
While the bubble sort routine is not the speediest, there are other vanilla AppleScript methods for sorting that are much faster and have the added benefit of keeping the data as the native data types without coercing to strings. For instance, here is a comparison using the shell sort example with the quick sort method developed by a few very accomplished AppleScripters (I'm not sure who at this point: HAS? AK? NG?)

Jon


tell application "iTunes" to set the_list to (get name of file tracks of library playlist 1)

set start_time_1 to (current date)
set sorted_list to my shell_sort(the_list)
set end_time_1 to ((current date) - start_time_1)

set start_time_2 to (current date)
my quick_sort(the_list, 1, the_list's length)
set end_time_2 to ((current date) - start_time_2)

return {end_time_1, end_time_2}

on shell_sort(the_list)
	set new_delim to {ASCII character 10}
	tell (a reference to my text item delimiters)
		set {old_delim, contents} to {contents, new_delim}
		set {the_list, contents} to {"" & the_list, old_delim}
	end tell
	return paragraphs of (do shell script "echo " & quoted form of the_list & " | sort -f")
end shell_sort

on quick_sort(a, l, r)
	--this sorts the list in place, no need to return anything
	local i, j, v
	script o
		property p : a
	end script
	set {i, j} to {l, r}
	set v to o's p's item ((l + r) div 2)
	repeat while (j > i)
		repeat while (o's p's item i < v)
			set i to i + 1
		end repeat
		repeat while (o's p's item j > v)
			set j to j - 1
		end repeat
		if (not i > j) then
			set o_s_p_s_item_i to o's p's item i
			set o's p's item i to o's p's item j
			set o's p's item j to o_s_p_s_item_i
			set {i, j} to {i + 1, j - 1}
		end if
	end repeat
	if (l < j) then quick_sort(o's p, l, j)
	if (r > i) then quick_sort(o's p, i, r)
end quick_sort


[ Reply to This | # ]
Sort lists in AppleScript using the Unix sort command
Authored by: Graff on May 17, '04 09:36:55PM

Sure, bubblesort is slow for a large number of items. That's why I said that I have a bunch of different types of sorts programmed in AppleScript. If I want to sort a large list I'd use a quicksort or a heapsort, they are O(nlogn) - much faster than bubblesort which is O(n^2). If I really needed efficient sorting I would combine a quicksort and an insertion sort (for when the quicksort partition is 10 elements or less). However, if I'm sorting a ton of elements and time is a factor then AppleScript is the wrong tool in the first place...

Bubblesort is just fine for sorting lists of a few hundred items. It is small and easily understood and doesn't clutter up a script too much. For most AppleScript tasks it is perfect.



[ Reply to This | # ]