基本情報試験_データの整列をJavaScriptで考える

この記事の目的

それぞれの整列アルゴリズムの違いを理解する。

┗ 整列アルゴリズムでは比較する回数やデータ量がパフォーマンス(整列が完了するまでの時間)に影響する。

整列とは

データをある規則に沿って並べ替えること。(ソート)
データの値を小さいものから大きいものへと並び替える昇順と、データの値を大きいものから小さいものへと並び替える降順がある。

基本交換法

バブルソート、隣接交換法とも呼ばれる。隣り合うデータを比較しながら整列していく方法。

JavaScriptで書いてみる

トレースしてみる

| I | J | A | | --- | --- | ----------------- | | 5 | 0 | [5, 7, 1, 9, 3] | | | 1 | [5, 1, 7, 9, 3] | | | 2 | [5, 1, 7, 9, 3] | | | 3 | [5, 1, 7, 3, 9] | | 4 | 0 | [1, 5, 7, 3, 9] | | | 1 | [1, 5, 7, 3, 9] | | | 2 | [1, 5, 3, 7, 9] | | 3 | 0 | [1, 5, 3, 7, 9] | | | 1 | [1, 3, 5, 7, 9] | | 2 | 0 | [1, 3, 5, 7, 9] |

基本選択法

選択ソートとも呼ばれる。データの列の最小値または、最大値を選択する。選択された値を除いたデータから再度、最小値または最大値を選択し交換を繰り返すことで整列する方法。

JavaScriptで書いてみる

トレースしてみる

| I | J | K | A | | --- | --- | --- | ------------------ | | 0 | 1 | 0 | [5, 7, 1, 9, 3] | | | 2 | 2 | [5, 7, 1, 9, 3] | | | 3 | 2 | [5, 7, 1, 9, 3] | | | 4 | 2 |  [1, 7, 5, 9, 3] | | 1 | 2 | 2 |  [1, 7, 5, 9, 3] | | | 3 | 2 |  [1, 7, 5, 9, 3] | | | 4 | 4 |  [1, 3, 5, 9, 7] | | 2 | 3 | 2 |  [1, 3, 5, 9, 7] | | | 4 | 2 |  [1, 3, 5, 9, 7] | | 3 | 4 | 4 |  [1, 3, 5, 7, 9] |

基本挿入法

挿入ソートとも呼ばれる。先頭(左端)から順にデータを整列してく方法

JavaScriptで書いてみる

トレースしてみる

| I | J | A | | --- | --- | ----------------- | | 1 | 0 | [5, 7, 1, 9, 3] | | 2 | 1 | [5, 7, 1, 9, 3] | | | 0 | [1, 5, 7, 9, 3] | | 3 | 2 | [1, 5, 7, 9, 3] | | 4 | 3 | [1, 5, 7, 3, 9] | | | 2 | [1, 5, 3, 7, 9] | | | 1 | [1, 3, 5, 7, 9] | | | 0 | [1, 3, 5, 7, 9] |

シェルソート

改良挿入法とも呼ばれる。基本挿入法を改良したような整列方法。
一定間隔おきにデータを取り出し、基本挿入法を用いて整列さる。さらに間隔を詰めながら間隔が1になるまで整列を繰り返す。

クイックソート

適当な基準を定め基準値より小さい値のグループと基準値より大きいグループで分ける操作を繰り返して整列する。

ヒープソート

未整列の部分を順序木に構成し、最大値or最小値を取り出すことを繰り返しながら整列する方法。