---
# System prepended metadata

title: Untitled

---

## アルゴリズムとデータ構造およびプログラミング演習
**レポート13 2019/01/31提出**
<p style="text-align: right;font-size:24px">
<b>1810128 - 大谷 孟宏</b>
</p>

*(特に記載がない場合、コンパイラはsol上のccを使用している。実行結果もsol上によるものである。)*
### 課題13.1
入力データ：
```
a[0]= 0 a[1]=52 a[2]= 6 a[3]=23 a[4]=58 a[5]=17 a[6]=41 a[7]=35 a[8]=63
```
#### ステップ1
##### 第1ポーズ
このポーズの開始時点でのa[i]：
```
a[0]= 0 a[1]=52 a[2]= 6 a[3]=23 a[4]=58 a[5]=17 a[6]=41 a[7]=35 a[8]=63
```
a[8]より大きいa[i]が存在しないため、このポーズでsplitは終了である。この時、$(i,j,t)=(8,7,63)$
となる。
#### ステップ2

##### 第1ポーズ
このポーズの開始時点でのa[i]：
```
a[0]= 0 a[1]=52 a[2]= 6 a[3]=23 a[4]=58 a[5]=17 a[6]=41 a[7]=35 a[8]=63
```
a[1]とa[5]の交換が行われる。
この時、$(i,j,t)=(1,5,35)$
となる。
##### 第2ポーズ
このポーズの開始時点でのa[i]：
```
a[0]= 0 a[1]=17 a[2]= 6 a[3]=23 a[4]=58 a[5]=52 a[6]=41 a[7]=35 a[8]=63
```
a[7]とa[4]の交換が行われる。
この時、$(i,j,t)=(4,3,35)$
となる。
また、ここで2回目のsplitは終了となる。
#### ステップ3
##### 第1ポーズ
このポーズの開始時点でのa[i]：
```
a[0]= 0 a[1]=17 a[2]= 6 a[3]=23 a[4]=35 a[5]=52 a[6]=41 a[7]=58 a[8]=63
```
以降は左右に分かれて整列を行う。
* 左
a[3]より大きいa[i]が存在しないため、左部分に関してはこのポーズで終了となる。
この時、$(i,j,t)=(1,2,23)$
となる。
* 右
a[7]より大きいa[i]が存在しないため、右部分に関してはこのポーズで終了となる。
この時、$(i,j,t)=(5,6,58)$
となる。

ステップ3はここで終了である。
#### ステップ4
このポーズの開始時点でのa[i]：
```
a[0]= 0 a[1]=17 a[2]= 6 a[3]=23 a[4]=35 a[5]=52 a[6]=41 a[7]=58 a[8]=63
```
* 左
a[1]とa[2]の交換が行われる。
この時、$(i,j,t)=(1,2,23)$
となる。
* 右
a[5]とa[6]の交換が行われる。
この時、$(i,j,t)=(5,6,58)$
となる。
#### ステップ5
```
a[0]= 0 a[1]=6 a[2]= 17 a[3]=23 a[4]=35 a[5]=41 a[6]=52 a[7]=58 a[8]=63
```
ステップ5の処理では、実質的に配列の操作は行われない。

