ソートアルゴリズム（クイックソートとマージソート）

データ列のソートアルゴリズムの中で、速いとされているクイックソートとマージソートをC言語で実装してみます。クイックソートはC言語のライブラリにあるqsort()で使用されているということですが、条件によって計算量が増加してしまいます。それに対する対策もさまざまな実装があるようです。マージソートは計算量は一定であり、安定して速いと言われていますが、処理過程においてワークメモリを使用する必要があります。<br>

#### クイックソートの実装
クイックソートは、Charles Antony Richard Hoareが考案したアルゴリズムである。<br>
クイックソートの動作は、データ列をある値（ピボット）より小さい値のデータ列と大きい値のデータ列に分離し、分離したデータ列に対してまた、ある値（ピボット）より小さい値のデータ列と大きい値のデータ列に分離するという操作を、データ列の要素が1つになるまで繰り返す。<br>
<br>
![quick_sort.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/ba7f5601-4b68-4115-8873-d43bbef18e2d.jpeg)<br>
アルゴリズムが[https://dl.acm.org/doi/pdf/10.1145/366622.366644](https://dl.acm.org/doi/pdf/10.1145/366622.366644)に記載されているので、ほぼその通りに（C言語で）実装する。引数は、データ列 array[]、ソート範囲の左端 m、ソート範囲の右端 nである（arra[m] ～ array[n] をソートする）。<br>
```
void quick_sort(int array[], int m, int n) {
  if (m >= n) {
    return;
  }
  /***データ列の分割（partition）***/
  quick_sort(array, m, j);
  quick_sort(array, j + 1, n);
}
```
データ列の分割は、データ列（array[m] ～ array[n]）をピボットより小さい値のデータ列（array[m] ～ array[j]）とピボットより大きい値のデータ列（array[j+1] ～ array[n]）に分割する。アルゴリズムの説明が[Hoare's partition algorithm](https://www.geeksforgeeks.org/hoare-s-partition-algorithm/)にあるので、これもその通りに実装する。<br>
```
  /* partition */
  int p = array[m];             // consider the first element as pivot
  int i = m, j = n;             // i = left most, j = right most
  while (1) {
    while (array[i] < p) i++;   // until greater than or equal to pivot
    while (array[j] > p) j--;   // until less than or equal to pivot
    if (i >= j) {               // pointers cross -> partitioning complete
      break;
    }
    int tmp = array[i];         // swap left element and right element
    array[i] = array[j];
    array[j] = tmp;
    i++; j--;
  }                             // partition m to j and j+1 to n
```
ただし、iとjについては、i + 1 = j の関係でなければならないので、j のみを使って実装した。また、
上記実装例では、<br>
```
int i = -1;
while () {
  do {
    i++;
  } while ();
  swap();
}
```
のようにしているが、ここでは、<br>
```
int i = 0;
while () {
  while () i++;
  swap();
  i++;
}
```
のように実装した。このアルゴリズムの説明では、ピボットをデータ列の先頭の値にしているので、これもそのまま実装した。このアルゴリズムの動作は、<br>
<br>
![partition.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/bb4a54a1-8983-44cc-9010-6bc8aa176465.jpeg)<br>
のようになる。<br>

1. iを左端からピボット以上の値がデータ列に現れるまでインクリメントし、jを右端からピボット以下の値がデータ列に現れるまでデクリメントする。
2. iとjが一致または交差していなければ、iの位置のデータはpivot以上の値なので右側のデータ列に、jの位置のデータはpivot以下の値なので左側のデータ列に移動するために、swapする。
3. i と j が一致または交差するまで、1. 2.を繰り返す。

要素数N個のデータ列をソートする場合、データ列を2つに分割するのを繰り返すのにlogN回、分割する操作（partition）にN回（左からの検索と右からの検索が同じ位置に達するまで）であるから、計算量は N×logN 回となる。ただし、2つに分解する操作で、1個とN-1個のような分割になってしまうと、N個のデータを分割する操作にN-1回かかることになり、最悪条件ではN<sup>2</sup>回の計算量になってしまう。<br>

#### マージソートの実装
マージソートは、データ列を分割し、分割したデータ列をソートした後で、データをマージする際に小さい値から順番にマージしていくことで、データ列をソートする。<br>
<br>
![merge_sort.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4054118/2d13996d-c19a-421e-8996-fdb1982fde34.jpeg)<br>
データ列の分割は、分割した要素が1個になるまで、左半分と右半分に2分割することを繰り返す。データの分割ができたら、データ列のマージを繰り返していく。マージする際には次の手順で行う。

1. 2つのデータ列の先頭のデータを比較して、小さい方の値をマージする。
2. マージした値は元のデータ列から取り除く。
3. 1.と2.を繰り返して、2つのデータ列の値すべてを1つのデータ列にマージする。

この手順では、マージする前の2つのデータ列がソートされている必要があるが、データ列の分割で要素数が1個になるまで分割している（要素数が1個のデータ列はソート済みである）ので、上記の手順でマージを繰り返していくことで、常にソート済みのデータ列をマージしていくことができる。<br>
この手順を実装してみる。merge_sort() 関数は、データ列 array[] とデータ列の要素の個数 n を引数にとる。関数の中で、データ列を2分割したデータ列を引数として、merge_sort() を再帰的に呼び出し、関数から戻ってきた（2分割したデータ列がソートされてきた）後で、1つのデータ列にマージする。<br>
```
void merge_sort(int array[], int n) {
  if (n == 1) {                         // no need to sort
    return;
  }
  int mid = n / 2;
  merge_sort(array, mid);               // sort left half
  merge_sort(array + mid, n - mid);     // sort right half
  /*** データ列をマージ（merge） ***/
}
```
マージの実装は以下の通り。<br>
```
  /* merge */
  int sorted[n];                        // merge into here
  int li = 0, ri = mid;
  for (int i = 0; i < n; i++) {         // merge sorted arrays
    if (li == mid) {                    // left half end
      sorted[i] = array[ri++];          // merge right half
    } else if (ri == n) {               // right half end
      sorted[i] = array[li++];          // merge left half
    } else {
      if (array[li] < array[ri]) {      // merge smaller of left or right
        sorted[i] = array[li++];
      } else {
        sorted[i] = array[ri++];
      }
    }
  }
  for (int i = 0; i < n; i++) {         // revise array with merged
    array[i] = sorted[i];
  }
```
データ列は、array[0] ～ array[mid-1] と arra[mid] ～ array[n-1] の2つのソート済みデータ列が与えらえてている。したがって、一方のデータ列の先頭の位置は li = 0、もう一方のデータ列の先頭の位置は ri = mid である。要素の合計数nに対して、i = 0～ n-1 について、array[li]とarray[ri]の小さい方を sorted[i] に入れて、入れた方のインデックス(li または ri ）を 1 増やす。どちらかのデータ列の要素をすべてマージしてしまったら、残っているデータ列の値をマージしていく。<br>

#### 速度比較
データ個数20000のデータ列（乱数で発生させたものと降順に並べたもの）に対して、quick_sort()、merge_sort() それぞれ3回ずつ<br>
```
$ time ./a.exe < in.dat > out.dat
```
のコマンドで時間を計測した。実行プログラムは、<br>
```
int main() {
  int n;
  scanf("%d", &n);
  int array[n];
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    array[i] = x;
  }
  quick_sort(array, 0, n - 1);
  /* merge_sort(array, n); */
  for (int i = 0; i < n; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
  return 0;
}
```
である。では、結果。<br>
<br>

- 乱数20000個のデータ列の場合<br>

|quick_sort      |                |                |merges_sort     |                |                |
| ----           | ----           | ----           | ----           | ----           | ----           |
|1回目           |2回目           |3回目           |1回目           |2回目           |3回目           |
| ----           | ----           | ----           | ----           | ----           | ----           |
|real    0m0.116s|real    0m0.115s|real    0m0.115s|real    0m0.114s|real    0m0.102s|real    0m0.115s|
|user    0m0.031s|user    0m0.031s|user    0m0.015s|user    0m0.000s|user    0m0.015s|user    0m0.015s|
|sys     0m0.000s|sys     0m0.000s|sys     0m0.015s|sys     0m0.062s|sys     0m0.015s|sys     0m0.031s|


- 降順の20000個のデータ列の場合<br>

|quick_sort      |                |                |merges_sort     |                |                |
| ----           | ----           | ----           | ----           | ----           | ----           |
|1回目           |2回目           |3回目           |1回目           |2回目           |3回目           |
| ----           | ----           | ----           | ----           | ----           | ----           |
|real    0m0.498s|real    0m0.482s|real    0m0.482s|real    0m0.115s|real    0m0.101s|real    0m0.102s|
|user    0m0.031s|user    0m0.000s|user    0m0.000s|user    0m0.015s|user    0m0.015s|user    0m0.015s|
|sys     0m0.031s|sys     0m0.015s|sys     0m0.015s|sys     0m0.032s|sys     0m0.015s|sys     0m0.000s|

今回実装した quick_sort() では、ピボットをデータ列の最初の値にしているため、降順（あるいは昇順）のデータ列だと、1個 vs 残り個数、で分割されてしまうので、quick_sort() は遅くなっている。<br>
<br>
バブルソートで同じデータをソートしてみた。その結果はこちら。<br>

|乱数データ        |                |                |降順データ        |                |                |
| ----           | ----           | ----           | ----           | ----           | ----           |
|1回目           |2回目           |3回目           |1回目           |2回目           |3回目           |
| ----           | ----           | ----           | ----           | ----           | ----           |
|real    0m1.232s|real    0m1.195s|real    0m1.213s|real    0m0.896s|real    0m0.894s|real    0m0.874s|
|user    0m0.015s|user    0m0.015s|user    0m0.015s|user    0m0.031s|user    0m0.031s|user    0m0.031s|
|sys     0m0.000s|sys     0m0.046s|sys     0m0.015s|sys     0m0.015s|sys     0m0.015s|sys     0m0.031s|

バブルソートのコードはこちら。<br>
```
void bubble_sort(int array[], int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (n-1) - i; j++) {
      if (array[j] > array[j+1]) {
        int tmp = array[j];
        array[j] = array[j+1];
        array[j+1] = tmp;
      }
    }
  }
}
```