|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 隣 ： [となり] 【名詞】 1. next to 2. next door to ・ 隣接 ： [りんせつ] 1. (n,vs) adjoin 2. adjacent 3. related ・ 交換 ： [こうかん] 1. (n,vs) exchange 2. interchange 3. switching 4. reciprocity 5. barter 6. substitution 7. replacement 8. clearing (of checks, cheques) ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある） ==アルゴリズム== 全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。 この「全ての要素に関して」において、全ての要素に関して比較交換が行なわれるならば順序を問わない特徴を持つ。この特徴により、比較交換順序を調整することで効率化されたアルゴリズムが多数派生している。そのため他の様々なソートアルゴリズムの基礎として一度は学ばされるアルゴリズムとなっている。 例えば前記の特徴によりバブルソートは並列処理と親和性が高く、比較交換器を潤沢に用いることで比較交換順序を調整したハードウェア実装では時間計算量はO(n)になる。この並列処理向けに比較交換順序を調整したアルゴリズムとして奇偶転置ソートがある。 また特にソフトウェアで実装される場合には一般に先頭から順に順次処理されるものなので、逆に先頭から順に順次処理されることを利用して不要なことが自明な比較交換をしないように効率化することは有効かつ直感的であり、この効率化されたアルゴリズムをもってバブルソートと呼ぶ場合もある。さらに、比較交換順序を逆順にすることで自明な比較交換を検出し易くしたアルゴリズムに挿入ソートがあり、効率化されたバブルソートは簡単な変更で容易に挿入ソートにできることから、ソートのソフトウェア実装としてバブルソートを選択する根拠はなく、学習専用の非効率的なアルゴリズムと考えられているのが現状である。 なお、係る派生したアルゴリズムが''隣接する要素と比較交換''以外の比較や交換を行なうことで効率化を図っている場合、安定という特徴を失う。 以下では、前記の自明な比較交換をしないように効率化されたバブルソートに関して解説する。 要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「バブルソート」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Bubble sort 」があります。 スポンサード リンク
|