스파르타 내배캠 Unity 3기 8일차

아~ (무슨 말이지?)

 

 

 

알고리즘... 예상은 했지만 예상밖으로 난해하네?

 

오늘부터 알고리즘 파트를 공부하기 시작했다.

역시나 초반부터 이해하기 힘든 녀석을 맞이했다.

 

그래서 적기 시작하는 TIL

 

Quick Sort(퀵 정렬) 알고리즘  

코드에 앞서 퀵 정렬 알고리즘에 대해 알아보자.

 

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

출처 : 위키백과

퀵 정렬 알고리즘.gif 출처:위키백과

 

 

음... 오늘 배운 코드를 보도록 하자

void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

핵심은 Partition 메서드이다.

int[] arr = [ 5, 3, 6, 1, 2, 4 ] 기준으로 설명해보자.

 

QuickSort 메서드의 매개변수로 (arr, 0, arr.Length - 1) 을 전달하자.

 

left == 0, right == 5 이므로 if 문의 첫 줄인 Partition 함수가 실행된다.

 

이 때, for문을 루프하면 다음과 같이 진행된다.

 

 

현재 배열에서 Partition 메서드의 pivot == 4이다.

for 문을 루프 해 배열의 각 값[ j = 0 ~ 5 (j < arr.Length - 1) ] 을 pivot 과 비교한다.

 

pivot 보다 작으면?

1. i++;

2. arr[i] 와 arr[j] 교체

3. j++;

 

pivot 보다 크면?

1. j++;

 

위 조건을 따르면 pivot 보다 큰 값들이 점점 오른쪽으로 옮겨진다.

for문이 끝나고 마지막으로 i + 1 값과 pivot을 교체 하게되면

pivot의 위치를 기준으로 오른쪽은 pivot 보다 큰 값이, 왼쪽은 작은값이 위치한다.

 

 

중요한 것은 이 한 번의 Partition으로 정렬이 되는것이 아니라

pivot이 중간값이 되고 그 위치의 Index를 반환한다는 것이다.

 

만약 배열이 [1, 2, 3, 4, 5, 6] 이었다면?

for문 루프에서 모든 조건이 true가 되어 자기 자신의 값을 교체 하며 for문 밖의 Swap 에도 변화가 없다.

 

만약 배열이 [6, 5, 4, 3, 2, 1] 이었다면?

for문 루프에서 모든 조건이 false 가 되어 i = -1을 유지하고 Swap은 일어나지 않는다.

for문을 빠져나와 Swap 시 arr[0] 과 arr[5]가 교체되어 [1, 5, 4, 3, 2, 6] 이 된다.

 

하나도 정렬이 안 된것 같지만 pivot을 제외한 모든 값이 1 보단 크다.

그러므로 "pivot 기준 오른쪽은 pivot 보다 큰 값" 에 부합한다.

 

이렇게 첫 Partition으로 pivot을 중간값에 위치했고 어느정도 정렬도 되었다.

그 후 Partition 으로 반환된 pivot Index를 기준으로 좌, 우 부분에 대한 QuickSort를 재귀적 호출한다.

QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);

 

위에서 보듯 모든값에 대한 조건이 true이든 false이든 반드시 끝나게 되고 정렬이 이루어지게 된다.

이를 반복하면 결국 각각의 부분들의 정렬이 완료되고 최종적으로 완전 정렬된 배열이 나오게 된다.

[다만 중복된 값이 있을 경우엔 이들에 대한 순서는 달라질 수 있어 불안정 정렬이라 부른다.]

 

이를 그림으로 표현하면 이런 느낌일 것이다.

0123