アルゴリズムとは？日常での例や代表的なアルゴリズム8選を紹介

あなたはアルゴリズムを理解して実装できますか？

実際に手を動かすと分かりますが、アルゴリズムの理解とプログラミング言語による実装には大きな壁があります。

本稿でこの高い壁を乗り越え、アルゴリズムの奥深さを味わってほしいと思います。

筆者による、

C
Ruby
Python

の実装例を、各アルゴリズムに対して紹介しますので、ぜひとも勉強の参考にしてください。
アルゴリズムを勉強することは、プログラミングの基礎練習です。スポーツで言えば、ランニング。算数でいえば九九の練習。

各種アルゴリズムを、自分の頭で考え、自分の手でコーディングすることを通して、各プログラミング言語の文法、プログラミングの考え方を習得しましょう。

この記事もオススメ

プログラミング言語とは？分類などの基礎知識を初心者向けにわかりやすく解説

この記事の目次

1 アルゴリズムとは？例題を挙げてわかりやすく解説
- 1.1 アルゴリズムは答えを出す手順
- 1.2 身近な例で理解するアルゴリズム
2 アルゴリズムの良し悪し
3 知っておくべき必須アルゴリズム8選とプログラミングでの実装例
- 3.1 探索アルゴリズム2選
- 3.2 ソートアルゴリズム6選
4 もっと学びたいあなたへのオススメのアルゴリズムの本
5 まとめ

アルゴリズムとは？例題を挙げてわかりやすく解説

そもそも、アルゴリズムとはなんでしょう。ここで例題をとって少し考えてみましょう。

アルゴリズムは答えを出す手順

アルゴリズムとは、答えを出す手順のことです。

課題に対して答えを出す手順自体はいくつもある場合がほとんどです。その中から、その課題にあったアルゴリズムを選ぶことが大切です。

身近な例で理解するアルゴリズム

アルゴリズムを理解するために、身近な例を用いて解説します。

例題と答え

例題：コンビニで税込108円のおにぎりを買います。財布には以下のお金が入っています。
- 100円*2枚
- 10円*2枚
- 1円*3枚
問題：どのように支払えばお釣りの小銭の枚数が最も少なくなるでしょうか？
答え：100円*1枚、10円*1枚、1円*3枚で113円払い、5円*1枚を受け取る

経験的にすぐ答えが分かった方も多いかと思います。どのように答えを出したでしょうか。

答えの出し方（アルゴリズム）

答えの出し方（アルゴリズム）は一通りではありません。例として二つのアルゴリズムをあげます。

アルゴリズム1：手持ちの小銭の全ての組合せとそれぞれのお釣りを求めて最小値を出す
アルゴリズム2：お釣りの小銭の枚数が小さくなる方から考えて、手持ちの小銭でできるか調べる。

アルゴリズム1は、明らかにお釣りが多くなる組み合わせも試すため、無駄があります。

一方アルゴリズム2は、最小値だけ見つければ良いということに注目しているので効率的です。

このように同じ問題に対するアルゴリズムでも、効率が良いものと悪いものがあります。次は、アルゴリズム同士の良し悪しを考えてみましょう。

アルゴリズムの良し悪し

アルゴリズムの評価の観点はいくつかあります。

効率の良さ（速さ）
メモリ使用量
コーディングのしやすさ

今回は、最も基本的な、アルゴリズムの「効率の良さ」に絞って解説したいと思います。

アルゴリズムの効率の良さの指標として、「計算量」という指標があります。これは、そのアルゴリズムを実行（計算）するのに、どれくらいの手間がかかるか、という指標です。

ここで、計算量は計算時間ではないことに注意しましょう。なぜなら、同じアルゴリズムでもパソコンによって実行時間が全然変わってしまい、アルゴリズムで比較することはできないからです。

そこで、計算回数がどれくらいになるかを基準とし、一般的にオーダー記法と呼ばれる表記が用いられます。

オーダー記法はアルゴリズムの対象となるデータの個数をnとした時に、計算回数がnに対してどうなるかを表します。例えば、以下のようなものがあります。

