基本的なソートアルゴリズムまとめ＋α。C言語での実装例

2016/07/18追記
CountingSortについて誤りがあったため訂正しました

#ソートアルゴリズム全般考察

典型的なソートアルゴリズムでは、最善で $O(n log n)$ 、最悪で $O(n^2)$ である。理想は $O(n)$ である。
比較ソートでは、必ず $O(n log n)$ の比較が必要となる。
汎用手法による分類。挿入、交換、選択、マージなどがある。
Wikipedia https://ja.wikipedia.org/wiki/ソート

授業で習った基本的なソートアルゴリズムをまとめたいと思います。
実際はライブラリを使うかもしれませんが、内部を知っていて損はないので覚書です。

#まとめるソートアルゴリズム

• バブルソート
• 選択ソート
• Counting Sort
• マージソート
• クイックソート
• 奇偶転置ソート

##バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間が$O(n^2)$と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）
Wikipedia https://ja.wikipedia.org/wiki/バブルソート

要するに横同士の大小を比較交換をひと通りして、さらにそれを配列の要素数回行いますよってことですね。非常にシンプルでわかりやすく、誰もが最初に思いつくアルゴリズムかなーと思います。

###疑似コード

bubblesort(N)
  for i = 0 to N.length-1
    for j = N.length-1 downto i+1
      if N[j] < N[j-1]
        swap N[j] and N[j-1]

###Cでの実装例

int* bubbleSort(int* N, int len){
  int i,j;

  for(i=0; i<len; i++){
    for(j=len-1; j>i; j--){
      if(N[j] < N[j-1]){
        temp = N[j];
        N[j] = N[j-1];
        N[j-1] = temp;
      }
    }
  }
  
  return N;
}

##選択ソート

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間が$O(n^2)$と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。安定ソートではない。
Wikipedia https://ja.wikipedia.org/wiki/選択ソート

配列中の最小を選択して、それを左端（正確にはキーの場所）に移動させます。ってアルゴリズムですね。わかりやすいです。

###疑似コード

SelectionSort(A)
for i = 0 to A.length-1
  mini = i
  for j = i to A.length-1
    if A[j] < A[mini]
        mini = j
  swap A[i] and A[mini]

###Cでの実装例

int selectionSort(int len, int *a){
  int i, j, mini, tmp, count=0;
    
  for(i=0; i<len; i++){
    mini = i;
 
    for(j=i+1; j<len; j++){
      if(a[j] < a[mini]){
        mini = j;
      }
    }
 
    if(mini != i){
      tmp = a[i];
      a[i] = a[mini];
      a[mini] = tmp;
      count++;
    }
 
  }
  return count;
}

##Counting sort

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.
Wikipedia https://en.wikipedia.org/?title=Counting_sort

worst case: $O(n)$

英語のWikiしか見つかりませんでした。
http://www.codereading.com/algo_and_ds/algo/counting_sort.html
このページが見やすく、理解しやすいですね

データの出現回数を数えて、小さい方から並べましたってソートです。わりとわかりやすいかなと思います。コードは少し読みづらいです。

###疑似コード

Counting-Sort(A, B, k)
  for i = 0 to k
    do C[i] = 0
  for j = 1 to length[A]
    do C[A[j]] = C[A[j]]+1
  /* C[i] now contains the number of elements equal to i */
  for i = 1 to k
  do C[i] = C[i] + C[i-1]
  /* C[i] now contains the number of elements less than or equal to i */
  for j = length[A] downto 1
   do B[C[A[j]]] = A[j]
   C[A[j]] = C[A[j]]-1

###Cでの実装例

#include <stdio.h>
  
#define N 2000001
  
int B[N], C[N];

void countingSort(int A[], int B[], int k, int n){
  int i, j;
    
  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }   
  for(i = 1; i <= k; i++){
    C[i] = C[i] + C[i - 1];
  } 
  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
    
  for(i = 1; i <= n; i++){
    printf("%d", B[i]);
    if(i != n) printf(" ");
  }
  printf("\n");
 
}

