アルゴリズムとデータ構造まとめその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++];
  }
}