比較回数をまとめると以下のようになる。
![](https://i.imgur.com/izlPt2m.png)

大小比較の合計回数は31回となる。

### 課題13.2
以下のようにプログラムを作成した。
quick2.c:
```C=
/*
*  quick2.c
*/
#include <stdio.h>
#include "array3.h"

int quicksort(Data *a, int l, int r) {
  int t;    // データを仕分ける基準値
  int i, j;
  int mcnt=0, lcnt=0, rcnt=0;
  if (l >= r) return 0;

  t=a[r];
  i=l-1; j=r;

  while (1) {
    while (a[++i]<t){mcnt++;};
    while (a[--j]>t){mcnt++;};
	mcnt+=2;
    if (i < j)
      swap(a, i, j);
    else
      break;
  }

  a[r]=a[i];
  a[i]=t;

lcnt = quicksort(a, l, i-1);
rcnt = quicksort(a, i+1, r);
return mcnt+lcnt+rcnt;
}
```
quick2.h:
```C=
/*
* quick2.h
*/
void printArrayQS(Data *a, int l, int r, char *msg);
int quicksort(Data *a, int l, int r);
```
main2.c:
```C=
/*
*  main2.c
*/

#include <stdio.h>
#include "array3.h"
#include "quick2.h"

#define NMAX 1000

int main() {
  Data a[NMAX];
  int n;

  // stdin は main() で定義されている標準入力
  n = getDataInArray(a, stdin);

  printArrayQS(a, 0, n-1, "input data");

  int count = quicksort(a, 0, n-1);

  printArrayQS(a, 0, n-1, "sorted");
  printf("count:%d\n",count);
  return 0;
}
```
以上のプログラムがquicksort2として実行できるようにコンパイルを行った。
プログラム動作確認のため、課題13.1と同一のデータを入力しプログラムを実行したので、その結果を以下に示す。
```
[o1810128@itc128 kadai13]$ cat data1 | ./quicksort2
input data
a[0]= 0 a[1]=63 a[2]=35 a[3]=52 a[4]= 6 a[5]=58 a[6]=23 a[7]=17 
sorted
a[0]= 0 a[1]= 6 a[2]=17 a[3]=23 a[4]=35 a[5]=52 a[6]=58 a[7]=63 
count:25
```
このデータを出力するために合計25回の比較を行っていることがわかる。これは資料に記載の回数と一致している。

### 課題13.3
測定のためにquicksortTという実行ファイルを作成した。Makefileの中身とソースコードを以下に示す。
Makefile:
```
#
# Makefile3
#
TARGET = quicksortT
OBJS = main3.o array3.o quick2.o data.o clock.o
CC = cc
CFLAGS = -Wall

.SUFFIXES: .c .o

${TARGET} : ${OBJS}
	${CC} ${CFLAGS} -o ${TARGET} $^

.c.o:
	${CC} ${CFLAGS} -c $<

clean:
	rm -f *.o
```
main3.c
```C
/*
*  main3.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "array3.h"
#include "quick2.h"
#include "data.h" // copy it from Chap. 11
#include "clock.h" // copy it from Chap. 11
/*#define NMAX 1000*/
#define NMAX 1000001

int* allocateMemoryForIntData(int n)
{
    // check the value of n
    int* d;
    if (n > NMAX) {
        printf("The input data size exeeds %d\n", NMAX);
        exit(2);
    }
    else if (n < 0) {
        printf("n must be positive integer.\n");
        exit(1);
    }
    d = (int*)calloc(n, sizeof(int));
    if (d == NULL) {
        printf("Failed to allocate memoryn");
        exit(9);
    }
    else
        return d;
}

int main(int argc, char** argv)
{
    Data a[NMAX];
    int i, n, *data;
    // enter the number of data
    if (argc == 2)
        n = (int)atoi(argv[1]);
    else {
        printf("usage: quicksortT n\n");
        return 1;
    }
    data = allocateMemoryForIntData(n);
    generateRandomData(data, n);
    for (i = n; i > 0; i--) // make data start at the address 1.
        data[i] = data[i - 1];

    startClock();
    int count = quicksort(data, 0, n - 1);
    stopClock();
    printClock();
    printf("count:%d\n", count);
    return 0;
}
```
ほかに必要なファイルは課題11からコピーして使用した。

以下にクイックソートに要した時間の測定結果とそのグラフを示す。
| $n$       | $T_n$       | $T_n/n$        |
|---------|----------|-------------|
| 1000    | 8E-05    | 8E-08       |
| 2000    | 0.00017  | 8.5E-08     |
| 5000    | 0.00049  | 9.8E-08     |
| 10000   | 0.001006 | 1.006E-07   |
| 20000   | 0.00228  | 1.14E-07    |
| 50000   | 0.005645 | 1.129E-07   |
| 100000  | 0.012656 | 1.2656E-07  |
| 200000  | 0.025921 | 1.29605E-07 |
| 500000  | 0.07008  | 1.4016E-07  |
| 1000000 | 0.147007 | 1.47007E-07 |

![](https://i.imgur.com/5lXHzn7.png)

クイックソートと他の整列アルゴリズムとの比較を行う。
まず、データ数が100000であるときの各ソートにおける1つ当たりのデータ処理時間を示す。(前回及び今回のレポートに記載の結果を再掲したものである)
|アルゴリズム|$T_n/n$|
|------------|---------|
|基本ソート|0.00031272869|
|二分探索ソート|0.00000044464|
|ヒープソート|0.00000039960|
|マージソート|0.00000018323|
|クイックソート|0.00000012656|

表より、クイックソートがもっとも計算時間が短いことがわかる。
また、すべてのソートをグラフにすると、以下のようになる。
![](https://i.imgur.com/mLxduTJ.png)

ほかのソート方法に比べ、クイックソートはを曲線で結んだときのy切片がもっとも小さい。また、ほかのアルゴリズムに比べ$n$が増加してもデータ1つあたりの時間計算量がほとんど変化していないことがわかる。また、ランダムなデータに対しても時間計算量の変化が少ないことも分かる。つまりクイックソートは名前の通り、いままで扱ったソートアルゴリズムの中では最も処理時間が早い。