int main(){
  int A[N];
  int i, j, n, k = 0;
    
  //input
  scanf("%d", &n); 
  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }
    
  //sort and out
  countingSort(A, B, k, n);
    
  return 0;
}

##マージソート

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
$n$個のデータを含む配列をソートする場合、最悪計算量$O(n log n)$である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常$O(n)$の外部記憶を必要とする
Wikipedia https://ja.wikipedia.org/wiki/マージソート

マージソートを実装する場合、まず最初に分割、その後また結合という作業が必要になります。結合する過程で配列がソートされてゆきます。
以下コードでは再帰を用いて長い配列を分割し、同じように再帰でマージを行っています。

###疑似コード

Merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  create array L[0...n1], R[0...n2]
  for i = 0 to n1-1
    do L[i] = A[left + i]
  for i = 0 to n2-1
    do R[i] = A[mid + i]
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

MergeSort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

###Cでの実装例

#include<stdio.h>
#include<stdlib.h>
 
#define SENTINEL 1000000000
 
int count=0;
 
void mergeSort(int A[],int left,int right){
  int i,mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}
 
 
 
void merge(int A[],int left,int mid,int right){
  int n1,n2,i,j,k;
  int *L,*R;
  n1=mid-left;
  n2=right-mid;
  L=(int *)malloc(sizeof(int)*(n1+1));
  R=(int *)malloc(sizeof(int)*(n2+1));
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[mid+j];
  }
  L[n1]=SENTINEL;
  R[n2]=SENTINEL;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
   if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
    else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
  free(L);
  free(R);
}
 
 
main(){
  int A[500000];
  int n,i;
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A,0,n);
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i<n-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}

##クイックソート

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
最良計算量および平均計算量は$O( n log n )$である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量は$O( n^2 )$である。また数々の変種がある。 安定ソートではない。
Wikipedia https://ja.wikipedia.org/wiki/クイックソート

配列の1番目の要素以上のものを左から探します、未満のものを右から探します
左右で１つづつ見つかったら、交換します。さらに探索は続きます。
左右のキーがぶつかったらその位置で左右に処理を分け、内部で完全にソートされるまで同じ処理を繰り返します。

このURLが参考になるでしょう
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

以下コードでは再帰を使用しています

###疑似コード

Partition(A, p, r)
  x = A[r]
  i = p-1
  for j = p to r-1
    do if A[j] <= x
      then i = i+1
        exchange A[i] and A[j] 
  exchange A[i+1] and A[r]
  return i+1


Quicksort(A, p, r)
  if p < r
    then q = Partition(A, p, r)
      run Quicksort(A, p, q-1)
      run Quicksort(A, q+1, r)

###Cでの実装例(Wikipediaより)

typedef int value_type; /* ソートするキーの型 */
 
value_type med3(value_type x, value_type y, value_type z)
/* x, y, z の中間値を返す */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}
 
void quicksort(value_type a[], int left, int right)
/* クイックソート
 * a     : ソートする配列
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            i++; j--;
        }
        quicksort(a, left, i - 1);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right); /* 分割した右を再帰的にソート */
    }
}

##奇偶転置ソート

奇偶転置ソート（きぐうてんちソート、Odd-even Sort）は、ソートのアルゴリズムの一つで、バブルソートを、改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートではペアごとに行う。
バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量は$O(n^2)$である。
ペアの比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。
Wikipedia https://ja.wikipedia.org/wiki/奇偶転置ソート

なんだか名前がやたらとかっこいいので入れてみました。
アルゴリズムはこうなっている模様。

奇偶置換ソートは、奇数番目とその次の偶数番目をペア (Pair1) にして比較／交換した後、偶数番目とその次の奇数番目をペア (Pair2) にして比較／交換することを繰り返すアルゴリズムである。
Pair1:（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後に
Pair2:（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。これを繰り返す。
Wikipedia https://ja.wikipedia.org/wiki/奇偶転置ソート