- O(1)　nによらない、つまり、データがどれだけ大きくなってもアルゴリズムの計算回数は変わらないことを表します。

- O(n) nに比例することを表します。例えば、データそれぞれに対してfor文やeach文でループするアルゴリズムがこれに当たります。

- O(log n) やや難しいですが、底を２とした対数に比例することを表します。例えば、後述の二分探索など、１回の計算ごとにデータを2等分、4等分、８等分…と分割していくようなアルゴリズムがこれに当たります。

- O(n^2) nの二乗に比例することを表します。for文などで２重のループを行うアルゴリズムがこれに当たります。

O(2^n) ２のn乗に比例することを表します。データに対して全ての組合せを調べるようなアルゴリズムがこれに当たります。指数時間アルゴリズムと呼ばれ、実用的にもとても時間が掛かるアルゴリズムになります。

知っておくべき必須アルゴリズム8選とプログラミングでの実装例

アルゴリズムは日常生活でも考えることができますが、これが会社の膨大な人員・膨大なデータになった時、

コンピューターに頼らざるをえません。この時どうしても必要なのがプログラミングになります。

例えば、シフト組みや消耗品の発注の自動化などは、アルゴリズムを考えてプログラミングをする必要があります。

逆に言えばアルゴリズムの知識とプログラミングの技術さえあれば、

手動で行われる単純作業などは、コンピューターによる自動化にしてしまうことができます。

それでは、ここからは各アルゴリズムの各言語による実装例を紹介していきます。

探索アルゴリズム2選

まずは、n個のデータから、指定された値のデータを探してくるアルゴリズムを考えてみましょう。

線形探索

一番、素朴な方法として、n個のデータを１つずつ見て、指定された値を見つけるという方法があります。一番単純な方法だと言えます。
計算量は、O(n)になります。

rubyでの実装例

def linear_search(key, input)
    find_flag = false

    for i in 0..input.length()
    	if input[i] == key
	       puts "#{key} は input[#{i}]で発見しました！"
	       find_flag = true
	       break
        end
    end
    unless find_flag
        puts "#{key} は見つかりませんでした.."
    end
    
end

input = [3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93]

linear_search(62, input)
linear_search(9, input)
linear_search(10, input)

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def linear_search(key, input):
    for i, num in enumerate(input):
        if key == num:
            print "{} はinput[{}]で発見しました！".format(key, i)
            break
    else:
        print "{} は見つかりませんでした..".format(key)


input = [3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93]

linear_search(62, input)
linear_search(9, input)
linear_search(10, input)

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define INPUT_SIZE 16
int input[INPUT_SIZE] = {3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93};

void linear_search(int key) {
  int i;
  
  int find_flag = 0;
  for(i = 0; i &amp;lt; INPUT_SIZE; i++) {
    if( input[i] == key) {
      printf("%d は input[%d] で発見しました！\n", key, i);
      find_flag = 1;
      break;
    }
  }

  if(find_flag == 0) {
    printf("%d は見つかりませんでした..\n", key);
  }
  
}


int main() {  

  linear_search(62);
  linear_search(9);
  linear_search(10);

  return 0;
}

二分探索

次は、n個のデータが左から小さい順に並んでいる場合を考えます。

線形探索と同じように、n個のデータを1つずつ見ても良いのですが、データは大きさ順に並んでいることがわかってるので、それを利用したいですね。
これを利用したアルゴリズムの一つとして、二分探索があります。

まず、全データのうち、ちょうど中央のデータを見ます。

指定された値が、中央のデータの値より大きければ、指定された値は、中央より右にあることがわかります。

一方、指定された値が中央のデータの値より小さければ、指定された値は、中央より左にあることがわかります。
どちらにせよ、探すべきデータが半分になります。

次に、半分になったデータの、ちょうど中央のデータを見て、また指定された値と比較をします。
それによって、再び探すべきデータはまた半分になります。

これを繰り返していくことで、探すべきデータを見つけます。

