毎月アルゴリズム – 第4回 –

はじめに

こんにちは。よっしーです。
毎月アルゴリズムを考えていくブログの第4回目です。
前回はより多く種類のデータ構造を見ていきました。
今回でデータ構造をすべて話しきろうと思いましたが、今までデータ構造の話ばかりだったのでアルゴリズム多めの回にしようかなと考えまして、今回はアルゴリズムのみを考えていこうと思います。
前回までのデータ構造で、一応線形のデータ構造は考えましたので、次回以降でグラフデータの構造を考えていきたいと思います。

アルゴリズムを考えてみる

本日は以下のソートに関してアルゴリズムを考えていきます。

  • シェルソート
  • マージソート
  • クイックソート

シェルソート

概要

シェルソートは改良挿入ソートとも呼ばれます。

前回を思い出していただきたいのですが、挿入ソートは最悪計算量が O(n^2) だったのに対して、最良計算量は O(n) でした。
そのため、挿入ソートは「整列されたデータに対しては高速」、「あまり整列されていないデータに対しては低速」という特長があると言えます。

適当な間隔を開けて飛び飛びのデータ列に対して予めソートをして、その数列に対して挿入ソートを適用すれば高速になると考えられたのがこのシェルソートです。

処理

  1. 元データを用意する
  2. 適当な間隔 h を決定する。(今回は4とする)
  3. 間隔 h を空けて取り出したデータ列に挿入ソートを適用する
  4. 間隔 h を狭めて、2.を適用する操作を繰り返す。(今回は1すなわち普通の挿入ソートを適用する)
  5. h=1 になったら、最後に挿入ソートを適用して終了

処理の上記処理

オーダー

オーダーは以下です。

最悪計算量 O(n(logn)^2)
最良計算量 O(nlogn)
平均計算量 O(n^{1.25})

平均計算量は O(n^{1.25})と書きましたが、hのとり方によって計算量は異なります。
hの間隔が以下の場合 O(n^{1.25}) となるようです。
1, 4, 13, … , (3^{k} - 1) / 2
とされています。

参考:The Art of Computer Programming

コード

シェルソートのコードを考えてみました。
コードはC#で書いています。
hの間隔は (3^{k} - 1) / 2 になるように取っています。

マージソート

概要

マージソートはソートしたい数列を同じ長さの2つの数列に分割していきます。
これ以上分割できない長さまで分割を繰り返し(つまりは1つの数字になるまで)ます。
その後、隣のグループとソートしながら統合していきます。
これをすべてが統合されるまで繰り返します。

2つのグループを1つずつマージしていき最終的に統合した時ソートが完了していることからマージソートと呼ばれます。

処理

  1. 元データを用意する
  2. 数列を半分に分割していき最小単位に分割されるまで分割を繰り返す(最小単位とは、要素数1の数列)
  3. 隣り合うグループを統合する。その際、各グループの一番左の数字同士を比較して、左に小さい数字が配置されるように統合していく
  4. 4をグループが1つになるまで繰り返す

処理の上記処理

オーダー

オーダーは以下です。

最悪計算量 O(nlogn)
最良計算量 O(nlogn)
平均計算量 O(nlogn)

分割していくと logn 段処理をすることが分かります。
要素 n の半分、半分、半分、と logn 回半分にすると要素が1となります。
少し分かりづらいですが、数列にすると、

n / 2 / 2 / 2 \cdot\cdot\cdot\cdot  = 1

としたいので、/2m 回登場したと考えると、式変形すると

(n / 2)^m = 1
n = 2^m
logn = m (両辺 log_2 で対数を取りました。アルゴリズムの世界では log が出てくる時は底の2を省略します)

となるため、logn 回割りましたということになります。
1段あたりの処理のオーダーは O(n) となりますので、計算量は O(n) \times O(logn) となり、 O(nlogn) となります

コード

マージソートのコードを考えてみました。
コードはC#で書いています。
グループごとに一番左の数字が小さいという性質を利用して、Queueを用いて実装してみました。

クイックソート

概要

クイックソートでは基準となる数(ピボットと呼びます。)を数列の中からランダムに1つ選びます。
そしてピボット以外の数をピボットより小さい数、大きい数の2グループに分けていきます。
その後、それぞれのグループでまたピボットを選定してそれぞれ小さい数大きい数にどんどん振り分けていく作業を繰り返すことで全体をソートします。
C#のSortメソッドはクイックソートを実装しています。
名前の通り、一番早いソートと言われていますが、並びが悪いと O(n^2) の計算量がかかってしまうことが特徴です。
クイックソートとは名前が潔くてかっこいいですね。自負を感じますね。

処理

  1. 元データを用意する
  2. 基準となるピボットを数列グループの中から選ぶ
  3. 数列グループの中の一番左から走査し、基準のピボット以上の数字を選び、インデックスを記憶。
  4. 数列グループの中の一番右から走査し、基準のピボットより小さい数字を選び、インデックスを記憶。
  5. 3, 4 で記憶したインデックスの数値を入れ替える。
  6. 3~5の操作を繰り返し、3で走査しているインデックスが4で走査しているインデックスを超えた数字を記憶(すべてを走査しきった状態になる)。
    この処理で得た数字はピボットの数より小さいグループと大きいグループに区分けしたこととなる。
  7. 小さいグループと大きいグループでそれぞれ3~6の操作を繰り返す。

処理の上記処理

オーダー

最悪計算量 O(n^2)
最良計算量 O(nlogn)
平均計算量 O(nlogn)

基本的に2分割していくことになるので、平均はマージソートと同等の O(nlogn) となります。
最悪の計算時間は逆順ソートになった場合再帰処理が n 段になってしまうため、O(n^2)となってしまう。

ピボット軸の選定

クイックソートは少し特殊でピボットの選定が重要です。
というのも、できるだけ半分に分割できた方が処理の時間が短くなります。
そのためできるだけ中央値を選出したいのですが、選定に時間をかけるのも本末転倒です。
選定方式は以下のような候補があります。

案1. 左端の要素
案2. ランダムに選んだ位置の要素
案3. 左端,中央,右端の要素の中央値の要素
案4. 左から見て最初に得られた2つの異なる値の大きい方の要素(3,3,5,4,6,2 みたいな感じだと、3,5を選出する)

案1~3の場合は、最小値を選択してしまう可能性があります。
今回は案4で考えようと思います。

コード

クイックソートのコードを考えてみました。
コードはC#で書いています。

おわりに

今回は3つほどソートに関するアルゴリズムを考えていきました。
先人たちはいろいろな方法で効率の良いアルゴリズムを考えており、ソートだけでも随分な量になります。
各言語でソートのメソッドは用意されており、裏側を考えることは滅多にありませんが、こうやって改めてアルゴリズムを考えてみるのも勉強になって良いです。
よろしければ次回も見ていただけますと幸いです!

シリーズのブログの数も増えてきましたので、リンクを貼っておきます。

第0回 (初歩的な数学のアルゴリズムを考えてみよう)
第1回
第2回
第3回

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

コメント

この記事へのコメントはありません。

アーカイブ

カテゴリー

PAGE TOP