Re: Sorting a list of records
Re: Sorting a list of records
The merge sort seems more complicated and a lot slower. Am I missing something?
ES
-----------
property sortedList : {}
property calcList : {}
property listToSort : {}
property finalList : {}
set listToSort to {}
repeat with x from 1 to 100
set myData to random number from 1 to 10
set the end of listToSort to myData
end repeat
copy listToSort to originalList
set sortAListStart to current date
set sortedLists to SortAList()
set sortAListEnd to current date
set sortAListElapse to sortAListEnd - sortAListStart
set mergeStart to current date
mergeSort(listToSort, 1, -1)
set mergeEnd to current date
set mergeElapse to mergeEnd - mergeStart
on mergeSort(theList, l, r)
script o
property mainList : theList -- The list to be sorted.
property extract : missing value -- Holder for extracts from the list
-- Recursively merge-sort the section of the list between items l and r.
on msort(l, r)
-- Recurse to sort the left and right halves of this section.
set m to (l + r) div 2
if (m > l) then msort(l, m)
if (r > m + 1) then msort(m + 1, r)
-- The left and right halves are now sorted. Extract a copy of the whole section.
set o's extract to items l thru r of o's mainList
(* Now we'll merge the two halves of the extract, writing the result back to the original section of list. *)
set j to 1 -- Left half loop index.
set leftLen to m - l + 1 -- The length of the left half (to the middle of the extract).
set k to leftLen + 1 -- Right half loop index.
set extractLen to r - l + 1 -- The length of the extract.
-- Get the first value from each half of the extract.
set leftVal to item j of o's extract
set rightVal to item k of o's extract
repeat with i from l to r -- 'i' indexes this section in the original list.
if (rightVal < leftVal) then
-- If the current right value's less than the current left one, put it in this slot of the original list.
set item i of o's mainList to rightVal
if (k < extractLen) then
-- If there are more values in the right half of the extract, get the next one …
set k to k + 1
set rightVal to item k of o's extract
else
-- … otherwise dump the remaining left values to the original list and end this recursion level.
repeat with i from (i + 1) to r
set item i of o's mainList to item j of o's extract
set j to j + 1
end repeat
exit repeat
end if
else
-- If the current left value's less than or equal to the current right one, put it in this original-list slot.
set item i of o's mainList to leftVal
if (j < leftLen) then
-- If there are more values in the left half of the extract, get the next one …
set j to j + 1
set leftVal to item j of o's extract
else
-- … otherwise end this recursion level.
-- The remaining right values were already in place in the list when the extract was obtained.
exit repeat
end if
end if
end repeat
end msort
end script
set listLen to (count theList)
if (listLen > 1) then
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
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 SortAList()
set sortedList to {}
set calcList to {}
set listSize to count of listToSort
repeat listSize times
set the end of sortedList to {}
set the end of calcList to {1}
end repeat
set i to 1
set y to 2
repeat
set thisItem to item i of listToSort
repeat with x from y to count of listToSort
set compItem to item x of listToSort
if (thisItem) > (compItem) then
set item i of calcList to (item i of calcList) + 1
else if (thisItem) < (compItem) then
set item x of calcList to (item x of calcList) + 1
end if
end repeat
set i to i + 1
set y to y + 1
if y > listSize then exit repeat
end repeat
repeat with x from 1 to count of calcList
set biggerThanCount to item x of calcList
set the end of item (biggerThanCount) of sortedList to item x of listToSort
end repeat
set finalList to {}
repeat with thisItem in sortedList
repeat with thisValue in thisItem
set the end of finalList to thisValue as item
end repeat
end repeat
return finalList
end SortAList
_______________________________________________
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