분할 정복 Swift

 

 

 

분할정복

분할 정복은 문제를 부분문제로 나누어 문제를 해결할 수 있는단위까지 나눈 후, 해결하고 다시 조합하는 방법이다.

분할정복은 세단계로 구성되어있다.

 

분할: 문제를 분할할 수 있을 만큼 같은 유형의 문제로 분할한다.

정복: 분할된 작은 문제를 해결한다.

조합: 해결된 작은 부분문제들을 조합하여 정답을 출력한다.

 

 

※ 분할정복과 동적 계획법 차이:

분할정복은 큰 문제를 여러개의 작은 문제로 나누어 해결하고, 이를 모두 조합한다.

동적계획법은 작은 문제부터 해결하여 기록하고, 기록된 정보를 통해 큰문제를 해결해나간다.

 

분할정복은 대표적으로 합병정렬과 퀵 정렬이 있다.

 

 

합병정렬

분할정복의 대표적인 정렬 알고리즘이다.

 

합병정렬의 단계

1. 주어진 배열의 크기가 0또는 1이라면 이미 정렬이 되있다고 간주하고, 그렇지 않다면 2개의 부분배열로 나눈다.

2. 부분배열의 크기가 정렬할 수 있을만큼 작지않다면 1번을 재호출한다.

3. 나눠진 부분배열을 합친다. 이때 순서에 맞춰서 정렬한다.

4. 부분배열을 조합하여 결과를 출력한다.

 

합병정렬의 특징:

- 합병정렬의 조합단계에서 따로 저장해둘 배열로부터 값을 가져오므로 입력과 같은 공간의 임시배열이 필요하다.

- 재귀호출로 인해 오버헤드가 발생할 수 있다.

- 연결리스트를 정렬할때는 다른 정렬방법보다 더 효율적이다.

 

Swift 코드로 구현

 

// 합병 정렬
func mergeSort(arr: inout [Int], p: Int, q: Int) -> [Int] {
	// 따로 저장해둘 공간(입력된배열의 크기만큼)
    var result = Array(repeating: 0, count: arr.count)
    // 배열의 크기가 1 또는 0이 될때까지 최대로 나누어준다.
    if p < q {
        // 배열의 중간인덱스
        var k = (p + q) / 2
        // 배열을 둘로 나누었을때, 왼쪽배열과 오른쪽배열
        var leftArr = mergeSort(arr: &arr, p: p, q: k)
        var rightArr = mergeSort(arr: &arr, p: k+1, q: q)
        
        // 배열이 최대로 나누어졌을때 아래 행동이 시작된다.
        // 분할된 배열들을 정렬하며 합친다.
        var i = p
        var j = k+1
        var d = p
        
        // 왼쪽배열과 오른쪽배열중 한 배열이 모두 정렬이 완료될때까지
        while i <= k && j <= q {
            // 왼쪽배열 원소가 더크면 오른쪽배열 원소를 넣고, 오른쪽배열 원소가 더 크면 왼쪽배열 원소를 넣는다.
            if leftArr[i] < rightArr[j] {
                result[d] = leftArr[i]
                i += 1
            } else {
                result[d] = rightArr[j]
                j += 1
            }
            d += 1
        }
        // 한쪽의 배열이 모두 정렬되었을때, 다른 한쪽은 원소가 남아있기때문에 그대로 붙여준다.
        // 남아있는 원소는 이미 이전에 정렬되어있는 원소기때문에 그대로 붙여도 좋다.
        if i > k {
            for index in j...q {
                result[d] = rightArr[index]
                d += 1
            }
        } else if j > q {
            for index in i...k {
                result[d] = leftArr[index]
                d += 1
            }
        }
        
        // 정렬된 원소를 배열에 넣고 리턴
        for i in p...q {
            arr[i] = result[i]
        }
    }
    return arr
}

 

입력 & 결과:

