#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* timespec使い方メモ
struct timespec {
time_t tv_sec;
long tv_nsec;
};
void sub() {
timespec_get(&ts, TIME_UTC);
printf("%ld %09ld\n", ts.tv_sec, ts.tv_nsec);
}
*/
// 時間経過ナノ秒計算
int calc_timelapse_nsec(struct timespec start, struct timespec end){
if(start.tv_sec == end.tv_sec){
// 秒が同じ
return end.tv_nsec - start.tv_nsec;
}else{
// 秒が異なる
int diff_sec = end.tv_sec - start.tv_sec;
int diff_nsec = diff_sec * 1000000000;
return diff_nsec + (end.tv_nsec - start.tv_nsec);
}
}
void dispArrayList(int *a, int length){
for(int i=0; i<length; i++){
printf("[%d] : %d\n", i, a[i]);
}
}
void dispArrayLine(int *a, int length){
for(int i=0; i<length; i++){
printf("%d", a[i]);
if(i == length - 1){
printf("\n");
}else{
printf(" ");
}
}
}
void resetArray(int *a, int length){
for(int i=0; i<length; i++){
a[i] = 0;
}
}
void init(){
srand(time(NULL));
}
double getRandomDouble(){
return rand() * 1.0 / RAND_MAX;
}
int getRandomInt(){
int min = 0;
int max = 9;
return getRandomIntMinMax(min, max);
}
int getRandomIntMinMax(int min, int max){
if(max < min){
return max;
}else{
return min + (int)(getRandomDouble() * (max - min + 1));
}
}
void setRandomForArray(int *a, int length){
for(int i=0; i<length; i++){
a[i] = getRandomInt();
}
}
void swap(int *a, int l, int r){
int t = a[l];
a[l] = a[r];
a[r] = t;
}
void bubblesort(int *a, int length){
for(int i=0; i<length-1; i++){
for(int j=i; j<length; j++){
if(a[j] < a[i]){
swap(a, i, j);
}
}
}
}
int getPivot(int a, int b, int c){
if(b < a){
if(a < c){
return a;
}else{
return b < c ? b : c;
}
}else{
if(b < c){
return b;
}else{
return a < c ? a : c;
}
}
}
void quicksort_core(int *a, int length, int left, int right){
if(right <= left){
return;
}
int l = left;
int r = right;
int p = getPivot(a[l], a[l+1], a[r]);
while(1){
while(a[l] < p){
l++;
}
while(p < a[r]){
r--;
}
if(r <= l){
break;
}
swap(a, l, r);
l++;
r--;
}
quicksort_core(a, length, left, l-1);
quicksort_core(a, length, r+1, right);
}
void quicksort(int *a, int length){
int left = 0;
int right = length - 1;
quicksort_core(a, length, left, right);
}
int calcTimeLapse_bubblesort_nsec(int *a, int length){
int b[length];
for(int i=0; i<length; i++){
b[i] = a[i];
}
struct timespec ts_start, ts_end;
timespec_get(&ts_start, TIME_UTC);
bubblesort(b, length);
timespec_get(&ts_end, TIME_UTC);
return calc_timelapse_nsec(ts_start, ts_end);
}
int calcTimeLapse_quicksort_nsec(int *a, int length){
int b[length];
for(int i=0; i<length; i++){
b[i] = a[i];
}
struct timespec ts_start, ts_end;
timespec_get(&ts_start, TIME_UTC);
quicksort(b, length);
timespec_get(&ts_end, TIME_UTC);
return calc_timelapse_nsec(ts_start, ts_end);
}
int calcTimeLapse_bubblesort_average_nsec(int length, int times){
int a[length];
int sum_nsec = 0;
for(int i=0; i<times; i++){
setRandomForArray(a, length);
sum_nsec += calcTimeLapse_bubblesort_nsec(a, length);
}
return sum_nsec / times;
}
int calcTimeLapse_quicksort_average_nsec(int length, int times){
int a[length];
int sum_nsec = 0;
for(int i=0; i<times; i++){
setRandomForArray(a, length);
sum_nsec += calcTimeLapse_quicksort_nsec(a, length);
}
return sum_nsec / times;
}
int main(void){
/* 準備 */
init();
/* 宣言 */
struct timespec ts_start, ts_end;
int times = 10000;
int length = 30;
/* 処理 */
int timelapse_bubblesort_average_nsec =
calcTimeLapse_bubblesort_average_nsec(length, times);
int timelapse_quicksort_average_nsec =
calcTimeLapse_quicksort_average_nsec(length, times);
/* 出力 */
printf("timelapse_bubblesort_average_nsec : %d\n",
timelapse_bubblesort_average_nsec);
printf("timelapse_quicksort_average_nsec : %d\n",
timelapse_quicksort_average_nsec);
}
