Re: Sort a List with Integers & Letters
Re: Sort a List with Integers & Letters
- Subject: Re: Sort a List with Integers & Letters
- From: Bill Hernandez <email@hidden>
- Date: Mon, 9 Apr 2007 00:06:17 +0000
On Apr 3, 2007, at 7:33 PM, Nigel Garvey wrote:
Nigel,
I ran some tests on your mergesort and was surprised by the huge
difference in times...
(*
ran the comparisons for 500, and 1000 items in the random list
mergesort(aList, 1, -1) --> (for 500 -> 0.132 seconds), (for 1000 -
> 0.303 seconds)
sort_QSort(aList, 1, -1) --> (for 500 -> 0.899 seconds), (for 1000 -
> 2.629 seconds)
sort_ASCII_Sort(aList) --> (for 500 -> 34.793 seconds), (for 1000 ->
245.098 seconds)
*)
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on mergesort(theList, l, r)
script o
property lst : theList
property extract : missing value
on msort(l, r)
set m1 to (l + r) div 2
set m2 to m1 + 1
if (m1 - l > 1) then
msort(l, m1)
else
set leftVal to item l of my lst
set rightVal to item m1 of my lst
if (rightVal < leftVal) then
set item l of my lst to rightVal
set item m1 of my lst to leftVal
end if
end if
if (r - m2 > 1) then
msort(m2, r)
else if (r > m2) then
set leftVal to item m2 of my lst
set rightVal to item r of my lst
if (rightVal < leftVal) then
set item m2 of my lst to rightVal
set item r of my lst to leftVal
end if
end if
set my extract to items l thru r of my lst
set leftIdx to 1
set leftLen to m2 - l
set rightIdx to leftLen + 1
set extractLen to r - l + 1
set leftVal to beginning of my extract
set rightVal to item rightIdx of my extract
repeat with i from l to r
if (rightVal < leftVal) then
set item i of my lst to rightVal
if (rightIdx < extractLen) then
set rightIdx to rightIdx + 1
set rightVal to item rightIdx of my extract
else
repeat with i from (i + 1) to r
set item i of my lst to item leftIdx of my extract
set leftIdx to leftIdx + 1
end repeat
exit repeat
end if
else
set item i of my lst to leftVal
if (leftIdx < leftLen) then
set leftIdx to leftIdx + 1
set leftVal to item leftIdx of my extract
else
exit repeat
end if
end if
end repeat
end msort
end script
set listLen to (count theList)
if (listLen > 1) then
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
else
if (l > r) then
set temp to l
set l to r
set r to temp
end if
o's msort(l, r)
end if
end if
return -- nothing
end mergesort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on sort_ASCII_Sort(my_list)
set the index_list to {}
set the sorted_list to {}
set counter to 0
--=counter
repeat (the number of items of my_list) times
set counter to counter + 1
set the low_item to ""
repeat with i from 1 to (number of items of my_list)
if i is not in the index_list then
set this_item to item i of my_list as text
if the low_item is "" then
set the low_item to this_item
set the low_item_index to i
else if this_item comes before the low_item then
set the low_item to this_item
set the low_item_index to i
end if
end if
end repeat
set the end of sorted_list to the low_item
set the end of the index_list to the low_item_index
end repeat
return the sorted_list
end sort_ASCII_Sort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on sort_QSort(aArray, start_val, no_of_elements)
if (no_of_elements = -1) then
set no_of_elements to count of aArray
end if
set i to start_val
set j to no_of_elements
set v to item ((start_val + no_of_elements) div 2) of aArray -- pivot
repeat while (j > i)
repeat while (item i of aArray < v)
set i to i + 1
end repeat
repeat while (item j of aArray > v)
set j to j - 1
end repeat
if (not i > j) then
tell aArray to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (start_val < j) then set aArray to sort_QSort(aArray, start_val, j)
if (no_of_elements > i) then set aArray to sort_QSort(aArray, i,
no_of_elements)
return aArray
end sort_QSort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on run
-- Demo:
set aList to {}
repeat with i from 1 to 200
set str to ""
set str to str & (ASCII character (65 + (random number 25 as
integer)))
set str to str & (ASCII character (97 + (random number 25 as
integer))) as string
set str to str & (random number 1000) as string
set end of my aList to str
end repeat
set t to (GetMilliSec)
mergesort(aList, 1, -1) -- Sort items 1 thru -1 of aList
aList
display dialog ((GetMilliSec) - t) / 1000 --> (for 500 -> .132
seconds), (for 1000 -> .303 seconds)
set t to (GetMilliSec)
sort_QSort(aList, 1, -1) -- Sort items 1 thru -1 of aList
aList
display dialog ((GetMilliSec) - t) / 1000 --> (for 500 -> .899
seconds), (for 1000 -> 2.629 seconds)
set t to (GetMilliSec)
sort_ASCII_Sort(aList)
aList
display dialog ((GetMilliSec) - t) / 1000 --> (for 500 -> 34.793
seconds), (for 1000 -> 245.098 seconds)
end run
Thanks for posting it...
Best Regards,
Bill Hernandez
Plano, Texas
_______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users
This email sent to email@hidden