Programings/Algorithms (10) 썸네일형 리스트형 [Algorith] 병합 정렬 (Merge Sort) #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 void MakeRandomNumber(void); void MergeSort(int [], int, int); void DisPlayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; int temp[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisPlayBuffer(); printf("정렬 후 데이터\n"); MergeSort(Buf, 0, MAX -1); DisPlayBuffer(); printf("\n"); } void MakeRandomNumb.. [Algorith] 퀵 정렬 (Quick Sort) #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 void MakeRandomNumber(void); void QuickSort(int [], int, int); void DisPlayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisPlayBuffer(); printf("정렬 후 데이터\n"); QuickSort(Buf, 0, MAX -1); DisPlayBuffer(); printf("\n"); } /* 정렬할 데이터의 초기화 */ void MakeRandom.. [Algorith] 쉘 정렬 (Shell Sort) Bing-O 표기법에 의한 O( N (logN)^2 ) 이다. 퀵 정렬에 가까운 성능을 보인다. #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 // 함수의 프로토타입 void MakeRandomNumber(void); void ShellSort(void); void DisplayBuffer(void); int IsNumberExit(int, int); int Buf[MAX]; void main() { printf("정렬할 데이터의 초기화\n"); MakeRandomNumber(); DisplayBuffer(); printf("정렬 후 데이터\n"); ShellSort(); DisplayBuffer(); printf("\.. [Algorith] 버블 정렬 (Bubble Sort) 정렬 전 3 7 9 1 2 1차 정렬 3 7 1 9 2 -> 3 7 1 2 9 1차 정렬 끝 2차 정렬 3 1 7 2 9 -> 3 1 2 7 9 2차 정렬 끝 3차 정렬 1 3 2 7 9 -> 1 2 3 7 9 3차 정렬 끝 정렬이 한번 끝날 때 마다 끝에 가장 큰 수가 정렬된다. 비교 횟수는 N^2/2가 된다. 만약 최악의 경우일 경우 비교와 이동 횟구 모두 N^2/2가 된다. Big-O 표기법의 의한 O(N^2)이 된다. #include #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 // 함수의 프로토타입 void MakeRandomNumber(void); void BubbleSort(void); void DisplayBuffer(.. [Algorith] 삽입 정렬 (Insertion Sort) 정렬 전 3 7 9 1 2 1차 정렬 3 7 9 1 2 2차 정렬 3 7 9 1 2 3차 정렬 1 3 7 9 2 4차 정렬 1 2 3 7 9 비교 횟수는 데이터 수와 같다. 최악의 경우엔 N(N-1)/2 의 계산이 필요하다. 또한 데이터의 이동 횟수도 N(N-1)/2의 계산이 나온다 따라서 정렬이 잘된 리스트를 가지고 삽입 정렬을 하면 선택 정렬에 비해 빠를 수 있다. 왜냐면 삽입 정렬의 비교가 비교적 선택 정렬보다 적을 수 있기 때문이다. 그래서 정렬이 잘 되어 있다면 O(N)에 가까운 계산이 나올 수 있다. 다만 정렬이 안된 상태라면 선택 정렬이 빠를 수 있다. Big-O 표기법의 의한 O(N^2)이다. #include #include #define MAX 100 #define TRUE 1 #defi.. [Algorith] 선택 정렬 (Selection sort) 정렬 전 3 7 9 1 2 1차 정렬 1 7 9 3 2 2차 정렬 1 2 9 3 7 3차 정렬 1 2 3 9 7 4차 정렬 1 2 3 7 9 정렬을 할때 위와 같이 첫 번째 원소의 값을 그 뒤의 나머지 원소들 중 가장 작은 값과 바꾼다. 두번째 원소의 값을 그 뒤의 원소들 가장 작은 값과 바꾼다. 위와 같이 반복하면 정렬이 끝난다. 선택 정렬은 비교 하는데 N^2/2회나 되지만 데이터 교환에는 N번의 횟수면 된다. 때문에 정렬 데이터가 큰 경우 다른 정렬 알고리즘에 비해 유용하다. Big-O 표기법의 의한 계산 O(N^2) (단순 계산으로는 for문이 중첩되는 경우므로 N*N=N^2이 나온다.) #include #include #define MAX 100 #define TRUE 1 #define FALS.. [Algorith] 이진 트리 (Tree) - 레벨 순회 (Level-Order Traverse) A -> B -> C -> D -> E -> F -> G 순서로 나온다. 레벨 순회는 스택보다 큐를 사용하는 것이 바람직 하다. /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeQueue(void); extern void Put(NODE *); extern NODE *Get(void); extern int IsQueueEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는.. [Algorith] 이진 트리 (Tree) - 후위 순회 (Post-Oreder Traverse) /*------------------*/ /* main.c */ /*------------------*/ #include "Appendix.h" /* Definition of External Functions */ extern void InitializeStack(void); extern void Push(NODE *); extern NODE *Pop(void); extern int IsStackEmpty(void); /* Definition of Internal Functions */ void InitializeTree(void); // 트리의 기본적인 헤드와 엔드 노드를 만는다. void MakeTree(void); // 트리의 기본적으로 들어갈 데이터의 값을 만든다. void Traverse(NOD.. 이전 1 2 다음
