/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박성현 ' 의 내용을 토대로 작성되었습니다. */
참고 자료
[정렬 - 퀵 정렬] : http://dawoonjeong.com/algorithm-sort-quick/
1. 퀵 정렬
퀵 정렬은 이름에서 부터 퀵이 들어간 빠른 정렬 알고리즘이다. 퀵 정렬은 전쟁 전략 중의 하나인 '분할 정복'에 기반한 알고리즘이다. 분할 정복 전략은 적군의 전체를 공략하는 대신, 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 전법이다. (분할 정복에 대한 자세한 내용은 다른 게시물에서 다루겠다.)
퀵 정렬 예시
퀵 정렬은 다음과 같은 과정으로 분할 정복을 이용해 정렬을 수행한다.
- 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소(pivot)의 왼편에, 큰 값은 오른편에 위치시킨다.
- 기준 요소 왼편에는 기준 요소 왼편에는 기준 요소보다 작은 요소들이 모여 있고 오른편에는 큰 요소들이 모여 있다. 이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다.
- 1과 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다.
퀵 정렬 코드
퀵 정렬은 pivot 의 위치에 따라 코드 구현이 달라진다. 이번에는 피벗값을 첫 번째 값으로 할 때와 중앙 값일 때 각각 코드를 구현해보았다. 구현하기에 앞서 퀵 정렬의 코드를 구현할 아이디어를 살펴보자.
퀵 정렬 코드 구현에 있어서 핵심은 다음과 같다.
- 배열을 데이터 집합의 자료구조로 사용할 때, 분할은 어떻게 수행해야 하는가? (링크드 리스트처럼 삽입/삭제가 자유롭지 못함)
- 반복되는 분할 과정을 어떻게 처리할 것인가?
첫 번째 질문에 대한 답으로 우리는 '수색 섬멸 작전'을 사용할 것이다. 배열에서는 삽입과 삭제가 자유롭지 못하다. 그렇기 때문에 분할 정복을 위한 작전이 필요하다.
'수색 섬멸 작전'은 정찰병 2명을 투입해서 한 명은 왼쪽부터 오른쪽 방향을 데이터 집합을 검사하면서 기준보다 큰 요소를 찾고, 또 한 명은 오른쪽부터 왼쪽 방향으로 검사하면서 기준보다 작은 요소를 찾는다. 그리고 찾아낸 두 값을 교환(swap)한다. 계속해서 값을 찾아내 교환하다보면 정찰병들은 하나의 값에서 만나게 된다. 정찰병이 만난 값과 피벗 값을교환하는 것으로 작전을 종료한다.
첫 번째 과정을 통해 우리는 피벗 값 기준 왼쪽으로는 작은 값들이 모이고 오른쪽에는 큰 값들로 모인 2 개의 분할로 볼 수 있다. (피벗 값은 이미 확정이므로 제외) 이로써 첫 번째 문제에 대한 답을 찾았다!
두 번째 질문인 '반복되는 분할 과정은 어떻게 처리할까?'의 답은 바로 '재귀'이다. '수색 섬멸 작전'을 보다보면 이 작전은 재귀를 이용하는데 최적화 되어있다고 볼 수 있다. 하나의 배열이 주어지면 왼쪽, 오른쪽의 2개의 배열이 생긴다. 왼쪽, 오른쪽 배열을 각각 기준으로 다시 수색 점멸 작전을 진행하면 각각 2개의 배열을 또 얻을 수 있을 것이다. 이러한 과정을 반복하다보면 데이터가 1개가 남아 더 이상 쪼갤 수 없다. 이 때가 재귀를 탈출할 때이다.
위 방법을 통해 퀵 정렬을 구현해보자.
1. pivot 값이 첫 번째 기준
object QuickSort {
// pivot 값이 첫 번째 값
fun sortByFirst(arr: Array<Int>, start: Int = 0, end: Int = arr.size - 1) {
//탈출 조건 : 원소가 하나 남을 경우
if (start >= end){
return
}
//수색 작전 시작
//Index
// 기준 값으로 첫번째 값 설정
val pivot: Int = start
// 초깃값으로 왼쪽 시작값 / 오른쪽 마지막 값 설정
var left: Int = start + 1
var right: Int = end
// 수색 작전 시작
// 왼쪽과 오른쪽이 만날 때 동안 실행
while (left < right){
//왼쪽은 pivot 값보다 작은 값 pass
// [방법 1]. left의 최댓값 end + 1 조건의 순서를 바꾸면 error!
while (left <= end && arr[left] <= arr[pivot]){
left++
}
// [error]. left의 최댓값 end, 단 마지막 값 검사 x -> 중복된 배열에서 마지막 값을 정렬 못함..
//while (left < end && arr[left] <= arr[pivot]){
// left++
//}
//오른쪽은 pivot 보다 큰 값 pass
while (arr[right] > arr[pivot] && pivot <= right){
right--
}
// 만약 아직 수색병이 만나기 전
if (left < right) {
arr.swap(left, right)
}
// 만나거나 지나칠 때
else {
//피벗값 교체
arr.swap(pivot,right)
}
}
//분할 정복
//왼쪽 배열
sortByFirst(arr, start, right - 1)
//오른쪽 배열
sortByFirst(arr, right + 1, end)
}여기서 변수들의 의미들이 좀 햇 갈릴 수 있다. 하나 하나 씩 살펴보자.
- 함수의 파라미터로 넘겨주는 값은 배열, start, end 이다. start는 분할된 배열이 시작하는 index 값이고 end 는 배열이 끝나는 index 값이다.
- 재귀 함수의 탈출 조건은 start와 end 값이 같아질 때, 즉 데이터 값이 1개일 때 재귀 함수를 종료한다.
- pivot 값은 배열의 첫 번째 값을 기준으로 했기 때문에 arr[start] 이다.
- left, right 은 수색 섬멸 작전에서 정찰병 역할을 할 변수들이다. left 변수에는 pivot(기준) 값 보다 큰 값의 index를, right 변수에는 pivot 보다 작은 값의 index를 담는다.
변수들의 의미를 파악했으니 수색 작전을 코드로 구현해보자.
1. while 문은 왼쪽 정찰병과 오른쪽 정찰병이 만날때 까지 실행하도록 조건을 left < right 으로 설정한다.
2. 왼쪽 정찰병은 기준 값보다 큰 값을, 오른쪽 정찰병은 기준 값보다 작은 값을 찾을 수 있도록 while 문을 이용해 구현했다. 여기서 조건을 설정할 때 조심할 부분이 있다.
한참 헤맨구간
우선, 왼쪽 정찰의 조건에서 주의할 점은 left 값이 배열의 끝 index까지 탐색하게 left <= end로 설정한다. 이 때 left의 값은 배열의 끝 index 보다 1 큰 값을 가질 수 있다. 즉 left의 값은 조건에 따라 end + 1 를 가질 수 있기 때문에 최댓값은 end + 1이다. 이 때문에 left <= end && arr[left] < arr[pivot] 순서가 중요하다. 만약 arr[left] <= arr[pivot] && left <=end 로 순서를 바꾸면 index 값을 벗어나기 때문에 error 가 발생한다. 그리고 left <= end 대신 left < end로 바꿔도 상관없다. 배열의 마지막 값은 검사를 못하지만 연산을 하는데는 문제가 없다. (방법 1은 right left 값이 같을 수 없고, 방법 2는 end 에서 right과 left 값이 같을 수 있다.) -> 중복된 값이 있는 배열에서 마지막 값 정렬 못하는 현상 발생
arr[left] <= arr[pivot] 에 = 붙여야하는 이유는 pivot값과 중복된 값을 처리해야하기 때문이다. 혹은 =를 붙이지 않고 arr.swap 밑에 left++ right -- 를 붙이면 된다.
오른쪽 정찰병은 pivot값 까지 탐색할 수 있게 pivot <= right 로 조건을 설정한다. 그럼 만약 right이 pivot 값과 같아지면 right이 pivot의 index보다 작아질 수 있지 않을까 걱정할 수 있지만 pivot = right 이면 값도 같기 때문에 right의 최솟값은 pivot의 index 이다.
그런 다음 만약에 아직 정찰병은 안 만나기전에 값을 찾았다면 두 값을 swap 그 외 상황(만나거나 지나치는 상황)에서는 pivot 값과 right 값을 swap 한다. 왜 right 값을 swap 해야하는가? left 값은 상황에 따라 right이랑 만나거나 지나친다. 그렇기 때문에 이를 또 조건으로 구현하면 코드가 길어지고 조건을 추가로 비교하는 비용이 든다. 그렇기 때문에 right을 기준으로 swap을 한다. (이거를 이해하느라 한참을 헤맸다..)
기준 값까지 swap 했으므로 배열 분할까지는 완성했다.
그럼 이제 재귀를 이용해 분할 과정을 처리해보자.
우리는 재귀 함수의 파라미터로 배열, 배열의 시작값(start), 배열의 끝나는 값(end)만 주면 수색 점멸 작전을 통해 정렬을 해준다. 그렇다면 배열의 시작값과 배열의 끝나는 값만 제대로 주면 퀵 정렬의 구현은 끝이다.
배열의 시작값과 배열의 끝나는 값은 왼쪽 배열(작은 값이 모여있는 배열) 과 오른쪽 배열(큰 값이 모여있는 배열)에 따라 달라진다. 왼쪽 배열은 배열의 시작값으로 start를 배열이 끝나는 값은 pivot의 index(right) - 1 이다. 오른쪽 배열은 배열의 시작 값으로 pivot의 index(right) + 1이다. 배열의 끝 값은 end 그대로 주면 된다.
2. pivot 값이 중앙일 때
// pivot 값이 중앙
fun sortByMid(array: Array<Int>, left: Int = 0, right: Int = array.size - 1) {
val index = partition(array, left, right)
if (left < index - 1) {
sortByMid(array, left, index - 1)
}
if (index < right) {
sortByMid(array, index, right)
}
}
private fun partition(array: Array<Int>, start: Int, end: Int): Int {
var left = start
var right = end
val pivot = array[(left + right) / 2]
while (left <= right) {
while (array[left] < pivot) {
left++
}
while (array[right] > pivot) {
right--
}
if (left <= right) {
array.swap(left,right)
//다음 요소 탐색
left++
right--
}
}
return left
}배열을 정렬을 하는 작전은 동일하지만 pivot 값의 위치에 따라 코드가 달라진다. 분할 정렬하는 부분과 재귀 호출하는 부분을 나누기 위해 수색 섬멸 작전을 partition 함수로 구현했다. 중앙 값으로 기준 요소를 지정하면 pivot값을 구하기 쉽다(pivot이 들어갈 위치를 안 찾아도 됨)는 장점이 있다.
퀵 정렬 성능
퀵 정렬의 성능 측정을 위해 두 가지의 array를 주었다. 첫 번째로는 random array와 두 번째로는 reversed array이다.
random array 실행 결과
결과 분석
퀵 정렬은 데이터 크기가 클 수록 그 효율성을 확인할 수 있었다. 데이터가 작은 array 를 처리하는 것은 오히려 삽입 정렬이 더 빠른 경우도 존재했다. 시간 뿐만 아니라 공간 복잡도까지도 고려한다면 데이터가 작을 때는 퀵 정렬말고 삽입 정렬을 써야겠다.
흥미로운 점은 같은 퀵 정렬이라도 pivot 값의 기준에 따라 성능 차이가 발생했다. 대부분에 테스트에서 중앙 퀵정렬이 첫 번째 퀵정렬 보다 빠른 결과를 보여주었다.
reversed array 실행 결과
결과 분석
reversed array 에서 결과를 보면 흥미로운 결과가 나왔다.
대략 데이터 개수가 7000 에서 8000 사이에서 첫 번째를 기준으로 한 퀵 정렬에서 stackoverflow 가 발생했다. 이는 reversed array 가 첫 번째 퀵 정렬의 최악의 상황이기 때문이다.
이처럼 데이터가 어떠한 경향을 보이고 있을 때 퀵 정렬의 기준 요소에 따라 성능 편차가 심해진다.
cf> 기준 요소의 선택
많은 소프트웨어 엔지니어와 과학들은 알고리즘이 더 빠른 성능을 갖도록 개선하기 위해 노력한다. 데이터 집합 내에서 '좋은' 기준 요소를 선택하는 방법도 개선하는 노력 중 한 가지이다. 좋은 기준 요소만 선택할 수 있다면 퀵 정렬은 최선의 성능을 낼 수 있다.
그렇다면 퀵 정렬에서의 '좋은 기준'은 무엇일까?
첫 번째로 생각해볼 만한 방법은 기준 요소의 선택 방법 중 쓸만한 것 한 가지는 데이터 집합에서 무작위로 기준 요소를 선택하는 방식이다. 하지만 이렇게 하면 최소값이나 최대값이 선택되는 확률을 크게 줄일 수 있다. but, 난수를 뽑는 과정도 비용이 들어 성능 저하가 생긴다.
이보다 좋은 방법으로는 우리가 구현한 데이터 집합의 중간 값을 기준요소로 지정하는 것이다. 이렇게 하면 처음 세 개 중의 중간 값을 찾기 위한 아주 작은 성능 비용이 들지만, 최악의 경우를 피할 수 있다!
퀵 정렬 오류 잡느라 힘들었다.. 삽질 x 100..
