기본 정렬 알고리즘 : 병합 정렬, 퀵 정렬

참고 : 선택 정렬, 삽입 정렬, 버블 정렬https://hyunah-home.tistory.com/entry/%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC

기본 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬

 

 

④ 병합 정렬

 

▷ 아이디어

: 리스트를 두 개로 분할하고, 분할된 부분 리스트를 각각 재귀적으로 정렬한 후에 병합하여 전체 리스트를 정렬.

 

 

병합 과정 예시

 

▷ 알고리즘

1. 정렬할 데이터의 개수가 2개 이상이라면 중간 위치를 계산하여 두 부분 배열로 분할

2. 각각의 부분 배열에서 재귀 함수를 호출하여 부분 배열을 정렬

3. 정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 구성

 

 

 

▷ 프로그램

int sorted[MAX_SIZE]; //정렬 배열

//병합 알고리즘
void merge(int list[], int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int k = left;
    int w;
    
    //작은 순서대로 배열에 삽입
    while (i <= mid && j <= right){
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else sorted[k++] = list[j++];
    }
    
    //남은 데이터 삽입
    if (i > mid)
        for(w=j; w<=right; w++)
            sorted[k++] = list[w];
    else
        for(w=i; w<=mid; w++)
            sorted[k++] = list[w];
    
    //정렬된 배열 삽입
    for (w=left; w<=right; w++)
        list[w] = sorted[w];
}

//병합 정렬 알고리즘
void merge_sort(int list[], int left, int right){
    int mid;
    if(left < right){
        mid = (left+right)/2; //리스트 분할
        merge_sort(list,left,mid); //부분 리스트 정렬
        merge_sort(list,mid+1,right);
        merge(list,left,mid,right); //병합
    }
}

 

 

 

▷ 시간 복잡도

: 리스트의 크기를 n(=2^k)라고 가정하면 리스트를 정확히 log₂n번 나눌 수 있고, 각각의 병합마다 비교연산이 n번, 레코드의 이동은 2n번 발생(한 번의 교환마다 2번씩)하므로 전체적으로 O(nlog₂n)의 시간 복잡도를 가짐. 레코드를 연결 리스트로 구성하여 병합 정렬할 경우 크기가 큰 레코드 정렬시 다른 어떤 정렬 방법보다 매우 효율적. 안정적이며 데이터의 초기 분산 순서에 영향을 덜 받음

 

 

 

 

⑤ 퀵 정렬

 

▷ 아이디어

: 하나의 값을 중심으로 리스트를 그 값보다 작은 부분리스트와 큰 부분리스트로 분할하고 각각의 부분리스트를 다시 재귀호출하여 퀵 정렬

 

퀵 정렬 전체 과정

 

▷ 알고리즘

1. 정렬할 범위가 2개 이상의 데이터라면 축값(리스트의 첫 번째 원소값)을 기준으로 나뉜 2개의 리스트로 분할

1-1. 리스트의 맨 왼쪽과 맨 오른쪽 값을 각각 low와 high로 읽어오며 왼쪽에 축값보다 큰 값이 있고 오른쪽에 축값보다 작은 값이 있다면 서로 교환

1-2. low와 high가 교차한다면 종료. 시행을 멈춘 곳에서의 high값이 축값의 위치

2. 왼쪽은 축값보다 작은 리스트, 오른쪽은 축값보다 큰 리스트.

3. 축값을 제외한 각각의 리스트를 재귀 호출

 

 

 

▷ 프로그램

//분할 함수
int partition(int list[], int left, int right){
    int low = left;
    int high = right+1;
    int pivot = list[left];
    int temp;
    
    do{
        do
            low++;
        while(low<=right && list[low]<pivot); // 왼쪽에 축값보다 큰 값이 있다면 정지
        
        do
            high--;
        while(high>=left && list[high]>pivot); // 오른쪽에 축값보다 작은 값이 있다면 정지
        
        if(low<high){ // 양쪽 값을 교환
            temp = list[low];
            list[low] = list[high];
            list[high] = temp;
        }
    }while(low<high); // 인덱스가 교차된다면 중지
    
    // high의 위치가 축값의 적절한 위치이므로 교환
    temp = list[left];
    list[left] = list[high];
    list[high] = temp;
    
    return high; // 축값의 위치를 반환
}

//퀵 정렬 알고리즘
void quick_sort(int list[], int left, int right){
    if(left < right){ //left==right라면 원소가 1개인 것
        int p = partition(list,left,right);
        quick_sort(list,left,p-1);
        quick_sort(list,p+1,right);
    }
}

 

 

 

▷ 시간 복잡도

: 거의 균등하게 부분리스트로 분할되는 최선의 경우, 병합 정렬과 동일하게 총 log₂n번 분할되고, 각각의 경우마다 n번의 비교 연산이 실행되므로 O(nlog₂n)의 시간 복잡도를 가짐. 극도로 불균등하게 부분리스트로 분할되는 최악의 경우(이미 정렬된 리스트)에는 O(n²)의 시간 복잡도를 가지지만 중앙값을 축값으로 선택하면 불균등 분할을 완화할 수 있음. 일반적으로 왼쪽, 오른쪽, 중앙값 3개 중 하나를 선택하는 방법이 많이 사용됨.