bubbleSort関数

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

引数に指定された配列をバブルソートで並び替えます。参照引数で戻り値はありません。

構文
bubbleSort( array, optimazed )
引数
array 必須
ソートする数値を格納した配列。参照引数。
optimazed 省略可
最適化フラグ
戻り値

プログラム

UWSC

解説

    2-11行目
    UWSC
    配列全体を走査(チェック)。最大で要素の個数-1回ループします。1周するごとに、未整列の部分の最大値が1つずつ後ろに確定していきます。
    3行目
    UWSC
    この周回でデータの入れ替えが起こったかを記録するフラグを、FALSEに初期化します。
    4-9行目
    UWSC
    隣り合うデータを比較するループです。外側のループがi回進むと後ろのi個のデータは整列済みとなっているため、ループする範囲を毎回1ずつ狭めて無駄を省きます。
    5-8行目
    UWSC
    左側のデータが右側のデータより大きければこの2つを入れ替え、swappedをTRUEにして入れ替えが発生したフラグを立てます。
    10行目
    UWSC
    最適化が有効(optimazedがTRUE)でこの周回で入れ替えが発生していなければ(swappedがFALSE)ならばループを抜けます。

使い方

UWSC
結果
プレーンテキスト

バブルソート

バブルソートは、ソートを行うアルゴリズムの一つです。リストにおいて隣り合うふたつの要素の大小を比較しながらソートを行います。基本交換法、隣接交換法ともいいます。

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

アルゴリズム

すべての要素に関して、隣接する要素を比較し大小が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行います。繰り返しは入れ替えが起こらなくなった時点で中断することができます。

  1. 最初に、配列の先頭要素をカレントポインタに設定します。
  2. カレントポインタが配列の末尾まで到達するまで、以下の処理を繰り返します。
    1. カレントポインタが指す要素と、カレントポインタの次の要素の大小関係を比較します。
    2. もし、大小関係が逆であれば、2つの要素を交換します。
  3. カレントポインタが配列の末尾まで到達したら、ソートが完了です。
メリット
  • 実装が極めてシンプルで直感的に理解しやすい。
  • 別のメモリ領域をほとんど必要としない(インプレース)。
  • 同じ値の順序が入れ替わらない(安定ソート)。
  • デメリット
    1. データの件数をnとすると、比較回数がn²に比例して増えるため、大量のデータ処理には全く向かない。
    アルゴリズムを選択して「開始」を押してください。
    比較交換/代入基準整列済処理中のグループ処理対象外(薄く表示)
    比較回数: 0
    交換/代入回数: 0

    関連記事

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