配列 - Ubiquitous Computing and Networking Lab. -

2005年度
データ構造とアルゴリズム
第7回
「基礎的な整列アルゴリズム」
西尾信彦 [email protected]
立命館大学情報理工学部
情報システム学科
整列とは
• 何らかの(全)順序関係が成立するレコード
群を，その順序関係に従って並べ換えるこ
と
– 数字の昇順，降順や文字列の辞書順
• ここでは，整数データのみによるレコード
が n 個あるとき，その整数をキーとして整
列させることを考える
単純な整列アルゴリズム
• 先頭レコードを残りの全
てのレコードと順に比べ
る
• より小さいレコードを発見
したら交換する
• 結果，先頭に最も小さい
レコードが置かれる
• 残りのレコードに対し，同
様のことを繰りかえす．
void sort(void)
{
int i, j;
for (i = 0; i < n-1; i++) {
for (j = i+1; j < N; j++) {
if (arr[i] > arr[j]) {
swap(i, j);
}
}
}
}
単純法の計算量
• 二重のループ
– 外側は0から N-2
– 全体で n(n-1)/2 回
• 比較演算の回数は
ループの回数と同じ
• 交換は最悪ループ回
数，平均はその半分
• O(n2)の計算量
void sort(void)
{
int i, j;
for (i = 0; i < n-1; i++) {
for (j = i+1; j < N; j++) {
if (arr[i] > arr[j]) {
swap(i, j);
}
}
}
}
バブルソート
• 隣りあうレコー
ド同士を比較し
逆転していれば
交換する
• このままでは計
算量は単純
ソートと同じ
void sort(void)
{
int i, j;
for (i = N; i > 1; --i) {
for (j = 1; j < i; j++) {
if (arr[j-1] > arr[j]) {
swap(j-i, j);
}
}
}
}
バブルソートの改良 1
• ループの途中で整
列が完了している
ことを感知する
• 交換が一度も行な
われなければもう
整列している
• 計算量は0.01%程
度の改良
void sort(void)
{
int i, j, flag;
for (i = N; i > 1; --i) {
flag = 1;
for (j = 1; j < i; j++) {
if (arr[j-1] > arr[j]) {
swap(j-i, j);
flag = 0;
}
}
if (flag) return;
}
}
バブルソートの改良 2
• 最後に交換が行な
われた箇所を記憶
• それ以降は比較し
ない
• 計算量は0.04%程
度の改良
void sort(void)
{
int i, j, last;
for (i = N; i > 1; i = last) {
last = 0;
for (j = 1; j < i; j++) {
if (arr[j-1] > arr[j]) {
swap(j-i, j);
last = j;
}
}
}
}
単純法の改良：選択整列法
• 1回のループで交換は1度のみに限定する
– swap関数を呼び出す代りに交換候補として
min変数に保存する
• 比較はループの回数と同じ n(n-1)/2回
• 交換はn-1回に固定
– その代りにminへの代入が増えている
– 関数呼出しよりは安価
挿入整列法
• 先頭 [未整列レコード][整列レコード]最後
– と見たてて，先頭レコードを整列レコードのど
こに挿入するかを決定し，挿入する．
– 始めは整列レコードは最後レコードの1個
• その右に挿入するか，左に挿入するかを決定する
– 挿入のために配列内を移動させるのが手間
• ほぼ整列しているレコードに対して有効
アルゴリズムの特性
• あまり大差ないが，選択整列法の交換が
O(n) であるのは大きい
• 比較演算に対して交換の手間が大きなレ
コードでは効果が大きい
– 巨大なデータ本体を持つレコードとか
• ほぼ整列しているデータの場合には挿入
整列法が有利
– ほぼ O(n) の計算量

Download Report