●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
