イケッチロゴ

Applescript実験室

イケッチトップページ

作品

リンク


Applescript実験室

自作スクリプト


●N×logNとなるソートのハンドラ-1
(クイックソート---失敗例)

実はこれまで実験に使っていたのは挿入ソートです。速度はリストの総数の2乗となります。今度はN×logNの速度のクイックソートを作ってみることにしましたが、見事に失敗しました。誰もが落ち入りやすい失敗のように思えたのであえて掲載します。
そもそも私はクイックソートというものを勘違いしていました。必ずしもN×logNにならないクイックソートがなぜ速いのかも考えもせず、図解だけを見て作ったのがいけなかったようです。クイックソートが速いのは、“必ずしもデータを移動しない”ことでした。それをご丁寧にリストを仕分け、いったんストックしておいて、あとで順番に処理していくという方法をとったために遅くなってしまったようです。
(ある方が、アップルスクリプトで組んだ、クイックソートの計測タイムを教えてくれていました。もし、それがなければ「こんなものなのか」と思っていたかもしれません。情報提供に感謝します。)
以下がこのスクリプトで3桁の数値のソートに要した時間です。
1000要素 1〜2秒
5000要素 9〜10秒
10000要素 21秒前後


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

if pItem > item i of aListRef then

set end of list_1Ref to item i of aListRef

else

set end of list_2Ref to item i of aListRef

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.