quickSort

タグ: ,

引数に指定された配列をクイックソートで並び替えます。

構文
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. 要素数が1つ以下なら整列されているとみなしソートは行わない。
  2. 軸（ピボット）となる要素をピックアップする。
  3. 軸より小さい数を前方、大きい数を後方に移動する。
  4. 分割された2つの区間に対して、上記手順を繰り返します。
  5. 区間の要素数が1つになるまで繰り返します。