#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define swap(type,x,y) type t = x; x = y; y = t; //교환함수
void selection(void); //선택정렬
void insertion(void); //삽입정렬
void merge(int,int); //병합정렬
void quick(int,int); //퀵정렬
void bubble(void); //버블정렬
void output(char*); //(output.txt로 정렬된 수열과 elapsed time 출력) or 표준출력
int n;
int *a;
int *buff;
double milsec;
time_t start, end;
FILE *input_file;
FILE *output_file;
int main(int argc, char* argv[]){
int i;
char num[10]; //n은 1,000,000,000미만.
input_file = fopen(argv[2],"r");
output_file = fopen(argv[3],"w");
if(input_file == NULL){;
printf("ERROR_InputFile\n");
return 0;
}//input_file이 존재하지 않으면 에러 출력.
fgets(num,sizeof(num),input_file);
n = atoi(num); //배열의 크기 N을 구함.
a = calloc(n,sizeof(int));
for(i=0;i<n;i++){
fscanf(input_file,"%d",&a[i]); //배열 a에 정렬되지 않은 수 받기.
}
//명령받기.
if(!strcmp(argv[1],"selection")) selection();
else if(!strcmp(argv[1],"insertion")) insertion();
else if(!strcmp(argv[1],"merge")){
buff = calloc(n,sizeof(int));
merge(0,n-1);
free(buff);
}
else if(!strcmp(argv[1],"quick")) quick(0,n-1);
else if(!strcmp(argv[1],"bubble")) bubble();
else printf("Wrong_SortInstruction");
//결과출력.
output(argv[3]);
//배열해제 및 파일닫기.
free(a);
fclose(input_file);
fclose(output_file);
return 0;
}
//선택정렬
void selection(void){
start = clock();
int i, j;
for(i=0;i<n-1;i++){
int min = i;
for(j=i+1;j<n;j++){
if(a[j]<a[min]){
min = j;
}
}
swap(int,a[i],a[min]);
}
end = clock();
}
//삽입정렬
void insertion(void){
start = clock();
int i,j;
for(i=1;i<n;i++){
int tmp = a[i];
for(j=i; j>0 && a[j-1]>tmp; j--){
a[j] = a[j-1];
}
a[j] = tmp;
}
end = clock();
}
//병합정렬
void merge(int left, int right){
start = clock();
if(left<right){
int i, j = 0, k = left, p = 0;
int center = (left + right) / 2;
merge(left,center);
merge(center+1,right);
for(i=left;i<=center;i++){
buff[p++] = a[i];
}
while(i<=right && j<p){
a[k++] = (buff[j]<=a[i]) ? buff[j++] : a[i++];
}
while(j<p){
a[k++] = buff[j++];
}
}
end = clock();
}
//퀵정렬
void quick(int left, int right){ //재귀적인 방식.
start = clock();
int pl = left;
int pr = right;
int x = a[(pl+pr)/2];
do{
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr){
swap(int,a[pl],a[pr]);
pl++;
pr--;
}
}while(pl <= pr);
if(left < pr) quick(left,pr);
if(pl < right) quick(pl,right);
end = clock();
}//비재귀적인 방법은 스택을 활용.
//버블정렬
void bubble(void){
start = clock();
int i = 0, j;
while(i<n-1){
int last = n-1; //가장 마지막으로 교환이 일어난 위치
for(j=n-1;j>i;j--){
if(a[j]<a[j-1]){
swap(int,a[j],a[j-1]);
last = j;
}
}
i = last;
}
end = clock();
}
//출력함수
void output(char* argv){
int i;
milsec = 1000.0 * (end-start) / CLOCKS_PER_SEC;
if(argv){
for(i=0;i<n;i++){
fprintf(output_file,"%d ",a[i]); //정렬된 배열 a 출력
}
fprintf(output_file,"\n");
fprintf(output_file,"elapsed_time = %.3f ms\n",milsec); //elapsed_time 출력
}
else{
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
printf("elapsed_time = %.3f ms\n",milsec);
}
}
//힘들어ㅠㅠ
