[자료구조] 정렬

record단위로 정렬

• record는 field로 이루어짐
• key field로 record를 구별

Internal Sorting: 모든 데이터가 주기억장치에 저장된 상태에서 정렬

External Sorting: 외부기억장치에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬

 

Stability(안전성): 동일한 키 값을 갖는 레코드들의 상대적 위치가 정렬 후에도 바뀌지 않음

---

Selection Sort (선택 정렬)

External Sorting

정렬된 왼쪽 리스트와 정렬 안 된 오른쪽 리스트

처음에는 왼쪽 비어 있고, 오른쪽에서 왼쪽으로 옮기면서 정렬

 

Internal Sorting

맨 앞에 들어가야하는 애부터 swapping

 

Time Complexity: O(n^2)

비교 횟수: O(n^2)

이동 횟수: 3(n-1)

 

Unstable

In-place sort - Space Complexity: O(1)

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

void selection_sort(int list[], int n){
    for(int i = 0; i < n-1; i++){
        least = i;
        //제일 작은 애 찾기
        for(int j = i+1; j < n; j++)
            if(list[j] < list[least]) least = j;
        SWAP(list[i], list[least], temp);
    }
}

---

Insertion Sort (삽입 정렬)

정렬되어 있는 부분에, 새로운 레코드를 정렬이 유지되는 위치에 삽입

 

Time Complexity: O(n^2)

비교 횟수: O(n)

이동 횟수: O(n^2)

+ 이미 정렬 되어있으면 O(n) - 대부분 정렬되어 있으면 매우 효율적 

 

Stable

In-place sort - Space Complexity: O(1)

void insertion_sort(int list[], int n){
    int key; //지금 삽입할 것

    for(int i = 1; i < n; i++){
        key = list[i];
        
        //내 자리 찾을 때까지  
        for(int j = i-1; j >= 0 && list[j] > key; j--)
            list[j+1] = list[j]; //하나씩 오른쪽으로 옴기기
            
        list[j+1] = key; //삽입   
    } 
}

---

Bubble Sort

붙어있는 2개의 레코드를 비교하여 순서가 반대이면 서로 교환

 

각 round에 가장 큰 record가 최종 위치를 찾아감  

 

Time Complexity: O(n^2)

비교 횟수: O(n^2)

이동 횟수: O(n^2)

 

Stable

In-place sort - Space Complexity: O(1)

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

---

Shell Sort

전체 리스트를 일정 간격(gap-보통 홀수)으로 나누고 각각 삽입정렬

gap이 점점 줄어든다.

 

그룹이 index {0~4}, {5~9}, {10~14}가 아니고 index {0,5,10}, {1,6,11}, {2,7,12} 이다.

 

Time Complexity: O(n^2)

평균 Time Complexity : O(n^1.5)

 

Unstable

In-place sort - Space Complexity: O(1)

inc_insertion_sort(int list[], int first, int last, int gap){
    int key;
    for(int i = first + gap; i <= last; i = i + gap){
        key = list[i];
        //조건이 for문 안에 key < list[j]
        for(int j = i-gap; j >= first && key < list[j]; j = j-gap)
            list[j+gap] = list[j]; //j+gap == i
        list[j+gap] = key;    
    }
}

void shell_sort(int list[], int n){
    for(int gap = n/2; gap > 0; gap = gap/2){
        if((gap%2) == 0) gap++; //gap은 홀수
        
        for(int i = 0; i < gap; i++)
            inc_insertion_sort(list, i, n-1, gap);
    }
}

---

Merge Sort (합병 정렬)

Divide & Conquer

리스트를 절반으로 나누고 반반 먼저 정렬, 나눈 걸 합치면서 정렬

계속 쪼개서 1개가 될때까지 쪼개기 (재귀)

 

 

                                                        새로운 리스트에 정렬하여 합병

merge

Time Complexity: O(n^2)

