quickSort関数

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

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

構文
quickSort( array, Lt, Rt )
引数
array 必須
ソートする数値を格納した配列。参照引数。
Lt 省略可
ピボットで分割したとき処理するグループの左端。再帰呼び出し時の処理に必要な引数のため指定する必要なし。
Rt 省略可
ピボットで分割したとき処理するグループの右端。再帰呼び出し時の処理に必要な引数のため指定する必要なし。
戻り値

プログラム

UWSC

解説

    2行目
    UWSC
    最初の呼び出し時、Rtには配列の要素数-1(最後のインデックス)を渡す必要があります。RtがEMPTYの場合、最後のインデックスを代入します。
    3行目
    UWSC
    探索によって変化するLtの初期値を保持し、再帰処理で左側のソート範囲を指定するために使用します。
    4行目
    UWSC
    探索によって変化するRtの初期値を保持し、再帰処理で右側のソート範囲を指定するために使用します。
    5行目
    UWSC
    配列の先頭要素を基準値として保持し、探索時の大小比較と、ソート完了時の格納位置の確定に使用します。
    7-22行目
    UWSC
    左端のインデックスLtが右端のインデックスRtより小さい間、左右からの探索と要素の入れ替えを繰り返します。左右のインデックスが一致すると探索範囲がなくなるため、ループを終了します。これにより、基準値を境界として配列を左右に分割する処理を行います。
    8-10行目
    UWSC
    右端の要素が基準値pivot以上である間、右端のインデックスRtを1つずつ減らし、左方向に探索します。基準値より小さい値が見つかるか、左右のインデックスが一致すると探索を終了します。
    11-14行目
    UWSC
    基準値の位置pivotより左側にソート対象の要素が存在する場合、その範囲をquickSort関数に渡して再帰的にソートします。基準値自身はソート済みのため、終了位置にはpivot - 1を指定します。
    15-17行目
    UWSC
    左端の要素が基準値pivot以下である間、左端のインデックスLtを1つずつ増やし、右方向に探索します。基準値より大きい値が見つかるか、左右のインデックスが一致すると探索を終了します。
    18-21行目
    UWSC
    基準値の位置pivotより右側にソート対象の要素が存在する場合、その範囲をquickSort関数に渡して再帰的にソートします。基準値自身はソート済みのため、開始位置にはpivot + 1を指定します。
    24行目
    UWSC
    ピボットの値を、最終的に確定した「中央の位置」に書き戻す。
    25行目
    UWSC
    変数 pivot の中身を、「基準値(値)」から「基準値のインデックス(位置)」に切り替える。
    26行目
    UWSC
    左端のポインタを、この関数が始まったときの「最初の位置」に戻す。
    27行目
    UWSC
    右端のポインタを、この関数が始まったときの「最初の位置」に戻す。

クイックソート

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

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

アルゴリズム

  1. 要素数が1つ以下なら整列されているとみなしソートは行わない。
  2. 軸(ピボット)となる要素をピックアップする。
  3. 軸より小さい数を前方、大きい数を後方に移動する。
  4. 分割された2つの区間に対して、上記手順を繰り返します。
  5. 区間の要素数が1つになるまで繰り返します。
アルゴリズムを選択して「開始」を押してください。
比較交換/代入基準整列済処理中のグループ処理対象外(薄く表示)
比較回数: 0
交換/代入回数: 0

関連記事

small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
shearSort関数 (自作関数)
引数に指定された配列を シェアソート で並び替えます。
heapSort関数 (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
shellSort関数 (自作関数)
引数に指定された配列を シェルソート で並び替えます。
insertionSort関数 (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
gnomeSort関数 (自作関数)
引数に指定された配列を ノームソート で並び替えます。
shakerSort関数 (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
bubbleSort関数 (自作関数)
引数に指定された配列を バブルソート で並び替えます。
QSORT関数 (スクリプト関数)
配列の中身をソートします。
arrayRand関数 (自作関数)
一次元配列から一つの値をランダムに取得します。