The Master of FT

merge(list, left, mid, last): // 2개의 인접한 배열 list[left..mid]와 list[mid+1..right]를 합병 b1←left; e1←mid; b2←mid+1; e2←right; sorted 배열을 생성; index←0; while b1≤e1 and b2≤e2 do if(list[b1]<list[b2]) then sorted[index]←list[b1]; b1++; index++; else sorted[index]←list[b2]; b2++; index++; 요소가 남아있는 부분배열을 sorted로 복사한다; s..

// gap 만큼 떨어진 요소들을 삽입 정렬 // 정렬의 범위는 first에서 last inc_insertion_sort(int list[], int first, int last, int gap) { int i, j, key; for(i=first+gap; i<=last; i=i+gap){ key = list[i]; for(j=i-gap; j>=first && key<list[j];j=j-gap) list[j+gap]=list[j]; list[j+gap]=key; } } // void shell_sort( int list[], int n ) // n = size { int i, gap; for( gap=n/2; ..

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { int i, j, temp; for(i=n-1; i>0; i--){ for(j=0; j<i; j++) /* 앞뒤의 레코드를 비교한 후 교체 */ if(list[j]>list[j+1]) SWAP(list[j], list[j+1], temp); } } 이동횟수 최악: 역순정렬 이동 = 3*비교 최상: 이미정렬 이동 = 0 평균: O(n2) 애플릿 확인

void quick_sort(int list[], int left, int right) { if(left<right){ int q=partition(list, left, right); quick_sort(list, left, q-1); quick_sort(list, q+1, right); } } 최상의 경우: 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 2->1 4->2 8->3 … n->log2n 각 패스안에서의 비교횟수: n 총비교횟수: n log2n 총이동횟수: 비교횟수에 비..