#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 20
int data[MAX];
int random[MAX];
int tmp[MAX]; // 합병정렬에서 사용
double result[6];
clock_t start, end;
void ArrayReset(); // 배열 초기화
void swap(int*, int*); // 값 바꾸는 함수
void print_sorted();
void SelectionSort(); // 선택정렬
int Small(int);
void InsertionSort(); // 삽입정렬
void BubbleSort(); // 버블정렬
void MergeSort(int, int); // 합병정렬
void Merge(int, int, int);
void QuickSort(int, int); // 퀵정렬
void firstNode(int); // 이진탐색트리
struct node* makeNode(int);
void searchNode(struct node*,int);
void inOrder(struct node*);
/*구조체 선언*/
struct node
{
int value;
struct node *Alink;
struct node *Blink;
};
struct node *Root=NULL;
/*랜덤으로 수를 정해줌*/
int main(){
int i, j, k, x, count;
srand((unsigned)time(NULL));
for(j=0;j<MAX;j++){
do{
x=rand()%101;
count=0;
for(k=0;k<j;k++){
if(random[k]==x) count++;
}
}while(count!=0);
random[j]=x;
}
printf("☞정렬 데이터\n");
for(i=0;i<MAX;i++) printf("%d ", random[i]);
printf("\n\n");
ArrayReset();
start=clock();
SelectionSort();
end=clock();
printf(" ☞ 선택정렬\n");
print_sorted();
result[0]=(double)(end-start)/CLOCKS_PER_SEC;
ArrayReset();
start=clock();
InsertionSort();
end=clock();
printf(" ☞ 삽입정렬\n");
print_sorted();
result[1]=(double)(end-start)/CLOCKS_PER_SEC;
ArrayReset();
start=clock();
BubbleSort();
end=clock();
printf(" ☞ 버블정렬\n");
print_sorted();
result[2]=(double)(end-start)/CLOCKS_PER_SEC;
ArrayReset();
start=clock();
MergeSort(0, MAX-1);
end=clock();
printf(" ☞ 합병정렬\n");
print_sorted();
result[3]=(double)(end-start)/CLOCKS_PER_SEC;
ArrayReset();
start=clock();
QuickSort(0, MAX-1);
end=clock();
printf(" ☞ 퀵정렬\n");
print_sorted();
result[4]=(double)(end-start)/CLOCKS_PER_SEC;
ArrayReset();
printf(" ☞ 이진탐색트리\n");
start=clock();
firstNode(random[0]);
for(i=1;i<MAX;i++)
searchNode(Root,random[i]);
end=clock();
inOrder(Root);
result[5]=(double)(end-start)/CLOCKS_PER_SEC;
printf("\n\n");
for(i=0;i<6;i++)
printf("%2.3f ", result[i]);
printf("\n");
return 0;
}
/*정렬할 배열 데이터 초기화*/
void ArrayReset(){
int i;
for(i=0;i<MAX;i++){
data[i]=random[i];
}
}
void swap(int *a, int *b){
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
/*정렬 결과 출력*/
void print_sorted(){
int i;
for(i=0;i<MAX;i++) printf("%d ", data[i]);
printf("\n");
}
/* 선택정렬*/
void SelectionSort(){
int i, j;
for(i=0;i<MAX-1;i++){
j=Small(i+1);
if(data[i]>data[j]){
swap(&data[i], &data[j]);
}
}
}
/*가장 작은 수를 찾는 함수 */
int Small(int a){
int i, j=a, small=data[a];
for(i=a;i<MAX;i++){
if(data[i]<small){
small=data[i];
j=i;
}
}
return j;
}
/* 삽입정렬 */
void InsertionSort(){
int tmp, i, j;
for(i=1;i<MAX;i++){
tmp=data[i];
j=i;
while(data[j-1]>tmp && j>=1){
data[j]=data[j-1];
j--;
}
data[j]=tmp;
}
}
/* 버블정렬*/
void BubbleSort(){
int i, j;
for(i=MAX;i>=0;i--){
for(j=0;j<i-1;j++){
if(data[j]>data[j+1]){
swap(&data[j], &data[j+1]);
}
}
}
}
/* 합병정렬 */
void MergeSort(int low, int high){
int mid;
if(low<high){
mid=(low+high)/2;
MergeSort(low,mid);
MergeSort(mid+1,high);
Merge(low, mid,high);
}
}
void Merge(int low, int mid, int high){
int i, l, m, k;
l=low;
m=mid+1;
k=low;
while(l<=mid && m<=high){
if(data[l]<=data[m]){
tmp[k++]=data[l++];
}
else{
tmp[k++]=data[m++];
}
}
if(l>mid){
for(i=m;i<=high;i++){
tmp[k++]=data[i];
}
}
else{
for(i=l;i<=mid;i++){
tmp[k++]=data[i];
}
}
for(i=low;i<=high;i++){
data[i]=tmp[i];
}
}
/* 퀵정렬*/
void QuickSort(int left, int right){
int pivot=data[left], i=left, j=right+1;
if(left<right){
do{
do{
i++;
}while(pivot>data[i]);
do{
j--;
}while(pivot<data[j]);
if(i<j){
swap(&data[i], &data[j]);
}
}while(i<j);
swap(&data[left], &data[j]);
QuickSort(left, j-1);
QuickSort(j+1, right);
}
}
/* 이진탐색트리 */
void firstNode(int a){
Root=makeNode(a);
}
struct node* makeNode(int b){
struct node *mnode;
mnode=(struct node*)malloc(sizeof(struct node));
mnode->value=b;
mnode->Alink=NULL;
mnode->Blink=NULL;
return mnode;
}
void searchNode(struct node *T,int a){
struct node *snode;
if(T->value>a) {
if(T->Alink!=NULL){
searchNode(T->Alink,a);
}
else {
snode=makeNode(a);
T->Alink=snode;
}
}
else{
if(T->Blink!=NULL){
searchNode(T->Blink,a);
}
else{
snode=makeNode(a);
T->Blink=snode;
}
}
}
void inOrder(struct node* T){
if(T!=NULL){
inOrder(T->Alink);
printf("%d ", T->value);
inOrder(T->Blink);
}
}
// 뭐 이정도 쯤은 암기-_-해줘야 컴퓨터를 전공한다 할 수 있겠지요
