本ページには広告が含まれています。
引数に指定された配列をクイックソートで並び替えます。
- 構文
- quickSort( 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クイックソート
クイックソートはリストにおいてピボットと呼ぶ要素を軸に分割を繰り返して整列を行うアルゴリズムです。
| 最悪計算時間 | \(O(n^{2})\) |
|---|---|
| 最良計算時間 | \(O(n \log n)\) |
| 平均計算時間 | \(O(n \log n)\) |
アルゴリズム
- 要素数が1つ以下なら整列されているとみなしソートは行わない。
- 軸（ピボット）となる要素をピックアップする。
- 軸より小さい数を前方、大きい数を後方に移動する。
- 分割された2つの区間に対して、上記手順を繰り返します。
- 区間の要素数が1つになるまで繰り返します。
関連記事
- QSORT関数 (スクリプト関数)
- QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
- small関数 (自作関数)
- 配列の中で小さい方から数えた順位の値を求めます。
- bubbleSort関数 (自作関数)
- 引数に指定された配列を バブルソート で並び替えます。
- shakerSort関数 (自作関数)
- シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行います。
- gnomeSort関数 (自作関数)
- ノームソートはソートアルゴリズムの一つです。挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行います。
- insertionSort関数 (自作関数)
- 挿入ソートは、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。
- shellSort関数 (自作関数)
- シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
- heapSort関数 (自作関数)
- 引数に指定された配列をヒープソートで並び替えます。
- shearSort関数 (自作関数)
- シェアソートはソートアルゴリズムの一つで、データを長方形に並べた上で各行・各列ごとにソートを行ないます。
- Sort.Header プロパティ (Excel)