#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10 //1번 문제에서 10 개 생성
#define FALSE 0
#define TRUE 1
void Swap(int *p1,int *p2); //값 비교 후 해당 배열값 교환하는 함수
void makeRanNum(int A[], int n, int m); //난수 생성 함수
void printarray(int A[]); // 배열 출력 함수
void SelectionSort (int A[ ], int n ) ;
void BubbleSort(int A[], int n);
void InsertionSort(int A[],int n);
void ShellSort(int A[],int n);
int Partition (int A[ ], int Left, int Right );
void QuickSort (int A[ ], int Left, int Right );
void MergeSort (int A[ ], int Low, int High );
void Merge (int A[ ], int Low, int Mid, int High ); //B[NUM OF KEY] 에서 NUM OF KEY가 n=10,10000,100000개 일때 마다 달라서 함수를 더 생성함.(적절한 방법이 떠오르지 않음)
void MergeSortv2 (int A[ ], int Low, int High , int n); //비순환 버젼
void Merge10000 (int A[ ], int Low, int Mid, int High ); //n=10000일때 사용
void Merge100000 (int A[ ], int Low, int Mid, int High ); //n= 100000일때 사용
void HeapSort (int A[ ], int n );
void MakeHeap(int A[ ], int Root, int LastNode );
int main()
{
int i,num[SIZE],x,y,z,start,finish;
int num1[10000];
int num2[100000];
double duration;
srand(time(NULL));
while(1){
printf("\n\t\t[메 뉴]");
printf("\n\t\t====================");
printf("\n\t\t1.난수 생성 후 정렬");
printf("\n\t\t2.정렬하는데 걸리는 시간");
printf("\n\t\t0.종 료");
printf("\n\n\t\t숫자를 입력하세요:");
scanf("%d",&x);
switch(x)
{
case 1:
{
printf("\n\t\t[난수 생성 후 정렬]");
printf("\n\t\t1.선택정렬");
printf("\n\t\t2.버블정렬");
printf("\n\t\t3.삽입정렬");
printf("\n\t\t4.쉘정렬");
printf("\n\t\t5.퀵정렬(순환버전)");
printf("\n\t\t6.합병정렬(순환버전)");
printf("\n\t\t7.합병정렬(비순환버전)");
printf("\n\t\t8.힙정렬");
printf("\n\t\t9.기수정렬");
printf("\n\n\t\t 숫자를 입력하세요:");
scanf("%d",&y);
switch(y)
{
case 1:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
SelectionSort(num,SIZE);
printf("\n[선택정렬]\n");
printarray(num);
}break;
case 2:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
BubbleSort(num,SIZE);
printf("\n[버블정렬]\n");
printarray(num);
}break;
case 3:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
InsertionSort(num,SIZE);
printf("\n[삽입정렬]\n");
printarray(num);
}break;
case 4:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
ShellSort(num,SIZE);
printf("\n[쉘 정렬]\n");
printarray(num);
}break;
case 5:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
QuickSort(num,0,9); //퀵정렬 함수
printf("\n[퀵 정렬]\n");
printarray(num);
}break;
case 6:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
MergeSort(num,0,9);//합병정렬 함수
printf("\n[합병정렬]\n");
printarray(num);
}break;
case 7:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
MergeSortv2(num,0,9 , 10);
printf("\n[합병정렬(비순환)]\n");
printarray(num);
}break;
case 8:
{
makeRanNum(num,SIZE,10000);
printf("\n[생성된 난수]\n");
printarray(num);
HeapSort(num,10);
printf("\n[힙 정렬]\n");
printarray(num);
}break;
}
}break;
case 2:
{
printf("\n\t\t[정렬하는데 걸리는 시간]");
printf("\n\t\t1.선택정렬");
printf("\n\t\t2.버블정렬");
printf("\n\t\t3.삽입정렬");
printf("\n\t\t4.쉘정렬");
printf("\n\t\t5.퀵정렬(순환버전)");
printf("\n\t\t6.합병정렬(순환버전)");
printf("\n\t\t7.합병정렬(비순환버전)");
printf("\n\t\t8.힙정렬");
printf("\n\t\t9.기수정렬");
printf("\n\n\t\t 숫자를 입력하세요:");
scanf("%d",&z);
switch(z)
{
case 1:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
SelectionSort(num1,10000);
finish = clock();
printf("\n[10000개 선택 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
SelectionSort(num2,100000);
finish = clock();
printf("\n[100000개 선택 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
} break;
case 2:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
BubbleSort(num1,10000);
finish = clock();
printf("\n[10000개 버블 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
BubbleSort(num2,100000);
finish = clock();
printf("\n[100000개 버블 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 3:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
InsertionSort(num1,10000);
finish = clock();
printf("\n[10000개 삽입 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
InsertionSort(num2,100000);
finish = clock();
printf("\n[100000개 삽입 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 4:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
ShellSort(num1,10000);
finish = clock();
printf("\n[10000개 쉘 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
ShellSort(num2,100000);
finish = clock();
printf("\n[100000개 쉘 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 5:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
QuickSort(num1,0,9999);
finish = clock();
printf("\n[10000개 퀵 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
QuickSort(num2,0,99999);
finish = clock();
printf("\n[100000개 퀵 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 6:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
MergeSort(num1,0,9999);
finish = clock();
printf("\n[10000개 합병정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
MergeSort(num2,0,99999);
finish = clock();
printf("\n[100000개 합병정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 7:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
MergeSortv2(num1,0,9999,10000);
finish = clock();
printf("\n[10000개 합병정렬(비순환) 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,10000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
MergeSortv2(num2,0,99999,100000);
finish = clock();
printf("\n[100000개 합병정렬(비순환) 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
case 8:
{
makeRanNum(num1,10000,1000000);
printf("\n[n=10000개 난수 생성 완료!!]\n");
start = clock();
HeapSort(num1,10000);
finish = clock();
printf("\n[10000개 힙 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
makeRanNum(num2,100000,1000000,1000000);
printf("\n[n=100000개 난수 생성 완료!!]\n");
start = clock();
HeapSort(num2,100000);
finish = clock();
printf("\n[100000개 힙 정렬 완료!!]\n");
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("걸린 시간은 %.7lf 밀리초\n",duration*1000.);
}break;
}break;
}
case 0: exit(0);
}
getch();
system("cls");
}
return 0;
}
void SelectionSort (int A[ ], int n )
{
int i,j,MinIndex=0;
//선택 정렬
for (i = 0; i < n-1; i++)
{
MinIndex = i;
for (j = MinIndex +1; j < n; j++)
{
if (A[MinIndex] > A[j])
MinIndex = j;
}
if (MinIndex != i)
Swap(&A[i], &A[MinIndex]);
}
}
void BubbleSort(int A[],int n)
{
int i,NumKeys,Sorted=FALSE; // c++은 bool 로 false true 되는데 c는 그게 안되서 define으로 0과 1값을 따로 정의
while (!Sorted) {
Sorted = TRUE;
for (i = 1; i < SIZE; i++) // for문에 { } 중괄호가 없어서 이해하는데 시간을 많이 소요함. Tico 교재에 수정을 요청함.
{
if (A[i - 1] > A[i])
{
Swap(&A[i - 1], &A[i]);
Sorted = FALSE;
}
}
NumKeys --;
}
}
void InsertionSort(int A[],int n)
{
int i,j, Value;
for (i= 2; i<n; i++)
{
Value = A[i];
j = i;
while (A[j - 1]> Value)
{
A[j] = A[j - 1]; j --;
}
A[j] = Value;
}
}
void ShellSort(int A[],int n)
{
int h,i,j,Value;
h = 1;
do
{
h = 3 * h + 1;
}while (h < SIZE);
do {
h = h/3;
for (i = h; i < SIZE; i++)
{
Value = A[i];
j = i;
while (A[j - h] > Value)
{
A[j] = A[j - h];
j -= h;
if (j <= h-1)
break;
}
A[j] = Value;
}
}while (h > 1);
}
int Partition (int A[ ], int Left, int Right ) {
/* 입력 : A[Left : Right] : 분할하려는 부분배열, A[Left] : 분할 원소, A[Right] : 더미 키
출력 : A[Left : Right], Right : 분할 원소를 제자리에 위치시키고, 그 인덱스를 변수
Right 에 담아서 복귀한다. */
int PartElem, Value;
PartElem = Left;
Value = A[PartElem];
do {
do { } while (A[ ++Left] < Value);
do { } while (A[ --Right] > Value);
if (Left < Right) Swap (&A[Left], &A[Right]);
else break;
} while (1);
A[PartElem] = A[Right];
A[Right] = Value;
return Right;
}
void QuickSort (int A[ ], int Left, int Right ) {
/* 입력 : A[Left : Right + 1] : 정렬할 배열, A[Right+1]은 배열 내의 최대값보다
큰 값.
Left, Right : 배열 내의 정렬할 원소의 위치를 알리는 최소, 최대 인덱스.
출력 : A[Left : Right] : 정렬된 배열. A[Right + 1]은 더미 키가 있는 곳. */
int Middle;
if (Right > Left) {
Middle = Partition (A, Left, Right + 1);
QuickSort (A, Left, Middle - 1);
QuickSort (A, Middle + 1, Right);
}
}
void MergeSort (int A[ ], int Low, int High )
{
/* 입력 : A[Low : High] : 정렬할 배열,
Low, High : 정렬할 원소가 있는 곳을 나타내는 최소, 최대 인덱스.
출력 : A[Low : High] : 정렬된 배열. */
int Mid;
if (Low < High)
{
Mid = (Low + High)/2;
MergeSort (A, Low, Mid);
MergeSort (A, Mid+1, High);
if(Low+High==10)
Merge (A, Low, Mid, High);
else if(Low+High==10000)
Merge10000 (A, Low, Mid, High);
else if(Low+High==10000)
Merge100000 (A, Low, Mid, High);
}
}
void MergeSortv2 (int A[ ], int Low, int High ,int n)
{
int i,Mid=0;
for (i=1; i< n; i=2+i)
{
Low = 1;
while(Low <=n)
{
High = Low + (2+i)-1;
if(High>n) High =n;
Mid = Low +i -1;
if(Mid <=n)
{
if(Low+High==10){
Merge (A, Low-1, Mid-1, High-1);} //책에는 -1이 없음
else if(Low+High==10000)
Merge10000 (A, Low-1, Mid-1, High-1);
else if(Low+High==10000)
Merge100000 (A, Low-1, Mid-1, High-1);
}
Low = High +1;
}
}
}
void Merge (int A[ ], int Low, int Mid, int High)
{
/* 입력 : A[Low : Mid] : 정렬할 배열, A[Mid + 1 : High] : 정렬된 두 배열
출력 : A[Low : High] : A[Low : Mid]와 A[Mid + 1 : High]를 합병하여 정렬된 배열. */
int B[SIZE]; //NUM OF KEY 가 10 일때와 10000일때 그리고 100000일때 마다 다른크기로 배열을 설정해야하는데 해결하기 힘듬.
//조건에 따라 변수를 선언하려고 시도했으나 실패함.
int i, LeftPtr, RightPtr, BufPtr;
LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;
while (LeftPtr <= Mid && RightPtr <= High)
{
if (A[LeftPtr] < A[RightPtr])
B[BufPtr++] = A[LeftPtr++];
else B[BufPtr++] = A[RightPtr++];
}
if (LeftPtr > Mid)
{
for (i = RightPtr; i <=High; i++ )
B[BufPtr++] = A[i];
}
else
{
for (i = LeftPtr; i <= Mid; i++)
B[BufPtr++] = A[i];
}
for (i = Low; i <= High; i++)
A[i] = B[i];
}
void Merge10000 (int A[ ], int Low, int Mid, int High )
{
/* 입력 : A[Low : Mid] : 정렬할 배열, A[Mid + 1 : High] : 정렬된 두 배열
출력 : A[Low : High] : A[Low : Mid]와 A[Mid + 1 : High]를 합병하여 정렬된 배열. */
int B[10000];
int i, LeftPtr, RightPtr, BufPtr;
LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;
while (LeftPtr <= Mid && RightPtr <= High)
{
if (A[LeftPtr] < A[RightPtr])
B[BufPtr++] = A[LeftPtr++];
else B[BufPtr++] = A[RightPtr++];
}
if (LeftPtr > Mid)
{
for (i = RightPtr; i <=High; i++ )
B[BufPtr++] = A[i];
}
else
{
for (i = LeftPtr; i <= Mid; i++)
B[BufPtr++] = A[i];
}
for (i = Low; i <= High; i++)
A[i] = B[i];
}
void Merge100000 (int A[ ], int Low, int Mid, int High )
{
/* 입력 : A[Low : Mid] : 정렬할 배열, A[Mid + 1 : High] : 정렬된 두 배열
출력 : A[Low : High] : A[Low : Mid]와 A[Mid + 1 : High]를 합병하여 정렬된 배열. */
int B[100000];
int i, LeftPtr, RightPtr, BufPtr;
LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;
while (LeftPtr <= Mid && RightPtr <= High)
{
if (A[LeftPtr] < A[RightPtr])
B[BufPtr++] = A[LeftPtr++];
else B[BufPtr++] = A[RightPtr++];
}
if (LeftPtr > Mid)
{
for (i = RightPtr; i <=High; i++ )
B[BufPtr++] = A[i];
}
else
{
for (i = LeftPtr; i <= Mid; i++)
B[BufPtr++] = A[i];
}
for (i = Low; i <= High; i++)
A[i] = B[i];
}
void HeapSort (int A[ ], int n ) {
/* 입력 : A[0 : n - 1] : 정렬할 배열, n : 정렬할 원소의 개수.
출력 : A[0 : n - 1] : 정렬된 배열. */
int i;
for (i = n/2; i > 0; i--) /* 상향식 히프 구축 */
MakeHeap (A, i - 1, n - 1);
for (i = n - 1; i > 0; i--)
{
Swap (&A[0], &A[i]);
MakeHeap (A, 0, i - 1); /* 히프 조정 */
}
}
void MakeHeap(int A[ ], int Root, int LastNode )
{
/*입력 : A[Root : LastNode] : 히프로 변환할 배열,
입력당시에 A[Root+1 : LastNode]는 이미 히프 구조이다.
출력 : A[Root : LastNode] : 최대값 히프. */
int Parent, LeftSon, RightSon, Son, RootValue;
Parent = Root;
RootValue = A[Root];
LeftSon = 2 * Parent + 1;
RightSon = LeftSon + 1;
while (LeftSon <= LastNode)
{
if (RightSon <= LastNode && A[LeftSon] < A[RightSon])
Son = RightSon;
else
Son = LeftSon;
if (RootValue < A[Son])
{
A[Parent] = A[Son];
Parent = Son;
LeftSon = Parent * 2 + 1;
RightSon = LeftSon + 1;
}
else break;
}
A[Parent] = RootValue;
}
void makeRanNum(int A[],int n,int m)
{
int i;
for(i=0; i < n; i++)
{
A[i]= rand() % m + 0; //0~9999까지의 난수를 num 배열에 SIZE(10)만큼 삽입
}
}
void printarray(int A[])
{
int i;
for (i=0; i < SIZE; i++)
{
printf("%d\t",A[i]);
}
}
void Swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
