挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がと もに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で詳しく見る