アルゴリズムとデータ構造まとめその2 サーチ

はじめに

この記事は著者が学習書の内容を備忘録としてまとめたものです。
前
次
第二回の今回はサーチについてまとめます。

サーチ概要

サーチとはデータの中から、ある値と一致する値を持つものを探すことであり、主な手法は以下の2つである。

リニアサーチ

概要

最もシンプルな手法で、データを先頭から一つずつ確認していく。O(N)。 　 実際には、次回の記事で説明する自己組織化探索にする。

コード

int linear_search(int x, int *a, int num){
  int n = 0, t;
  // 番人
  t = a[num - 1];
  a[num - 1] = x;
  while(n < num && a[n] != x){
    n++;
  }

  a[num - 1] = t;
  if(n < num - 1){
    return n;
  }
  if(x == t){
    return n;
  }

  return NOT_FOUND;
}

バイナリサーチ

概要

クイックソートの逆バージョンのようなサーチ法。既にソートされているデータに対して、二分探索を繰り返してサーチを行う。O(logN)。

コード

int binary_search(int x, int *a, int left, int right){
  int mid;
  while(left < right){
    mid = (left + right) / 2;
    if(a[mid] < x){
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  if(a[left] == x){
    return left;
  }

  return NOT_FOUND;
}

アルゴリズムとデータ構造まとめその1 ソート

はじめに

この記事は著者が学習書の内容を備忘録としてまとめたものです。
次
第一回目の記事である今回はソートについてのまとめです。

バブルソート

概要

先頭から最後まで順に見ていき一つずつ順番に入れ替え、入れ替えがなくなるまで周回を繰り返していく方法である。計算量はO(N)で安定なソートである。
実際には「ループが一回終了するごとに、配列の後方要素は確実にソート済みになっている」という性質を利用し計算量はO(N²/2)になる。

コード

void BubbleSort(){
  int i, temp, flag, k = 0;

  do {
    flag = 0;
    for(i = 0; i < N - k - 1; i++){
      if(sort_list[i] > sort_list[i+1]){
        flag = 1;
        temp = sort_list[i];
        sort_list[i] = sort_list[i+1];
        sort_list[i + 1] = temp;
      }
    }
    k++;
  } while(flag == 1);
}

クイックソート

概要

ある値を決め、それ以下とそれ以上の2グループに分ける。さらにそのグループをそれぞれ最初と同様の方法で二分し、これをグループ分けできなくなるまで繰り返すことで分類する方法である。計算量はO(N²)~O(NlogN)で、不安定なソートである。

コード

void quick_sort(int bottom, int top, int *data){
  int lower, upper, div, temp;
  if(bottom >= top){
    return;
  }
  div = data[bottom];
  for(lower = bottom, upper = top; lower < upper;){
    while(lower <= upper && data[lower] <= div){
      lower++;
    }
    while(lower <= upper && data[upper] > div){
      upper--;
    }
    if(lower < upper){
      temp = data[lower];
      data[lower] = data[upper];
      data[upper] = temp;
    }
  }
  temp = data[bottom];
  data[bottom] = data[upper];
  data[upper] = temp;

  quick_sort(bottom, upper-1, data);
  quick_sort(upper+1, top, data);
}

再帰を用いている。ちなみに、C標準ライブラリにも同様の関数qsortというものがある。

マージソート

概要

まず要素を最小単位まで分類し、その後ソートしながら要素を二つずつ合成していく分類法であり、計算量はO(NlogN)で安定なソートである。8＊1→4＊2→2＊4→1＊8→2＊8→4＊2→8＊1というふうに推移していくイメージ。

コード

void merge_sort(int n, int x[]){
  int i, j, k, m;

  if(n <= 1){
    return;
  }

  m = n / 2;
  merge_sort(m, x);
  merge_sort(n - m, x + m);

  for(i = 0; i < m; i++){
    buffer[i] = x[i];
  }
  j = m;
  i = k = 0;
  while( i < m && j < n){
    if(buffer[i] <= x[j]){
      x[k++] = buffer[i++];
    } else {
      x[k++] = x[j++];
    }
  }
  while(i < m){
    x[k++] = buffer[i++];
  }
}

ブログ開設

主に備忘録兼思考の整理用