計算１回ごとに対象のデータが半分になるので、計算量はO(log n)となります。

rubyでの実装例

def binary_search(key, input)
  find_flag = false

  search_left = 0
  search_right = input.length() - 1
  pivot = (search_left + search_right)/2

  while search_left &amp;lt; search_right
    pivot = (search_left + search_right)/2
    if key == input[pivot]
      find_flag = true
      break
    end
    break if pivot == search_right || pivot == search_left
    search_right = pivot if key &amp;lt; input[pivot] search_left = pivot if key &amp;gt; input[pivot]
  end

  if find_flag
    puts "#{key} は input[#{pivot}]で発見しました！"
  else
    puts "#{key} は見つかりませんでした.."
  end
end

input = [3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93]

binary_search(62, input)
binary_search(9, input)
binary_search(10, input)

pythonでの実装例

def binary_search(key, input)
  find_flag = false

  search_left = 0
  search_right = input.length() - 1
  pivot = (search_left + search_right)/2

  while search_left &amp;lt; search_right
    pivot = (search_left + search_right)/2
    if key == input[pivot]
      find_flag = true
      break
    end
    break if pivot == search_right || pivot == search_left
    search_right = pivot if key &amp;lt; input[pivot] search_left = pivot if key &amp;gt; input[pivot]
  end

  if find_flag
    puts "#{key} は input[#{pivot}]で発見しました！"
  else
    puts "#{key} は見つかりませんでした.."
  end
end

input = [3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93]

binary_search(62, input)
binary_search(9, input)
binary_search(10, input)

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define INPUT_SIZE 16
int input[INPUT_SIZE] = {3, 5, 9 ,12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93};

void binary_search(int key) {
  int find_flag = 0;

  int search_left = 0;
  int search_right = INPUT_SIZE - 1;
  int pivot;
  
  while(search_left &amp;lt; search_right) {
    pivot = (search_right+search_left)/2;
    if(key == input[pivot]) {
      find_flag = 1;
      break;
    }
    if(pivot == search_right || pivot == search_left) break;
    if(key &amp;lt; input[pivot]) search_right = pivot; if(key &amp;gt; input[pivot]) search_left = pivot;

  }

  if(find_flag == 1) {
      printf("%d は input[%d] で発見しました！\n", key, pivot);
  }
  else {
    printf("%d は見つかりませんでした..\n", key);
  }
  
}

int main() {  
  
  binary_search(62);
  binary_search(9);
  binary_search(10);

  return 0;
}

ソートアルゴリズム6選

ソートとは、日本語で整列の意味で、n個のバラバラのデータを小さい順に並び替えるアルゴリズムを考えます。

バブルソート

バブルとは「泡」を指して、値の小さいデータの要素が上に浮かんでいく様子が泡のようだと例えられて名前がつきました。

ソートアルゴリズムの中でも最も直感的なアルゴリズムの一つと言えます。

バブルソートの基本的な考え方は、
下の要素を上の要素と比較して、下の方が小さければ互いに交換する。

これを、一番下の要素から順に行っていきます。
これによって一番小さな数字は一番上に上がっていきます。（これが泡のようなイメージなんですね）

次に、一番上を除いて、一番下の要素からこれを繰り返します。これによって二番目に小さな数字は二番目に上がってきます。

同様に、一番上、二番目を除いて、一番下の要素から繰り返します。これによって三番目に小さな数字は三番目に上がってきます。

これを繰り返すことで、ソート完了です！

計算量は、O(n^2)です。
ソートアルゴリズムの中では実装は容易ですが、計算量は比較的大きいアルゴリズムです。

rubyでの実装例

def bubble_sort(data)
  for i in 0..(data.length()-1)
    for j in 1.. (data.length()-i-1)
      data[j-1],data[j] = data[j],data[j-1] if data[j-1] &amp;gt; data[j]
    end
  end
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

