イケッチロゴ

Applescript実験室

イケッチトップページ

作品

リンク


Applescript実験室

自作スクリプト


●N×logNとなるソートのハンドラ-2
(マージソート)

N×logNとなるソートの速度を知ろうと思い、マージソートを作ることにしました。これが意外に速く、どこか間違っているんじゃないかとちょっと心配です。
以下がこのスクリプトで5桁の数値のソートに要した時間です。
1000要素 0.5〜0.6秒
5000要素 3〜4秒
10000要素 7〜8秒
20000要素 16秒前後


global stackList, stackListRef, compRecRef, theSortList, theSortListRef

set {stackList, theSortList} to {{}, {}}

set {stackListRef, theSortListRef} to {a reference to stackList, a reference to theSortList}

set compRec to {listA:{}, listB:{}, compList:{}}

set compRecRef to a reference to compRec


set n to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

set numList to {}

set numListRef to a reference to numList

repeat 1000 times

set end of numListRef to (some item of n) * 10000 + (some item of n) * 1000 + (some item of n) * 100 + (some item of n) * 10 + (some item of n)

end repeat


--set T to current date

--repeat 1 times --速度を計測するために何回か繰り返す

mergeSort(numListRef)

--end repeat

--(current date) - T


on mergeSort(theList)

set i to 2

set n to 2

set countTheList to count theList

set stackList to {}

repeat until i > countTheList

set end of stackListRef to mergeList({item (i - 1) of theList}, {item i of theList})

set i to i + 2

end repeat

if countTheList mod 2 > 0 then set end of stackListRef to {item -1 of theList}

repeat while n < countTheList

set i to 2

set theSortList to {}

repeat until i > (count stackListRef)

set end of theSortListRef to mergeList(item (i - 1) of stackListRef, item i of stackListRef)

set i to i + 2

end repeat

if (count stackListRef) mod 2 > 0 then set end of theSortListRef to item -1 of stackListRef

set n to n * 2

set stackList to theSortList

end repeat

return item 1 of stackListRef

end mergeSort


--以下がソート済みのデータを合体させるルーチン

on mergeList(list_1, list_2)

set compList of compRecRef to {}

if list_1 is {} then return list_2

if list_2 is {} then return list_1

set {listA of compRecRef, listB of compRecRef} to {list_1, list_2}

set {numA, numB} to {1, 1}

set {A, B} to {item 1 of listA of compRecRef, item 1 of listB of compRecRef}

repeat

if A > B then

set {end of compList of compRecRef, numB} to {B, numB + 1}

if numB > (count listB of compRecRef) then exit repeat

set B to item numB of listB of compRecRef

else

set {end of compList of compRecRef, numA} to {A, numA + 1}

if numA > (count listA of compRecRef) then exit repeat

set A to item numA of listA of compRecRef

end if

end repeat

if numA > (count listA of compRecRef) then

repeat until (count listB of compRecRef) < numB

set end of compList of compRecRef to item numB of listB of compRecRef

set numB to numB + 1

end repeat

else

repeat until (count listA of compRecRef) < numA

set end of compList of compRecRef to item numA of listA of compRecRef

set numA to numA + 1

end repeat

end if

return compList of compRecRef

end mergeList



Iketch Design Office, All Rights Recerved.