비교 횟수: O(nlogn) - 레벨이 logn개, 각 레벨당 n번 비교

이동 횟수: 2nlogn - 레벨이 logn개, 각 

 

Stable

Not In-place sort 

int sorted[MAX_SIZE]

void merge(ine list[], int left, int mid, int right){
    int i = left; //정렬된 왼쪽 리스트
    int j = mid + 1; //정렬된 오른쪽 리스트
    iint k = left; //왼쪽 오른쪽을 합쳐서 정렬될 리스트
    
    while(i <= mid && j <= right){
        if(list[i] <= list[j]) sorted[k++] = list[i++];
        else sorted[k++] = list[j++];
    }
    
    if(i > mid) //왼쪽은 다 들어가고 오른쪽이 남음
        for(int l = j; l <= right; l++)
          sorted[k++] = list[l];
    else //오른쪽이 다 들어가고 왼쪽이 남음
        for(int l = i; l <= mid; l++)
            sorted[k++] = list[l];
    
    //원래 배열로 복사하기
    for(int l = left; l <= right; l++)
        list[l] = sorted[l]; 
}

O(n)

void merge_sort(int list[], int left, int right){
    int mid;
    
    if(left < right){ //전 단계 sort가 잘 끝났을 때
        mid = (left + right)/2; //반 쪼개서 
        
        //재귀적 호출
        merge_sort(list, left, mid);
        merge_sort(list, mid + 1, right);
        
        merge(list, left, mid, right);`
    }
}

---

Quick Sort

리스트를 비균등 분할하고 각 부분 리스트를 다시 Quick Sort

Pivot(기준점): 값들 중 중간값 (우리는 가장 왼쪽값으로 잡음)

 

 

Time Complexity

최선

비교 횟수: O(nlogn) - 레벨이 logn개, 각 레벨당 n번 비교

이동 횟수: 비교횟수에 비해 적어서 무시 

최악

비교 횟수: O(n^2) - 레벨이 n개, 각 레벨당 n번 비교

이동 횟수: 비교횟수에 비해 적어서 무시 

 

Unstable

In-place sort 

int partition(int list[], int left, int right){
    int pivot = list[left];
    int low = left;
    int high = right + 1;
    int temp;
    
    do{
        do low++;
        while (low < right && list[low] < pivot);
        
        do hight--;
        while(high >= left && list[high] > pivot);
        
        if(low < high) SWAP(list[low], list[high], tmep);  
        
    }while(low < high);
    
    SWAP(list[left], list[hight], temp); //다시 복구
    return high;
}

void quick_sort(int list[], int left, int right){
    if(left < right){
        int q = partion(list, left, right);
        
        quick_sort(list, left, q-1);
        quick_sort(list, q+1, right);
    } 
}

---

Radix Sort (기수 정렬)

record를 비교하지 않고 정렬

bucket은 큐

 

O(dn)의 Time Complexity를 가짐 (d는 key의 자리 수/알파벳의 개수)

 

한자리수의 기수정렬

자리수에 따라 bucket에 넣었다가 꺼내면 정렬

 

Stable

Not in-place sort

---

두자리수의 기수정렬

1의 자리만 보고 한자리수의 기수정렬 한 후

10의 자리 보고 한자리수의 기수정렬

#define BUSXETS 10 //0~9
#define DIGITS 4 //최대 4자리인 경우

void radix_sort(int list[], int n){
    int factor = 1;
    QueueType queues[BUCKETS];
    
    //초기화
    for(int b = 0; b < BUCKETS; b++) init(&queues[b]);
    
    for(int d = 0; d < DIGITS; d++){
        //넣기
        for(int i = 0; i < n; i++)
            enqueue(&queues[(list[i]/factor) % 10], list[1]);
        //빼기    
        for(int b = 0; b < BUCKETS; b++)
            while(!is_emppty(&queues[b]))
                list[i++] = dequeue(&queue[b]);
                
        factor *= 10;        
    }    
}