並べ替えのアルゴリズム

予備知識

• アルゴリズムとは？
• 文章構成

はじめに

この記事では並べ替えのアルゴリズムの中でも基本的なものを紹介します。
具体的には以下５つのアルゴリズムです。

配列の最大要素数が５のときの例を表で掲載

• バブルソート
• 選択ソート
• 基数ソート

配列の最大要素数が１０のときの例を表で掲載

• バケットソート
• 分布数え上げソート

ソートとは並べ替えを意味する横文字です。
これらアルゴリズムの計算量について［最善，最悪，平均］の区別はありません。
［バケット，分布数え上げ］ソートについては、空間計算量が大きいため例外的に記載します。
基数ソートについても空間計算量は無視できるものの、上記２つに関連するため記載します。

並べ替えのアルゴリズムで出来ること

データ構造を昇順または降順に並べ替える
※ここでデータ構造は配列とする

計算対象選別

判定	計算対象	関係	基準値
○	データの比較回数	≧	データの交換回数
	データの交換回数	=	配列の中身により異なる
	関数の呼び出し回数	=	確定値の決定回数

共有変数定義

変数にする対象	変数	関係	数値
配列の最大要素数	$n$	>	1
配列の数値範囲	$m$
比較回数の総和	$S$

※基数ソートの場合のみｍは配列の最大値の桁数を意味する

バブルソート

このアルゴリズムでは隣接する２つの要素を順番に比較していくことで配列を並べかえる
その有り様が泡の動きに似ていることからバブルソートと呼ばれる

最大値を基準として配列を昇順に並べ替え

最小値を基準として配列を降順に並べ替え

比較基準の異なるバブルソート

※黄色は要素の交換が発生する部分

表のように同じバブルソートでも比較基準が異なる場合で違う形になる
この表では最小値を基準とする昇順バブルソートを示す
同じように最大値を基準とする降順バブルソートもある

一般化

配列の最大要素数が５のとき昇順または降順の表より
比較回数の総和Ｓは

$$S=(5-1)+(5-2)+(5-3)+(5-4)$$

一般化すると
$S=T(n)$ なので

$$T(n)=(n-1)+(n-2)+(n-3)+(n-4)…$$

自然数の和の公式より
$T(n)=\frac 1 2 n(n-1)$
漸近計算量は $O(n^2)$ である
※公式を元の形のまま適用するためには例の場合で総和が１～４までの和と捉えると分かりやすい

選択ソート

このアルゴリズムでは比較している時点までの最小値を基準とするため
交換回数は確定値が決まるごとに１回ずつで済む
比較回数はバブルソートと同じである

比較基準の異なるバブルソートの例で交換回数は８回である
バブルソートでは前確定値時点で交換したことで再度の余計な交換が発生する
下表のように同じ配列における選択ソートの場合だと交換回数は４回である
よって選択ソートはバブルソートと比べて交換回数が少ない

最小値を基準として配列を昇順に並べ替え

最大値を基準として配列を降順に並べ替え

一般化

バブルソートの一般化と同じになるため省略する
前述のとおり交換回数はバブルソートより少ない

基数ソート

基数とは数値のもとになるもので０～９の数字である
基数を用意して配列を先頭から分別していく
配列の要素の数値の桁数が多い場合には桁数の数だけ分別を繰り返す
一の位から順番に分別することで並べ替えが完了する

計算量が分かりやすいように比較順番に合わせた表になっている
実際には各基数のところに配列の各要素が縦ならびで並べ替えられていく
各位の数で同じ数字であるときは先に分別した方から左側に詰めて並べる
例えば３０１と５０１の１の位は同じなので配列の先頭の要素の値が３０１のとき
他の数値も交えて書いてみると

基数	優先席	次席	…
0	100
1	301	501
2	502
…

一般化

表のとおり
$T(n)=nm$
漸近計算量は $O(nm)$ である
空間計算量として基数分の $10$ 必要である

バケットソート

このアルゴリズムを使うには前もって配列の要素に入る数値の範囲が分かっている必要がある

例えば少なくとも１～５であると分かっている場合には
まずバケツを５つ用意して１～５の番号を記入する
そして配列を先頭の要素から順番に比較していき
要素内の数値を確認して用意されたバケツのうち同じ番号のバケツに分別していく
ここで言う用意されたバケツが数値範囲に該当する

一般化

表のとおり
$T(n)=n$
漸近計算量は $O(n)$ である
空間計算量として $nm$ が必要である

分布数え上げソート

このアルゴリズムを使うには前もって配列の要素に入る数値の範囲が分かっている必要がある

基本的な構造はバケットソートに似ているが数値範囲としてバケツではなくキーを使う
バケツに番号を記入するのは同じで配列の要素を分別したときに個数を記録していくことが特徴である
すべての記録が終了したら記録された個数をもとに配列の並べ替えを完了する
個数を記録する鍵的な仕組みから数値範囲を「キー」と呼ぶ

一般化

記録終了までの比較と記録終了後の配列の並べ替えの分だけ計算量がかかる

具体的には比較はｎ回かかり並べ替えはキー分のｍ回かかるので
$T(n)=n+m$
漸近計算量は $O(n+m)$ である
空間計算量として $n+m$ が必要である