quickSortクイックソート関数

本ページには広告が含まれています。

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

構文
quickSort( array, Lt, Rt )
引数
array 必須
ソートする数値を格納した配列。参照引数。
Lt 省略可
再帰呼び出し時の処理に必要なだけなので指定する必要なし。
Rt 省略可
再帰呼び出し時の処理に必要なだけなので指定する必要なし。
戻り値

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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

クイックソート

クイックソートはリストにおいてピボットと呼ぶ要素を軸に分割を繰り返して整列を行うアルゴリズムです。

最悪計算時間\(O(n^{2})\)
最良計算時間\(O(n \log n)\)
平均計算時間\(O(n \log n)\)

アルゴリズム

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

関連記事

QSORT関数 (スクリプト関数)
QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
bubbleSort関数 (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort関数 (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
gnomeSort関数 (自作関数)
引数に指定された配列を ノームソート で並び替えます。
insertionSort関数 (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
shellSort関数 (自作関数)
引数に指定された配列を シェルソート で並び替えます。
heapSort関数 (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
shearSort関数 (自作関数)
引数に指定された配列を シェアソート で並び替えます。
Sort.Header プロパティ (Excel)
最初の行にヘッダー情報が含まれるかどうかを指定します。