[두근두근 자료구조] 13,14장

13장 정렬

- 선택 정렬 : O(n^2)

#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

void selection_sort (int list[], int n)
{
	int i, j, least, tmp;
    for(i=0; i<n-1; i++) {
    	least = i;
        for(j = i+1; j < n; j++)
        	if(list[j] < list[least]
            least = j;
        SWAP(list[i], list[least], tmp);
        }
}

 

 

- 삽입 정렬 O(n^2)

- 버블 정렬 : O(n^2)

void bubble_sort (int list[], int n)
{
	int i, j, bChanged, tmp;
    for(i = n-1; i>0; i--){
    bChanged = 0;
    for(j=0; j<i ; j++)
    	if(list[j] > list[j+1]) {
        SWAP(list[j], list[j+1], tmp);
        bChanged = 1;
        }
    if(!bChanged) break;
 	}
}

 

- shell 정렬

- 병합정렬 O(n*log(n)) merge sorting 

static void merge(int list[], int left, int mid, int right) {
    int i, j, k = left, l;
    static int sorted[MAX_SIZE];
    
    for(i=left, j= mid+1; i <= mid && j<= right)
        sorted[k++] = (list[i] <= list[j]) ? list[i++] : list[j++];
        if(i > mid)
            for(l=j; l <= right ; l++, k++)
                sorted[k] = list[l];
        else
            for(l=j ; l <= right ; l++, k++)
                sorted[k] = list[l];
            for(l= left; l<=right ; l++)
                list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right){
    if(left < right) {
        int mid = (left+right)/2;
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge_sort(list, left, mid, right);
    }
}

- 퀵 정렬

- 기수 정렬 (radix sorting)

void radixSort(int list[], int n)
{
    Queue queue[BUCKETS];
    int factor =1, i, b, d;
    
    for(i=0 ; i<BUCKETS ; i++)
        init_queue(&queue[i]);
        
    for(d=0 ; d<DIGITS ; d++){
        for(i=0; i<n; i++)
            enqueue(&queues[(list[i]/factor)%10], list[i]);
        
        for(b=i=0 ; b<BUCKETS ; b++)
            while(!is_empty(&queues[b]));
                list[i++] = dequeue(&queues[b]);
                
        factor *= 10;
    }
}

---

14장 탐색

- 순차 탐색 (sequential search)

- 색인 순차탐색(Indexed sequential search)

- 이진 탐색 (binary search) : 정렬된 배열의 탐색에 적합

- 보간탐색 (interpolation search) : O(logn)

 

- 해싱 (hashing)

충돌과 오버플로가 발생할 수 있다.