bubble_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def bubble_sort(data):
    for i in range(0,len(data)-1):
        for j in range(1, len(data)-i):
            if data[j-1] &amp;gt; data[j]:
                data[j], data[j-1]  = data[j-1], data[j]

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

bubble_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

void bubble_sort(int* data) {
  int i,j;
  for(i = 0; i &amp;lt; DATA_SIZE; i++) {
    for(j = 1; j &amp;lt; DATA_SIZE-i; j++) { if(data[j-1] &amp;gt; data[j]) {
	int tmp = data[j-1];
	data[j-1] = data[j];
	data[j] = tmp;
      }
    }
  }
}

int main() {  
  int i;
  
  bubble_sort(data);
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

選択ソート

選択ソートは、最小値を「選択」して、それを順に並べていくアルゴリズムです。

まず、要素の中を全て見て最小値を選択します。その最小値と一番上の要素を交換します。

次に、一番上を除いた、要素の中を全て見て最小値を選択します。
これは二番目に小さい数となります。これと、二番目の要素を交換します。

次に、一番上と二番目を除いた、要素の中を全て見て最小値を選択します。
これは三番目に小さい数となります。これと、三番目の要素を交換します。

これを最後まで繰り返すことで、ソート完了です！

計算量は、O(n^2)です。
バブルソートとほとんど同じですが、バブルソートでは要素の交換を各ステップ行っていて、
選択ソートは要素の交換をループ１回につき、１回しか行わない点でやや早いと考えられます。

rubyでの実装例

def selection_sort(data)
  for i in 0..(data.length()-1)
    min_i = i
    for j in i+1.. (data.length()-1)
      min_i = j if data[min_i] &amp;gt; data[j]
    end
    data[min_i], data[i] = data[i], data[min_i]
  end
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

selection_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def selection_sort(data):
    for i in range(0,len(data)):
        min_i = i
        for j in range(i+1, len(data)):
            if data[min_i] &amp;gt; data[j]:
                min_i = j
        data[min_i], data[i] = data[i], data[min_i]

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

selection_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

void selection_sort(int* data) {
  int i,j;
  for(i = 0; i &amp;lt; DATA_SIZE; i++) {
    int min_i = i;
    for(j = i+1; j &amp;lt; DATA_SIZE; j++) { if(data[min_i] &amp;gt; data[j]) min_i = j;
    }
    int tmp = data[min_i];
    data[min_i] = data[i];
    data[i] = tmp;
  }
}

int main() {  
  int i;
  
  selection_sort(data);
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

挿入ソート

挿入ソートは、小さな整列済みのデータに対して、新たな要素を適切に「挿入」して整列済みのデータを拡大していき、全体を整列するアルゴリズムです。

まず、一番上のデータを、整列済みのデータとします。
次に、二番目のデータを、整列済みのデータ（一つしかない）と比較して、適切な位置に挿入します。
次に、三番目のデータを、整列済みのデータ（二つ）と比較して、適切な位置に挿入します。

これを繰り返して、整列済みのデータを全体まで拡大することでソート完了です！

計算量は、O(n^2)です。
バブルソートや挿入ソートと計算量は変わりませんが、対象のデータが既にある程度整列されているデータの場合、挿入する回数が少なくなることが期待されます。

rubyでの実装例

def insertion_sort(data)
  for i in 1..(data.length()-1)
    select = data[i]
    if data[i-1] &amp;gt; select
      j = i
      begin
        data[j] = data[j-1]
        j -= 1
      end while j &amp;gt; 0 &amp;amp;&amp;amp; data[j-1] &amp;gt; select
      data[j] = select
    end
  end
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

insertion_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def insertion_sort(data):
    for i in range(1,len(data)):
        select = data[i]
        if data[i-1] &amp;gt; select:
            j = i
            data[j] = data[j-1]
            j -= 1
            while j &amp;gt; 0 and data[j-1] &amp;gt; select:
                data[j] = data[j-1]
                j -= 1
            data[j] = select

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

insertion_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

void insertion_sort(int* data) {
  int i,j;
  for(i = 1; i &amp;lt; DATA_SIZE; i++) { int select = data[i]; if (data[i-1] &amp;gt; select) {
      j = i;
      do {
	data[j] = data[j-1];
	j--;
      } while(j &amp;gt; 0 &amp;amp;&amp;amp; data[j-1] &amp;gt;select);
      data[j] = select;
    }
  }
}

int main() {  
  int i;
  
  insertion_sort(data);
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

ここまでが、O(n^2)のソートアルゴリズムです。

ここからは、O(n log n)のソートアルゴリズムを紹介したいと思います。O(n^2)に比べて計算量は小さく、比較的早く実行できる一方で、

多くのアルゴリズムが関数（メソッド）の再帰的呼び出しを使うなど、技術的な部分もあり、やや実装が難しいアルゴリズムになります。

マージソート

既にソート済みの２つの配列があるとしたら、データを併合（マージ）して、新しく整列されたデータを取得するのは容易です。
マージソートは、このことを利用します。

まず初めに全データを分解してから、小さい配列を整列しながらマージを繰り返すことで、最終的に全体を整列するアルゴリズムです。

まず、全データを、要素数１の小さい配列に分解します。

二つの要素数1の配列同士をマージして整列します。
これによって要素数2のソート済みの配列が得られます。

二つの要素数2の配列同士をマージして整列します。
これによって要素数4のソート済みの配列が得られます。

これを繰り返して、全体がソート済みの配列を得ることでソート完了になります。

計算量を考えてみましょう。マージ回数は、配列の要素数が2倍、4倍、8倍…と繰り返しデータ全体とするので、log n回です。
1回のマージでn回の比較が必要なので、全体として計算量はO(n log n)となります。

rubyでの実装例

def merge_sort(data)
  def _merge(data1, data2)
    result = []
    item1 = data1[0]
    item2 = data2[0]
    while(true)
      if item1 &amp;lt; item2
        result &amp;lt;&amp;lt; data1.shift
        if data1.length() == 0
          result.concat(data2)
          break
        end
        item1 = data1[0]
      else
        result &amp;lt;&amp;lt; data2.shift
        if data2.length() == 0
          result.concat(data1)
          break
        end
        item2 = data2[0]
      end
    end
    print result
    puts
    return result
  end

  def _split(data)
    len = data.length()
    return data.each_slice(len/2).to_a
  end

  def _merge_sort(data)
    if data.length() &amp;lt;= 1
      return data
    end
    splited_array = _split(data)
    return _merge(_merge_sort(splited_array[0]), _merge_sort(splited_array[1]))
  end

  return _merge_sort(data)
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = merge_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def merge_sort(data):
    def _merge(data1, data2):
        result = []
        item1 = data1[0]
        item2 = data2[0]
        while(True):
            if item1 &amp;lt; item2:
                result.append(data1.pop(0))
                if len(data1) == 0:
                    result.extend(data2)
                    break
                item1 = data1[0]          
            else:
                result.append(data2.pop(0))
                if len(data2) == 0:
                    result.extend(data1)
                    break
                item2 = data2[0]
        return result

    def _split(data):
        length = len(data)
        data1 = data[0:length/2]
        data2 = data[length/2:length]
        return data1, data2

    def _merge_sort(data):
        if len(data) &amp;lt;= 1:
            return data
        data1, data2 = _split(data)
        return _merge(_merge_sort(data1), _merge_sort(data2))

    return _merge_sort(data)

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = merge_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

void _merge(int* data, int left, int right) {
  //left~mid-1 mid~right
  static int memory[DATA_SIZE];
  int i;
  for(i = left; i &amp;lt;= right; i++) memory[i] = data[i];

  int mid = (right+left)/2;
  int data_i = left;
  int left_i = left;
  int right_i = mid;

  while(1) {
    if(memory[left_i] &amp;lt; memory[right_i]) {
      data[data_i++] = memory[left_i++];
      if(left_i == mid) {
	for(i = right_i; i &amp;lt;= right; i++) data[data_i++] = memory[i];
	break;
      }
    }
    else {
      data[data_i++] = memory[right_i++];
      if(right_i == right+1) {
	for(i = left_i; i &amp;lt; mid; i++) data[data_i++] = memory[i];
	break;
      }
    }
  }
}

void _merge_sort(int* data, int left, int right) {
  if(left == right) return;
  int mid = (right+left)/2;
  _merge_sort(data, left, mid-1);
  _merge_sort(data, mid, right);
}


void merge_sort(int* data) {
  int i,j;
  for(i = 1; i &amp;lt; DATA_SIZE; i++) { int select = data[i]; if (data[i-1] &amp;gt; select) {
      j = i;
      do {
	data[j] = data[j-1];
	j--;
      } while(j &amp;gt; 0 &amp;amp;&amp;amp; data[j-1] &amp;gt;select);
      data[j] = select;
    }
  }
}

int main() {  
  int i;

  merge_sort(data);
  
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

クイックソート

クイックソートは、「クイック」と名がついてるだけあり、実用上は最も高速であるとされています。

1.配列の要素数が1以下なら整列済みとみなします。

2.ピボット（軸）と呼ばれる要素をその配列から選択します。（選択の方法はいろいろありますが、今回は先頭の要素を選択します。）

3.その配列全体を、ピボットより値が大きい配列、ピボットより値が小さい配列の二つに分割します。

4.手順1~5を、分割された二つの配列に対して、適用します。

5.ピボットより値が小さい配列、ピボット、ピボットより値が大きい配列　と結合して整列します。

計算量は、ピボットの選び方によって大きく依存しますが、ピボットがちょうど中央値に選ばれ、分割がちょうど二等分になると仮定すれば、分割回数はlog n回です。
分割をするために、ピボットとの比較がn回行われるので、全体として計算量はO(n log n)となります。

rubyでの実装例

def quick_sort(data)
  def _quick_sort(data)
    if data.empty?
      return data
    end
    pivot = data[0]
    left = []
    right = []
    for i in 1..data.length()-1
      if data[i] &amp;lt;= pivot
        left &amp;lt;&amp;lt; data[i]
      else
        right &amp;lt;&amp;lt; data[i]
      end
    end
    left = _quick_sort(left)
    right = _quick_sort(right)
    return left + [pivot] + right
  end

  return _quick_sort(data)
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = quick_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def quick_sort(data):
    def _quick_sort(data):
        if len(data) == 0:
            return data
        pivot = data[0]
        left = []
        right = []
        for i in range(1, len(data)):
            if data[i] &amp;lt;= pivot:
                left.append(data[i])
            else:
                right.append(data[i])
        left = _quick_sort(left)
        right = _quick_sort(right)
        return left + [pivot] + right

    return _quick_sort(data)
    
data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = quick_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

void _quick_sort(int* data, int left, int right) {
  int pivot = data[left];
  int l_hold = left;
  int r_hold = right;
  while(left &amp;lt; right) { while((data[right] &amp;gt;= pivot) &amp;amp;&amp;amp; (left &amp;lt; right)) right--;
    if(left != right) {
      data[left] = data[right];
      left++;
    }
    while((data[left] &amp;lt;= pivot) &amp;amp;&amp;amp; (left &amp;lt; right)) left++;
    if(left != right) {
      data[right] = data[left];
      right--;
    }
  }
  data[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left &amp;lt; pivot) _quick_sort(data, left, pivot-1); if (right &amp;gt; pivot) _quick_sort(data, pivot+1, right);
}

void quick_sort(int* data) {
  _quick_sort(data,0,DATA_SIZE-1);
}
    

int main() {  
  int i;

  quick_sort(data);
  
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

ヒープソート

ヒープ構造とは、木構造の一種で、二分木の各節点にデータの値を保存して、親のデータが二つの子のデータよりも小さくなるように作れられたデータ構造です。

ここで重要なことは、一番の親（「根」と言います）は、必ず最小値のデータになるという点です。

ヒープソートとは、まず、与えられたデータでヒープ構造をつくります。

「根」を取り出して、残りのデータでヒープ構造を作り、また「根」を取り出すということを繰り返すというアルゴリズムです。

計算量は、ヒープ構造を作るのにlog n回の計算、「根」の取り出しはn回の計算なので、全体として計算量はO(n log n)となります。

rubyでの実装例

def left(i)
  return i*2+1
end

def right(i)
  return i*2+2
end

def parent(i)
  return (i-1)/2
end

def heapify(data)
  start = (data.length()-1)/2
  until start &amp;lt;= 0
    i = start
    while true
      if left(i) &amp;lt; data.length() &amp;amp;&amp;amp; data[i] &amp;gt; data[left(i)]
        data[i], data[left(i)] = data[left(i)], data[i]
      end
      if right(i) &amp;lt; data.length() &amp;amp;&amp;amp; data[i] &amp;gt; data[right(i)]
        data[i], data[right(i)] = data[right(i)], data[i]
      end
      if i == 0
        break
      end
      i = parent(i)
    end
    start -= 1
  end
  return data
end

def heap_sort(data)
  result = []
  data = heapify(data)
  for i in 0..data.length()-1
    result &amp;lt;&amp;lt; data.shift
    data = heapify(data)
  end
  return result
end

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = heap_sort(data)

print data
puts

pythonでの実装例

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def left(i):
    return i*2+1

def right(i):
    return i*2+2

def parent(i):
    return (i-1)/2

def heapify(data):
    last = (len(data)-1)/2
    for i in range(last,0,-1):
        while True:
            if left(i) &amp;lt; len(data) and data[i] &amp;gt; data[left(i)]:
                data[i], data[left(i)] = data[left(i)], data[i]
            if right(i) &amp;lt; len(data) and data[i] &amp;gt; data[right(i)]:
                data[i], data[right(i)] = data[right(i)], data[i]
            if i == 0:
                break
            i = parent(i)
    return data

def heap_sort(data):
    result = []
    data = heapify(data)
    for i in range(len(data)):
        result.append(data.pop(0))
        data = heapify(data)
    return result

data = [42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69]

data = heap_sort(data)

print data

Cでの実装例

#include &amp;lt;stdlib.h&amp;gt;
#include &amp;lt;stdio.h&amp;gt;

#define DATA_SIZE 16
int data_size = DATA_SIZE;
int data[DATA_SIZE] = {42, 21, 10, 2, 30, 51, 80, 90, 18, 56, 50, 25, 15, 95, 44, 69};

int left(int i) {
  return i*2+1;
}

int right(int i) {
  return i*2+2;
}

int parent(int i) {
  return (i-1)/2;
}

void heapify(int* data) {
  int i,start;
  for(start = (data_size-1)/2; start &amp;gt; 0; start--) {
    i = start;
    while(1) {
      if(left(i) &amp;lt; data_size &amp;amp;&amp;amp; data[i] &amp;gt; data[left(i)]) {
	int tmp = data[i];
	data[i] = data[left(i)];
	data[left(i)] = tmp;
      }
      if(right(i) &amp;lt; data_size &amp;amp;&amp;amp; data[i] &amp;gt; data[right(i)]) {
	int tmp = data[i];
	data[i] = data[right(i)];
	data[right(i)] = tmp;
      }
      if(i == 0) break;
      i = parent(i);
    }
  }
}

void heap_sort(int* data) {
  int i;
  int tmp[DATA_SIZE];
  for(i = 0; i &amp;lt; DATA_SIZE; i++) {
    tmp[i] = data[i];
  }
  heapify(tmp);
  for(i = 0; i &amp;lt; DATA_SIZE; i++) {
    data[i] = tmp[0];
    tmp[0] = tmp[--data_size];
    heapify(tmp);
  }
}

int main() {  
  int i;

  heap_sort(data);
  
  for(i = 0; i &amp;lt; DATA_SIZE; i++) printf("%d, ", data[i]);
  printf("\n");
  return 0;
}

この記事のハッシュタグ