안녕하세요. 이번 시간에는 퀵 정렬에 대해 알아보겠습니다.
이름처럼 빠릅니다. 정확히는 재수가 없지 않으면 빠릅니다. 재수가 없으면 매우 느립니다. 하지만 재수없는 경우가 희박하기 때문에 많이 사용됩니다. 빠르기로 유명한 합병 정렬보다 평균 두 배 빠릅니다. 관심이 생기죠? 대신 합병 정렬보다 코드가 어려우니 차분히 보셔야할 겁니다.
단점도 있는데 운이 나쁘면 느리다는 것(극복하는 방법이 있습니다)입니다. 또 다른 단점으로 같은 숫자들을 정렬할 경우 순서가 섞일 수 있다는 겁니다. 예를 들면 100이 3개가 있고 각각 1번, 2번, 3번 번호가 매겨져 있을 때 퀵 정렬 방법으로 정렬하면 1,2,3번 순서가 아닌 다른 순서로 정렬될 수도 이있습니다. 같은 100인데 그 순서가 뭐가 중요하냐고 할 수도 있지만, 실제 데이터에서 100이 금액이고, 1번 2번 3번이 사람의 순서라면 금액 순으로 정렬을 했을 때 사람의 순서가 달라지는 불상사가 생기는 겁니다. 이 점들을 고려하여 퀵 정렬을 사용하셔야 합니다.
합병 정렬처럼 분할 정복 기법을 사용합니다. 그 상태로 문제를 해결하지 못할 때 작게 쪼개어 해결하는 거죠.
[4,1,7,6,5,8,2,3] 어떠한 한 숫자를 고릅니다. 기준으로 5를 골랐습니다. 5를 가장 오른쪽으로 보냅니다.
[4,1,7,6,3,8,2,5] 이제 왼쪽에는 기준보다 작은 수가, 오른쪽에는 기준보다 큰 수가 나오도록 조정하여 보겠습니다.
[4,1,7,6,3,8,2,5] 5를 제외한 가장 왼쪽과 오른쪽 수를 조작합니다. 이제부터 규칙은 다음과 같습니다. 집중해서 읽어주세요. 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다. 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히 있습니다. 이렇게 넘어가다가 왼쪽은 기준보다 크고, 오른쪽은 기준보다 작으면 서로 바꿔줍니다.
[4,1,7,6,3,8,2,5] 왼쪽 4는 기준보다 작기 때문에 다음 수로 넘어가고, 오른쪽 2은 기준보다 작기 때문에 가만히 있습니다.
[4,1,7,6,3,8,2,5] 왼쪽 1도 다음 수로 넘어가고, 오른쪽 2는 계속 가만히 있습니다.
[4,1,7,6,3,8,2,5] 왼쪽 7는 기준보다 크고, 오른쪽 2은 기준보다 작기 때문에 서로 바꿔줍니다.
[4,1,2,6,3,8,7,5] 왼쪽 6은 기준보다 크기 때문에 가만히 있고, 오른쪽 8은 기준보다 크기 때문에 다음 수로 넘어갑니다.
[4,1,2,6,3,8,7,5] 왼쪽 6은 기준보다 크고, 오른쪽 3은 기준보다 작기 때문에 서로 바꿔줍니다.
[4,1,2,3,6,8,7,5] 이제 더 이상 비교할 수가 없네요. 왼쪽과 오른쪽 수가 만났습니다.
[4,1,2,3,6,8,7,5] 그러면 만난 수인 6과 기준인 5를 바꿔줍니다.
[4,1,2,3,5,8,7,6] 이제 5를 기준으로 왼쪽에는 5보다 작은 수가, 오른쪽에는 5보다 큰 수들만 남았습니다. 신기하죠?
아직 정렬이 완료되지 않았기 때문에 끝이 아닙니다. 이제 5를 기준으로 왼쪽([4,1,2,3]), 오른쪽 배열([8,7,6])로 나누어 재귀적으로 퀵 정렬을 해줍니다. 이렇게 계속 하면 정렬이 완료됩니다.
코드로 볼까요? 코드를 간단하게 하기 위해 정렬하는 부분과 재귀하는 부분을 나누어주었습니다.
var partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
var temp;
var pivot = array[pivotIndex];
while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어갑니다.
while (array[left] < pivot)
left++;
while (array[right] > pivot)
right--;
if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
temp = array[left];
array[left] = array[right];
array[right] = temp; // 서로 바꿔줍니다.
left++;
right--;
}
}
temp = array[left];
array[left] = array[pivotIndex];
array[pivotIndex] = temp; // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 i입니다.
return left;
};
var quickSort = function(array, left, right) { // 재귀하는 부분
if (!left) left = 0;
if (!right) right = array.length - 1;
var pivotIndex = right; // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.
pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.
if (left < pivotIndex - 1)
quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
if (pivotIndex + 1 < right)
quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
return array;
};
quickSort([4,1,7,6,3,8,2,5]); // [1,2,3,4,5,6,7,8]성능은 최악의 경우 O(N^2)이고 최악의 경우를 제외하면 O(NlogN) 정도 됩니다. O(N^2)이 나오는 경우는 매우 희박하기 때문에 보통 O(NlogN)으로 취급합니다. 같은 NlogN이지만 합병 정렬보다는 두 배 빠르기 때문에 더 자주 쓰입니다.
최악의 경우는 기준(pivot)으로 뽑은 수가 항상 제일 큰 수이거나 제일 작은 수일 경우입니다. 이럴 경우는 나중에 두 배열로 나누더라도 한 배열은 비어있고, 한 배열은 꽉 차있습니다. 하지만 이렇게 운이 나쁜 경우는 거의 없겠죠?
퀵 정렬은 (물론 조금 변형되었지만) 대부분의 프로그래밍 언어에서 배열.sort()할 때 내부적으로 사용됩니다. 물론 합병 정렬도 간혹가다 사용되지만요. 다음 시간에는 계수 정렬에 대해 알아보겠습니다!
익명
ZeroCho