###疑似コード

###Cでの実装例（Wikipediaより）

int data[N] = { /* ... */ };
  int flag = 1;
  int i;
 
  while(flag) {
    flag = 0;
    for (i = 0; i < N-1; i += 2) { /* Pair1 */
      if (data[i] > data[i+1]) {
        swap(&data[i], &data[i+1]);
        flag = 1;
      }
    }
    for (i = 1;i < N-1;i += 2) { /* Pair2 */
      if (data[i] > data[i+1]) {
        swap(&data[i], &data[i+1]);
        flag = 1;
      }
    }
  }

#まとめ、考察
各アルゴリズムの良い所、悪いところがよくわかりますね。

###読みやすさ
　バブルソート > 選択ソート > 奇偶転置ソート > クイックソート > マージソート > Counting Sort
　これは完全主観ですね

###計算量

• WorstCaseでの比較

　Counting Sort > クイックソート >= マージソート > 選択ソート >= 奇偶転置ソート >= バブルソート

　バブルソート：$O(n^2)$
　奇偶転置ソート：$O(n^2)$
　選択ソート：$O(n^2)$
　CountingSort：$O(n)$
　マージソート：$O(n log n)$
　クイックソート：$O(n^2)$
　クイックソートの比較に中央値を使った場合WorstCaseは$O(n log n)$となります。

• データの並びに対する計算量分布を考慮

　Counting Sort > マージソート >= クイックソート > 選択ソート >= 奇偶転置ソート >= バブルソート

　バブルソート：最悪、最良共に$O(n^2)$
　奇偶転置ソート：最悪、最良共に$O(n^2)$
　選択ソート：最悪、最良共に$O(n^2)$
　CountingSort：最悪、最良共に$O(n)$の為最速
　マージソート：最悪、最良共に$O(n log n)$の為極めて高速
　クイックソート：平均計算時間が$O(n log n)$の為極めて高速

###必要なメモリ量
　Counting Sort > マージソート > クイックソート > 選択ソート = 奇偶転置ソート = バブルソート
　
　バブルソート：$O(1)$
　奇偶転置ソート；$O(1)$
　選択ソート：$O(1)$
　CountingSort：$O(k)$ $k$はデータの範囲
　マージソート：$O(n)$
　クイックソート：$O(logn)$

　CountingSortはデータの範囲が初めからわかっている且つ、
　その範囲を網羅するメモリが必要です。

###速さ
　マシンスペックに依存する部分も多いです。
　例えばCountingSortは圧倒的に最速ですが、
　値の範囲次第で尋常じゃないメモリ量が必要です。

　また、マージソートとクイックソートでは
　小さなデータではマージソートが速く、
　著しく大きなデータではクイックソートが速いと言われています。
　実際他の方が実験したものでもそのように結果がでていました。

##結局何が最強なんだろ
巷ではクイックソートが最速と言われてます

平仮名など単純で値の範囲が決まっている場合最速：CountingSort
著しくデータ量（容量）が大きい物：QuickSort
著しくデータ量（容量）が大きくないもの：MargeSort

#あとがき（2016/07/18追記）
日本語Wikipediaに情報がないのでメジャーや基本的とは言い辛いですが
CountingSortってすごい強いんじゃないかなって思いました。
多くの場合データ範囲は断定できますし、データ量はメモリ使用量にほぼ関わりません。
その上圧倒的に最速です。
ただし、データ範囲が間違っていると正しい結果とならない為注意が必要です。
また、範囲が広い場合小さなデータでも大量のメモリが必要です。
あとは、実装する際範囲を網羅したカウンタが必要なため、離散的なものにはいいですが、連続的なものには使いづらいかもしれません。

最後に間違っている部分があればすいません。

#参考Web
AizuOnlineJudge http://judge.u-aizu.ac.jp/onlinejudge/index.jsp
Wikipedia https://ja.wikipedia.org/wiki/メインページ