## アルゴリズムとデータ構造およびプログラミング演習
**レポート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の処理では、実質的に配列の操作は行われない。
比較回数をまとめると以下のようになる。
大小比較の合計回数は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 |
クイックソートと他の整列アルゴリズムとの比較を行う。
まず、データ数が100000であるときの各ソートにおける1つ当たりのデータ処理時間を示す。(前回及び今回のレポートに記載の結果を再掲したものである)
|アルゴリズム|$T_n/n$|
|------------|---------|
|基本ソート|0.00031272869|
|二分探索ソート|0.00000044464|
|ヒープソート|0.00000039960|
|マージソート|0.00000018323|
|クイックソート|0.00000012656|
表より、クイックソートがもっとも計算時間が短いことがわかる。
また、すべてのソートをグラフにすると、以下のようになる。
ほかのソート方法に比べ、クイックソートはを曲線で結んだときのy切片がもっとも小さい。また、ほかのアルゴリズムに比べ$n$が増加してもデータ1つあたりの時間計算量がほとんど変化していないことがわかる。また、ランダムなデータに対しても時間計算量の変化が少ないことも分かる。つまりクイックソートは名前の通り、いままで扱ったソートアルゴリズムの中では最も処理時間が早い。
Sign in with Wallet
Connect another wallet