[Algorithm] 정렬 알고리즘에 대하여 2

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.

---

이번에는 포스트에서는 분할정복 기법을 이용하는 병합정렬과 퀵정렬에 대해 포스트하겠습니다.

이전 포스트는 하단의 링크를 참고해주세요.

2019/06/26 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 1

 

 

 

분할 정복(divide & qonquer)

분할 : 문제를 작은 문제로 분할한다. (큰 문제와 작은 문제는 동일한 문제이며, 범위만 다르다.)

정복 : 작게 분할된 문제의 해를 구한다.

합병 : 작게 분할된 문제의 해를 합쳐, 큰 문제의 해를 구한다.

 

 

 

대표적인 정렬 알고리즘

퀵 정렬(quick sort)

코드

void quickSort(int[] arr, int stat, int end) {
	if(start < end) {
        // 피벗을 선정한 후, 작은 값들은 왼쪽으로, 큰 값은 오른쪽으로 이동시킨다.
        // 그리고 피벗의 인덱스를 반환한다.
        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot-1);
        quickSort(arr, pivot+1, end);
    }
}

int partition(int[] arr, int start, int end) {
    pivot = arr[end];  
    // 피벗보다 작은 값들 중에서, 마지막 요소의 인덱스
    int i = start - 1;
    
    for (int j = start; j < end; j++) {
        // 피벗보다 작은 값이 발견된다면, i번째 요소와 자리를 바꾼다.
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    // 피벗을 제자리에 넣어준다.
    swap(arr[i+1], arr[end]);
    
    // 피벗의 인덱스를 반환한다.
    return (i + 1);
}

분할 정복(divide & qonquer)을 이용한 정렬.

데이터 중에서 임의의 값을 pivot으로 설정한다. pivot보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 이동시킨다.

피벗 왼쪽과 오른쪽에 대해 반복한다.

따로 합병 과정은 없다.

 

시간복잡도

• 한쪽은 0개, 한쪽은 n-1개로 분할된 경우의 시간복잡도 : T(0) + T(n-1) + O(n)
  • partition함수에서 비교 횟수가 n-1이므로 O(n)을 더한다.
• 항상 (n-1)/2, (n-1)/2개로 분할된 경우의 시간복잡도 : 2T(n/2) + O(n)

T(n) = O(0) + O(1) + ... + O(n-1) + O(n) = O(n^2)

T(n) = ... = O(nlogn)

• 최악 : O(n^2)
• 최선 : O(nlogn)

 

 

병합 정렬(merge sort)

코드

void mergeSort() {

}

분할 정복(divide & qonquer)을 이용한 정렬.

데이터를 반으로 쪼갠다. 데이터가 아토믹(atomic)해질 때 까지 반복한다. (관심있는 데이터에만 집중하는 과정)

아토믹한 두 데이터를 비교한 후, 합병하면서 정렬한다. 모든 데이터가 합병될 때 까지 반복한다.

 

시간복잡도

• 왼쪽 데이터에 대한 시간 복잡도 : T(ceil(n/2))
• 오른쪽 데이터에 대한 시간 복잡도 : T(floor(n/2))
• 나눠진 두 데이터를 하나의 데이터로 합병하기 위해 비교하는 횟수 : n

T(n) = 2T(n/2) + n = O(nlogn)

• 최악 : 
• 최선 : 
• 평균 : O(nlogn)