挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がと もにO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート – Wikipedia より

C++による実装

#include <iostream>

using namespace std; 

int main() {
  int key;
  int i, j, n = 9;
  int arr[] = {6,5,1,10,11,23,30,2,7};

  for (i = 1; i < n; i++) {
    key = arr[i];
    for (j = i; j > 0 && arr[j-1] > key; --j) {
        arr[j] = arr[j-1];
    }
    arr[j] = key;
  }

  // 結果の出力
  for (i = 0; i < n; i++)
    cout << arr[i] << endl;

  return 0;
}

出力結果

1
2
5
6
7
10
11
23
30

参考書籍

数学的基礎とデータ構造 (アルゴリズムイントロダクション) Thomas H. Cormen 近代科学社 2007-03 売り上げランキング : 127547 おすすめ平均 Amazonで詳しく見る

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション) Thomas H. Cormen 近代科学社 2007-03 売り上げランキング : 148392 おすすめ平均 Amazonで詳しく見る

ダイクストラ法とは

ダイクストラ法はグラフ上の2頂点間の最短経路を効率的に求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 なお最短経路の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的 に最短経路を求める事ができる。

ダイクストラ法 – Wikipediaより

実装

もうちょっと綺麗に書いた方がいいなぁ。。

#include <vector>

using namespace std; 

#define MAX_VALUE 999999
int n = 6;
vector<vector<int> > graph(n, vector<int>(n));

void setGraph(int x, int y, int distance) {
  graph[y][x] = distance;
  graph[x][y] = distance;
}

void readGraph() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      graph[i][j] = MAX_VALUE;
  setGraph(0, 1, 6);
  setGraph(0, 2, 10);
  setGraph(1, 2, 2);
  setGraph(1, 3, 8);
  setGraph(2, 4, 4);
  setGraph(3, 4, 1);
  setGraph(3, 5, 1);
  setGraph(4, 5, 3);
}

void dijkstra(void) {
  int min = MAX_VALUE;

  int preview[6];
  bool visited[6];
  int distance[6];

  for (int i = 0; i < n; i++)
    visited[i] = false, distance[i] = MAX_VALUE;
  distance[0] = 0;
  preview[0] = 0; 

  int next = 0, p = 0;

  do {
    p = next;
    visited[p] = true;
    min = MAX_VALUE;

    for (int j = 0; j < n; j++) {
      if (visited[j]) continue;
      if (graph[p][j] < MAX_VALUE &&
          distance[p] + graph[p][j] < distance[j]){
        distance[j] = distance[p] + graph[p][j];
        preview[j] = p;
      }
      if (distance[j] < min) {
        next = j;
        min = distance[j];
      }
    }
  } while (min < MAX_VALUE);

  cout << "point" << " preview" << " distance" << endl;
  for (int i = 0; i < n; i++) {
    cout << i << "      " << preview[i] << "        " << distance[i] << endl;
  }
}

int main() {
  readGraph();
  dijkstra();
  return 0;
}

実行結果

point preview distance
0      0        0
1      0        6
2      1        8
3      4        13
4      2        12
5      3        14

参考リンク

1. ダイクストラ法（最短経路問題）

参考文献

Javaによるアルゴリズム事典 技術評論社 2003-05 売り上げランキング : 202576 Amazonで詳しく見る

幅優先探索とは

幅優先探索(Breadth first search) はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられる。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

幅優先探索 – Wikipediaより

実装

幅優先探索をC++で実装してみる。

#include <vector>
#include <queue>
#include <iostream>

using namespace std; 

int n = 6;

void setGraph(vector<vector<char> > &map, int x, int y) {
  map[y][x] = 1;
  map[x][y] = 1;
}

vector<vector<char> > readMap() {
  vector<vector<char> > map(n, vector<char>(n));
  setGraph(map, 0, 1);
  setGraph(map, 0, 2);
  setGraph(map, 1, 3);
  setGraph(map, 2, 3);
  setGraph(map, 3, 4);
  setGraph(map, 3, 5);
  return map;
}

int main(void) {
  vector<vector<char> > map = readMap();
  vector<int> distance(n), preview(n);
  vector<bool> visited(n);

  for (int i = 0; i < n; i++) {
    visited[i] = false;
    distance[i] = 0;
  }

  queue<int> q;
  int START = 0;
  q.push(START);
  visited[START] = true;
  while (!q.empty()) {
    int i = q.front();
    q.pop();

    for (int j = 0; j < n; j++) {
     if (map[i][j] == 1 && visited[j] == false) {
      distance[j] = distance[i] + 1;
      visited[j] = true;
      preview[j] = i;
      q.push(j);
     }
    }
  }

  cout << "point" << " preview" << " distance" << endl;
  for (int i = 0; i < n; i++) {
    cout << i + 1 << "    " << preview[i] + 1 << "     " << distance[i] << endl;
  }
  return 0;
}

実行結果

point preview distance
1     1       0
2     1       1
3     1       1
4     2       2
5     4       3
6     4       3

関連リンク

• 幅優先探索 – Wikipedia