プログラミング言語 Standard ML 入門 (問題の解答例)
13.2 配列のソートアルゴリズム
問 13.1
sort 関数中にコメントで記述されている 配列の2つの要素を入れ替える関数 swap を定義せよ．
解答例 問13.3の解答を参照。
問 13.2
以上の方針に従い，sort 関数中にコメントで記述されている pivot の設定処理を書け．
解答例 問13.3の解答を参照。
問 13.3
partition 関数の中にコメントで記述されている scanRight と scanLeft 関数を作成し， ArrayQuickSortストラクチャを完成させよ．
解答例 ArrayQuickSortストラクチャ全体のコード例を以下に示す。
signature SORT = sig
val sort : ’a array * (’a * ’a -> order) -> unit
end
structure ArrayQuickSort : SORT =
struct
local
open Array
in
fun sort (array,comp) =
let
fun swap (i,j) =
let val temp = sub(array,i)
in (update(array,i,sub(array,j)); update(array,j,temp))
end
fun getPivot (i,j) =
let
val delta = (j-i) div 4
val i = i + delta
val j = i + delta * 3
val mid = i + (j-i) div 2
val ie = sub(array,i)
val je = sub(array,j)
val me = sub(array,mid)
in
case (comp(ie,me),comp(me, je))
of (LESS, LESS) => (mid,me)
| (LESS, _) => (case comp(ie, je) of LESS => (j,je) | _ => (i,ie))
| (_, GREATER) => (mid,me)
| _ => (case comp(ie, je) of LESS => (i,ie) | _ => (j,je))
end
fun qsort (i,j) =
if j <= i+1 then ()
else
let
val pivot =
let val (pi,pivot) = getPivot(i,j-1)
in update(array,pi,sub(array,i));
update(array,i,pivot);
pivot
end
fun partition (a,b) =
if b < a then (a - 1)
else
let
fun scanRight a =
if a > b then a
else
case comp(sub(array,a),pivot) of
GREATER => a
| _ => scanRight (a+1)
val a = scanRight a
fun scanLeft b =
if b < a then b
else
case comp(sub(array,b),pivot) of
GREATER => scanLeft (b - 1)
| _ => b
val b = scanLeft b
in
if b < a then (a - 1)
else (swap(a,b);partition (a+1,b-1))
end
val k = partition (i+1,j-1)
val _ = swap(i,k)
in
(qsort (i,k); qsort (k+1,j))
end
in
qsort (0,Array.length array)
end
end
end
問 13.4
以下の改良を加えよ．
-
1.
配列の大きさが小さい場合，クイックソートアルゴリズムは最適ではない． qsort 関数の冒頭で部分配列の大きさを判定し， 大きさがとの場合を特別に処理するように変更せよ．
-
2.
pivot要素と先頭要素の入れ替え処理を伴うpivotの選択処理は，配列の大きさ が小さいときかえって効率を低下させる． 配列の大きさが30以下の場合，先頭要素をpivotとするように変更せよ．
解答例 以下に例を示す。この例では、pivotの選択も多少の洗練を試みている。 ただし、効果があるかは計算実行環境にもより、一様に最適なものがあるかは、 今後の探求によるところである。
structure ArrayQuickSortOpt : SORT =
struct
local
open Array
in
fun sort (array,comp) =
let
fun swap (i,j) =
let val temp = sub(array,i)
in (update(array,i,sub(array,j)); update(array,j,temp))
end
fun sort3 i =
case comp(sub(array,i),sub(array,i+1))
of GREATER =>
(case comp(sub(array,i+1),sub(array,i+2))
of GREATER => (* 3 2 1 *)
swap(i,i+2)
| _ => (case comp(sub(array,i),sub(array,i+2))
of GREATER => (* 3 1 2 *)
let val ei = sub(array,i) in
(update(array,i,sub(array,i+1));
update(array,i+1,sub(array,i+2));
update(array,i+2,ei))
end
| _ => (* 2 1 3 *)
(swap(i,i+1))
)
)
| _ =>
(case comp(sub(array,i+1),sub(array,i+2))
of GREATER =>
(case comp(sub(array,i),sub(array,i+2))
of GREATER => (* 2 3 1 *)
let val ei = sub(array,i) in
(update(array,i,sub(array,i+2));
update(array,i+2,sub(array,i+1));
update(array,i+1,ei))
end
| _ => (* 1 3 2 *)
(swap(i+1,i+2))
)
| _ => (* 1 2 3 *)
())
fun getPivot (i,j) =
let
val delta = (j-i) div 4
val i = i + delta
val j = i + delta * 3
val mid = i + (j-i) div 2
val ie = sub(array,i)
val je = sub(array,j)
val me = sub(array,mid)
in
case (comp(ie,me),comp(me, je))
of (LESS, LESS) => (mid,me)
| (LESS, _) => (case comp(ie, je) of LESS => (j,je) | _ => (i,ie))
| (_, GREATER) => (mid,me)
| _ => (case comp(ie, je) of LESS => (i,ie) | _ => (j,je))
end
fun qsort (i,j) =
if j < i+2 then ()
else if j = i+2 then case (comp(sub(array,i),sub(array,i+1)))
of GREATER => swap(i,i+1)
| _ => ()
else if j = i + 3 then sort3 i
else
let
val pivot = if (j-i) < 30 then sub(array,i)
else
let val (pi,pivot) = getPivot(i,j-1)
in update(array,pi,sub(array,i));
update(array,i,pivot);
pivot
end
fun partition (a,b) =
if b < a then a
else
let
fun scanRight a =
if a > b then a
else
case comp(sub(array,a),pivot)
of GREATER => a
| _ => scanRight (a+1)
val a = scanRight a
fun scanLeft b =
if b < a then b
else
case comp(sub(array,b),pivot)
of GREATER => scanLeft (b - 1)
| _ => b
val b = scanLeft b
in
if b < a then a
else (swap(a,b);
partition (a+1,b-1))
end
val a = partition (i+1,j-1)
val _ = swap(i,a-1)
in
(qsort (i,a-1); qsort (a,j))
end
in
qsort (0,Array.length array)
end
end
end