基本情報試験_データの整列を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最小値を取り出すことを繰り返しながら整列する方法。