var A = [37, 10, 22, 30, 35, 13, 25, 24]
print(mergeSort(arr: &A, p: 0, q: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]

 

위 코드 재귀호출의 흐름은 다음과 같다.

1. 왼쪽배열을 분할

2. [37, 10] 정렬 후 결합

3. [22,30] 정렬 후 결합

4. 두 배열을 정렬 후 결합

5. 왼쪽배열: [10,22,30,37]

6. 오른쪽배열을 분할

7. [35,13] 정렬 후 결합

8. [25,24] 정렬 후 결합

9 두 배열을 정렬 후 결합

10. 오른쪽 배열: [13, 24, 25, 35] 

11. 왼쪽배열과 오른쪽배열을 정렬 후 결합하여 리턴

 

이름	최선	평균	최악	메모리
합병정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(n)

 

 

퀵정렬

퀵정렬은 임의의 수 하나를 골라, 그 수보다 작으면 왼쪽에, 크다면 오른쪽에 정렬하는 방법이다.

 

퀵정렬 과정

정복: 임의의수 n을 기준으로 n보다 작은수는 왼쪽배열, n보다 큰수는 오른쪽배열에 배치

분할: 배치된 배열에서 왼쪽배열과 오른쪽배열 재귀호출

 

퀵정렬은 정복을 먼저하고 분할하여 재귀호출을 한다.

 

세부과정

1. 기준이되는 원소를 선택

2. 기준원소의 인덱스를 저장하고, 나머지 원소를 검사하며 기준원소보다 작다면 인덱스+1 후 원소와 저장된인덱스와 자리바꿈

3. 모든 원소 검사 후 기준원소와 인덱스와 자리바꿈

(여기까지 완료된다면 배열은 기준원소를 기준으로 왼쪽에는 작은값, 오른쪽엔 큰값 배치됨) (정복)

4. 기준원소를 제외한 왼쪽배열과 오른쪽배열을 재귀호출한다.(분할)

5. 1-4를 반복하여 결과 도출

 

코드로 구현하면 다음과 같다.

// 퀵 정렬
func quickSort(arr: inout [Int], left: Int, right: Int) -> [Int] {
    // 배열의 크기가 2 이상이면 정복, 아니면 그냥 출력
    if left < right {
        // 기준점 선택(가장왼쪽)
        var pivot = arr[left]
        // 기준점이 위치할 곳을 저장
        var j = left
        // 기준점을 제외한 배열의 원소들을 검사
        for i in left+1...right {
            // 원소가 기준점보다 작다면 j위치에 있는 원소와 바꿈
            // 원소가 기준점보다 크다면 패스
            // 이렇게 반복하면 j위치보다 이전에 위치한 원소들은 기준점보다 작은 원소들이다.
            if arr[i] < pivot {
                j += 1
                arr.swapAt(i, j)
            }
        }
        // 기준점과 j위치와 원소 바꾸기
        // 기준점은 중간에 위치하게되고, 기준점 왼쪽은 기준점보다 작은원소, 오른쪽은 기준점보다 큰원소가 배치됨
        arr.swapAt(j, left)
        // 분할
        // 왼쪽배열로 재귀호출
        // 오른쪽배열로 재귀호출
        quickSort(arr: &arr, left: left, right: j-1)
        quickSort(arr: &arr, left: j+1, right: right)
    }
    
    return arr
}

입력 및 결과:

var A = [25, 10, 22, 30, 35, 13, 37, 24]
print(quickSort(arr: &A, left: 0, right: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]

 

위 코드 재귀호출의 흐름은 다음과 같다.

1. 기준점:25 를 기준으로 [작은값, 25, 큰값] 배치

2. [작은값], [큰값] 재귀호출

3. 1-2 반복(기준점을 제외한 원소가 없을때까지)

 

이름	최선	평균	최악	메모리
퀵정렬	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)

 

퀵정렬의 최악의경우는 이미 정렬된 데이터를 정렬할 경우이다.