반응형 프로그래머의 길/알고리즘22 합병 정렬(Merge Sort) u 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함 u 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임 u 두 부분배열의 크기가 동일하도록 분할함 u 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨 u 순차적 방식에 의해 데이터를 접근함 u 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능 u N 에 비례하는 추가 기억장소가 필요함 u 안정적이지만 제자리 정렬은 아님 MergeSort(a[], l, r) if (r > l) then { m ← (r+l)/2; MergeSort(a[], l, m); MergeSort(a[], m+1, r); Merge(a[], l, m, r); } end MergeSort() Merge(a.. 2007. 4. 2. 버블 정렬 구현 #include #define MAX 100 void zigzag(int *,int, int *, int *); void main() { int table[MAX], num, rep_no, exchg_no,i; rep_no = exchg_no=0; printf("Input Data Number : "); scanf("%d", &num); printf("\n Input Data \n"); for(i=0;i 2007. 4. 2. 버블 정렬(Bubble Sort) 2. 버블정렬 Bubble Sort는 가장 기본적이고 초보적인 Sorting 방법으로써, 서로 인접한 데이터들을 뒤에서부터 자리바꿈하면서 정렬하는 방법이다. (Selection Sort는 앞에서부터 정렬한다.) 효율성은 떨어지나, 구현이 간단하여 속도가 별로 중요하지 않은 경우에 널리 쓰이는 방법이다. 입력자료 : 4 7 3 1 5 8 2 6 1. 4와7을 비교한다. 7이 더 크므로 변화 없다. --> 4 7 3 1 5 8 2 6 ↑ ↑ 2. 7과 3을 비교한다. 3이 더 작으므로 바꾼다. --> 4 7 3 1 5 8 2 6 ↑ ↑ 3. 7과 1을 비교한다. 1이 더 작으므로 바꾼다. --> 4 3 7 1 5 8 2 6 ↑ ↑ 4. 7과 5를 비교한다. 5가 더 작으므로 바꾼다. --> 4 3 1 7 5.. 2007. 4. 2. 후위식 계산기 #include #include #include #define MAX 100 int integer(char *); void push(int); int pop(); int *ptr, *top, *bottom; void main() { int op1, op2; char str[81]; // int *i; ptr = (int *)malloc(MAX*sizeof(int)); top = ptr; bottom = ptr+MAX-1; // printf("%d ", top); // printf("%d", bottom); printf("후위식 입력 : "); do { scanf("%s", str); switch(*str) { case '+': op2 = pop(); op1 = pop(); push(op1 + op2); .. 2007. 3. 30. 이전 1 2 3 4 5 6 다음 반응형
