Contents
- 構文
- quickSort( Var array[], Lt, Rt )
- 引数
- array
- ソートする数値を格納した配列。参照引数。
- Lt
- 再帰呼び出し時の処理に必要なだけなので指定する必要なし。
- Rt
- 再帰呼び出し時の処理に必要なだけなので指定する必要なし。
- 戻値
プログラム
//////////////////////////////////////////////////
// 【引数】
// array : ソートする数値を格納した配列。参照引数。
// Lt : 再帰呼び出し時の処理に必要なだけなので指定する必要なし。
// Rt : 再帰呼び出し時の処理に必要なだけなので指定する必要なし。
// 【戻値】
//
//////////////////////////////////////////////////
PROCEDURE quickSort(Var array[], Lt, Rt)
DIM LtHold = Lt
DIM RtHold = Rt
DIM pivot = array[Lt]
WHILE Lt < Rt
WHILE array[Rt] >= pivot AND Lt < Rt
Rt = Rt - 1
WEND
IFB Lt <> Rt THEN
array[Lt] = array[Rt]
Lt = Lt + 1
ENDIF
WHILE array[Lt] <= pivot AND Lt < Rt
Lt = Lt + 1
WEND
IFB Lt <> Rt THEN
array[Rt] = array[Lt]
Rt = Rt - 1
ENDIF
WEND
array[Lt] = pivot
pivot = Lt
Lt = LtHold
Rt = RtHold
IF Lt < pivot THEN quickSort(array, Lt, pivot - 1)
IF Rt > pivot THEN quickSort(array, pivot + 1, Rt)
FEND
クイックソート
クイックソートはリストにおいてピボットと呼ぶ要素を軸に分割を繰り返して整列を行うアルゴリズムです。
アルゴリズム
- 要素数が1つ以下なら整列されているとみなしソートは行わない。
- 軸(ピボット)となる要素をピックアップする。
- 軸より小さい数を前方、大きい数を後方に移動する。
- 分割された2つの区間に対して、上記手順を繰り返します。
- 区間の要素数が1つになるまで繰り返します。
この記事は役に立ちましたか?