목차
- Insertion sort
- quick sort
- merge sort
- heap sort
개략적인 개념
quicksort 는 partition 을 이용해서 정렬하는 것이다.이 파티션은 분할이란 뜻.
이게 쪼개는 것은 맞는데 조건이 있다. 쪼개는 녀석을 중심으로 구분이 되어야 한다는 것이다.
무슨 구분이겠는가 뭐 당연히 크거나 작거나 이런 것들일 것이다.
그래서 이 파티션의 핵심은
기준을 정하고 큰 부분과 작은 부분으로 나누는 것이다.
그러고 이 중심을 알려준다. 이 중심이 pivot 이다.
결국 어떤 기준으로 나누는 것이다. 이 어떤기준을 중심으로 작은 녀석을 한쪽으로 몰고 큰 녀석들을 반대 편으로 모는 것이다.
그러면 이 기준을 중심으로 나눴다고 볼 수 있는 것이다.
이 기준은 우리가 임의로 정한다. 예를 들면 중간값 같은 것들.
만약 우리가 학생들을 키를 기준으로 4그룹으로 나눈다고 하자. 그러면 아래처럼 할 수 있다.
160 이상은 오른쪽으로 160미만은 왼쪽으로 모여라고 할 것이다.
이 후에 오른쪽 그룹에선 다시 175 를 기준으로 작은 사람은 왼쪽, 175 이상인 사람은 오른쪽으로 모이게 한다.
그리고 왼쪽 그룹에선 다시 145 이상은 오른쪽 145 미만은 왼쪽으로 모이라고 한다.
이렇게 그룹을 나누는 것이 퀵소트의 "파티션(partition)"이다.
근데 만약 이 학급의 학생이 4명이라고 하고, 143, 147, 165, 178 이라고 생각해보자.
그러면 이 학급의 학생들은 이렇게 모이라고 동작만으로 정렬이 완성된다.
QuickSort
quicksort 의 전체적인 내용은 ref. 1 을 참고하자. 여기서는 ref.1 의 내용 중에서 in-place version , 그러니까 storage space 를 별로 사용하지 않는 방법에 대해서만 얘기할 것이다.partition 의 역할은 partition 함수를 실행하면, pivot 값을 중심으로 pivot 보다 작은 녀석들을 모두 왼쪽으로 옮기면, 자동으로 오른쪽에는 pivot 보다 큰 녀석이 남게 된다.
즉, 정렬이라는 것이 각 원소의 자리를 찾아주는 것이라고 한다면, partition 이 끝나면, pivot 의 자리가 정해진다고 보면 되겠다.
이 상황에서 마지막으로 pivot 값을 옮겨 놓으면, pivot 의 왼쪽에 pivot 보다 작은 값들이 있게 되고, 오른쪽에 pivot 보다 큰 값이 있게 된다. 아래에서 좀 더 자세하게 얘기하기로 하자.
Partition
여기서는 pivot 보다 작거나 같은 값들을 swap 하기로 하자.value <= pivot
5를 pivot 으로 선택했다.
먼저 pivot 을 가장 오른쪽으로 옮긴다.
2, 3, 4, 5, 7, 5, 3왼쪽에서 부터 pivot 보다 작은지 검사하고, 작으면 왼쪽으로 옮긴다.(왼쪽으로 옮기는 것을 enqueue 하는 것처럼 생각하면 된다.)
2, 3, 4, 3, 7, 5, 5
2, 3, 4, 3, 7, 5, 5 2 3, 4, 3, 7, 5, 5 2, 3 4, 3, 7, 5, 5 2, 3, 4 , 3, 7, 5, 5 2, 3, 4, 3 , 7, 5, 5
그러다가 pivot 보다 큰 값이 나오면 아무 일도 하지 않고, 그 다음 값을 검사한다.
2, 3, 4, 3 , 7, 5, 5 2, 3, 4, 3 , 7, 5, 5 2, 3, 4, 3, 5 , 7, 5
이제 pivot 바로 전까지 검사를 마쳤으면, 마지막으로 pivot 을 왼쪽으로 옮긴다.
2, 3, 4, 3, 5, 5 , 7
그러면, pivot 이 가장 오른쪽에 있는 list 가 하나 만들어진 것이다.
이 녀석을 남아있는 list 의 앞쪽으로 합치면, pivot 왼쪽에는 pivot 보다 작거나 같은 값들이 모여 있게 되고, 오른쪽에는 pivot 보다 큰 값만 남게 된다.
이 때의 pivot 이 가진 index 값이 중요하다.
pivot 을 중심으로 왼쪽을 partition 을 하고, 오른쪽을 partition 한다.
계속 partition 을 하면서 pivot 을 중심으로 계속 왼쪽에는 작은 수, 오른쪽에는 큰 수를 넣으면, 결국 모든 부분이 정렬되게 된다.
여기서 아래그림처럼 정확히 반으로 나뉘는 경우가 pivot 이 정확히 가운데값(mid) 을 가지는 경우이고, 그래서 partition 을 logn 번을 하게 되는 것이다.
반대로 최악의 경우는 pivot 이 한쪽 끝에 있는 값이어서 둘로 나눴을 때 한쪽이 0 이 되어서 결국 한쪽만 남는 경우다. 이렇게 계속해서 최소,최대값이 pivot 이 된다면, n-1 번의 partition 을 해야 돼서 최악의 시간(O(n2))이 소요될 것이다.
Pseudocode
ref. 1 에 보면 pseudocode 를 볼 수 있다.
그리고, 아래에는 python 으로 짠 간단한 코드를 볼 수 있다. 이해를 위해서 swap 과 enqueue 는 같은 역할을 하지만 구분해 놨다.
def swap(data, tail, b) : data[tail], data[b] = data[b], data[tail] def enqueue(data, tail, b) : data[tail], data[b] = data[b], data[tail]
def partition(input, left, right, pidx) : pivot = input[pidx] # swap(pidx, right) swap(input, pidx, right) tailIndex = left for i in range(left, right) : # enqueue value equal or less than pivot into left side queue if input[i] <= pivot : # swap(i, tailIndex) enqueue(input, i, tailIndex) tailIndex += 1 enqueue(input, tailIndex, right) return tailIndex def quicksort(input, left, right) : if left < right : # select and remove a pivot value from input pivotIdx = (left+right)/2 pivotNewIdx = partition(input, left, right, pivotIdx) print pivotNewIdx, input[left:pivotNewIdx], input[pivotNewIdx+1:right+1] quicksort(input, left, pivotNewIdx - 1) quicksort(input, pivotNewIdx + 1, right) if __name__ == '__main__': str = '2345753' left = 0 right = len(str)-1 quicksort(list(str), left, right)
See Also
- https://idea-instructions.com/ : 여러 알고리즘에 대한 그림이 있다.
댓글 없음:
댓글 쓰기