イケッチロゴ

Applescript実験室

イケッチトップページ

作品

リンク


Applescript実験室

自作スクリプト


●N×logNとなるソートのハンドラ-3
(クイックソート---前回のものに少し手を入れました)

「N×logN となるソートのハンドラ-1」で失敗例として紹介したクイックソートに少し手を入れました。マージソートのハンドラでは、速く動かすための施策を施していたにもかかわらず、クイックソートの方ではやっていませんでした。このままではアンフェアなので、以下のように修正します。
“2回以上使用する値には、変数名を付けておく”というただそれだけのことですが、これだけでもずいぶんと速くなります。だからといってマージソート並みの速度を出すことは出来ません。前にも触れたように、本来のクイックソートではないからです。


global aList, list_1, list_2, list_1Ref, list_2Ref, stackNum, currentStackNum, stackListRef, aList, aListRef, sortList, sortListRef

set {sortList, aList, list_1, list_2, stackList, stackNum, currentStackNum} to {{}, {}, {}, {}, {}, 0, 1}

set {sortListRef, aListRef, list_1Ref, list_2Ref, stackListRef} to {a reference to sortList, a reference to aList, a reference to list_1, a reference to list_2, a reference to stackList}


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

set theList to {}

set theListRef to a reference to theList

repeat 1000 times

set end of theListRef to (some item of n) * 100 + (some item of n) * 10 + (some item of n)

end repeat


set T to current date

qSort(theList)

(current date) - T


on qSort(theList)

set sortList to {}

set countTheList to count theList

push(theList)

repeat while (count sortListRef) < countTheList

set aList to picup()

set countAList to count aListRef

if countAList = 1 then

set end of sortListRef to item 1 of aListRef

else

set i to 2

set {list_1, list_2} to {{}, {}}

set pItem to item 1 of aListRef

repeat countAList - 1 times

set aItem to item i of aListRef --※2回以上使用する可能性のある値には変数名を付けておく

if pItem > aItem then

set end of list_1Ref to aItem --

else

set end of list_2Ref to aItem --

end if

set i to i + 1

end repeat

if list_2 is not {} then push(list_2)

push({pItem})

if list_1 is not {} then push(list_1)

end if

end repeat

return sortList

end qSort


on push(aItem)

if stackNum < currentStackNum then

set end of stackListRef to aItem

set {stackNum, currentStackNum} to {stackNum + 1, currentStackNum + 1}

else

set item currentStackNum of stackListRef to aItem

set currentStackNum to currentStackNum + 1

end if

end push


on picup()

if currentStackNum > 1 then

set currentStackNum to currentStackNum - 1

return item currentStackNum of stackListRef

else

return false

end if

end picup



Iketch Design Office, All Rights Recerved.