퀵 정렬(Quick Sort)

Quick Sort는 진짜 혼신의 힘을 다해서 정리할 것이다. 얘는 대학원 면접 단골 문제는 물론 지금까지 최고라고 또, 앞으로도 최고일거라는 호평을 받은 정렬 알고리즘이다.

퀵 소트는 분할과 정복으로 이루어진 알고리즘 중 하나이다. 따라서 매우 복잡하지만 성능만큼은 확실하다.

## Quick Sort process

1. 배열 a[l:r]에서 가장 오른쪽에 있는 원소를 pivot 이라고 선정한다. 피봇은 분할 원소이다.

2. 이 피봇을 기준으로 두개의 partition으로 분할한다. 그리고 이 파티션은 다음과 같은 성질을 따른다.

    - 분할 후 피봇은 a[i]로 들어가게 되는데, 이는 정렬 후 피봇이 들어가는 정확한 위치가 된다(즉, 정렬이 된다)

    - 왼쪽 파티션에 있는 원소 a[l] , ... a[i-1] 중 피봇보다 큰 원소는 없다. (즉, a[i]는 피봇보다 큰 원소일 수 있다)

    - 오른쪽 파티션에 있는 원소 a[i+1],...a[r] 중 피봇보다 작은 원소는 없다.

이러한 process를 갖고 quicksort는 왼쪽 파티션과 오른쪽 파티션에 대해 다시 quicksort를 순환적으로 적용한다. 이 순환 반복은 각 파티션이 하나의 원소 이하로 될 때 까지 반복한다.

 

ADL로 한 번 봐보자

quickSort(a[],l,r)
	// 배열 a[]의 부분 배열 a[l:r]을 오름차순 정렬
    if (r > l) then {
    	i <- partition(a[],l,r); // i는 파티션이 끝난 뒤 사용되는 피봇의 인덱스
        quickSort(a[],l,i-1);
        quickSort(a[],i+1,r);
    }
end quickSort()

또한 partition function의 ADL을 봐보자

partition(a[],l,r)
	// 가장 오른쪽 원소 a[r]을 피봇으로 하여 a[] 분할
     v <- a[r]; // 가장 오른쪽의 원소를 피봇
     i <- l-1; // left -> right 움직임
     j <- r; // right -> left 움직임
     for (;;) do {
     	do { i <- i+1; } while (a[i] < v); // 피봇값보다 작으면 i 증가
        do { j <- j-1;} while (a[j] > v); // 피봇값보다 크면 j 감소
        if (i>=j) then break; // i와 j가 교차하면 break
        a[i]와 a[j] 교환; // 왼쪽 포인터 값과 오른쪽 포인터 값 교환
        // i와 j 크로스 안될 때, 그 때 교환
     }
     a[i] 와 a[r] 교환; // pivot과 i의 값과 교환
     return i;
end partition()

 

이것만으로 이해하면 천재고, 난 천재보단 바보에 가깝기 때문에 무조건 예시 보고 이해해야한다. 따라서 예시로 알아본다.

 

[6,2,8,1,3,9,4,5,10,7] 를 정렬하는 과정을 한 번 봐보자

quicksort 1차 과정

여기서 -1 은 index가 넘어가는 것을 방지하기 위해서 삽입한다. 이의 필요성은 다다음 과정에서 나온다.

그림에서 보여지듯이 피봇은 맨 끝에 값으로 설정하고, i와 j가 피봇과 비교하여 큰지 작은지 구분하여 서로 교환한다.

그리고 마지막에서 두번째 줄에선 i는 피봇보다 큰 값을 찾다가 j는 피봇보다 작은 값을 찾다가 서로 인덱스의 크기가 역전되게 된다. 이럴 땐 피봇의 값과 i 위치의 값과 교환한다.

그리고 i는 7이 반환된다. partition이 끝난 후 리스트는 pivot을 중심으로 [6,2,5,1,3],4,[7,8,10,9] 이렇게 나뉘게 된다.

1차적으로 quicksort(a,l,i-1) 에 들어간다. 따라서 l = 1, r = i-1 = 7-1 = 6이 된다.

l = 1, r = 6인 상태로 partition이 진행된다. 그리고 피봇과 a[i] 가 교환되고, partition은 끝난다.

이 때 i는 return 4를 하게 되고 다시 quicksort(a,l,i-1) 에 들어간다. 그래서 r=4-1 = 3 이 되고 피봇이 1이 된다. 그리고 바로 i>j이므로 피봇과 교환이 되고 i는 1이 return 된다. 

여기부터 중요하다!!!

i = 1이 return 되고 다시 quicksort(a,l,i-1)에 들어가려 보니 l = 1, r = 0이  된다. 따라서 이는 첫번째 if 문 if r>l 에 어긋나므로 다음 quicksort(a,i+1,r) 에 들어가야한다. 이 때 기존의 r = 3 값이 되고 l은 2가 되서 if 문을 통과할 수 있다.

이 때, 이미 정렬이 되어 있으므로 i 값과 pivot 값이 같게 되서 변화가 없고 i = 3을 return 하게 된다. 그리고 두번째 quicksort(a,i+1,r) 을 통과한다.

이는 시간이 지날 수록 연속된다. (만약 손으로 정렬 과정을 한다면 이미 정렬이 됐으면 스킵한다.)

그리고 pivot값이 5가 됐을 때 유의미한 변화가 나타난다. 이 때, r = 6 이 되어야하고, ㅣ = 5가 될 때이다.

이렇게 해서 값이 교환이 된다. 

여기까지해서 처음에 pivot으로 나뉜 첫번째 부분을 정렬하였다. 

그리고 두번째 부분 [8,10,9] 부분을 정렬할 차례이다. 이 떄, l = 8이 되고, r = 10이 된다. (리스트의 끝 원소가 피봇)

따라서, 다음 그림처럼 나타난다.

요건 맨날 하던거니까 스킵한다.

 

# 과정 핵심 정리

- i >= j 일 때 pivot value 와 a[i] 바뀜.

- partition을 수행하고 pivot 기준으로 array가 분할 됨. -> 따라서 분할된 array를 끝까지 정렬해야지 알고리즘 끝

- ADL 외워놓는게 편함

 

# 시간 복잡도

평균적으론 \( O(NlogN) \) 최악의 경우 \( O(N^{2}) \), 이미 정렬된 array에 대해 퀵 sort하면 더 오래 걸림

python 코드는 다음과 같다.

def partition(a,l,r):
    v = a[r] # pivot
    i = l
    j = r - 1
    print('pivot : ',v)
    while True:
        while a[i] < v:
            i += 1
        while a[j] >= v:
            j -= 1
        if i >= j: break
        a[i],a[j] = a[j],a[i] # change
        print('In While ',a)
    a[i],a[r] = a[r],a[i] # change
    print('Out while ',a)
    print(f'i : {i}')
    return i

def quicksort(a,l,r):
    if r>l:
        i = partition(a,l,r)
        quicksort(a,l,i-1) # left
        quicksort(a,i+1,r) # right

    return a

a = [-1,11,15,7,2,8,5,3,1]
l = 1
r = len(a) - 1
quicksort(a,l,r)