Re: how to sort a list
Re: how to sort a list
- Subject: Re: how to sort a list
- From: Graff <email@hidden>
- Date: Fri, 14 May 2004 14:32:20 -0400
On May 14, 2004, at 6:27 AM, Emmanuel wrote:
At 9:09 PM -0400 13/05/04, Graff wrote:
If you have really large lists (on the order of thousands of items)
then you might want to do a shell or quick sort. I have those
implemented in AppleScript so let me know if you need them. Honestly
though, if you are sorting more than a few thousand items with
AppleScript then you might want to look at going to another language
such as C or Java or the like.
A bit confusing for me: what you call the "shell sort" is written in
C, isn't it? What good would there be to write [yet] another "sort" in
C?
Emmanuel
You can write a shell sort in just about any language, shell sort is a
type of sort just as are bubble sort, insertion sort, merge sort, quick
sort, etc.
Here is a description of a shell sort:
<
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/
shellen.htm>
Here is a quick shell sort implemented in AppleScript, based on the
algorithm on that site:
---------
on shellsort(a)
set n to length of a
set cols to {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
1968, 861, 336, 112, 48, 21, 7, 3, 1}
repeat with h in cols
if (h <= (n - 1)) then
repeat with i from h to (n - 1)
set v to item (i + 1) of a
set j to i
repeat while (j >= h) and ((item (j - h + 1) of a) > v)
set (item (j + 1) of a) to (item (j - h + 1) of a)
set j to j - h
end repeat
set item (j + 1) of a to v
end repeat
end if
end repeat
return a
end shellsort
set theList to {}
repeat 100 times
copy (random number 100) to end of theList
end repeat
shellsort(theList)
---------
The reason I would say someone should do large sorts in a language
other than AppleScript is that AppleScript is not exactly the quickest
or most optimizable language. Don't get me wrong, it's amazing just
how well you can get AppleScript to run if you know some tricks.
However, with C you can get very close to optimal machine code and
properly tweaked C code can run orders of magnitude faster than
AppleScript. For a couple of hundred elements or so you might not see
much of a difference but try sorting a few hundred thousand or a couple
of million elements and you will see C's true strengths.
- Ken
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.