Quick Sort(퀵 정렬)
1. Quick Sort(퀵 정렬) 문제
예제를 통해서 퀵 정렬을 한 번 알아보자
다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하라.
3 7 8 1 5 9 6 10 2 4
2. Quick Sort(퀵 정렬) 풀이
특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.
퀵 정렬에서는 기준 값이 있고 이 기준 값을 피벗(Pivot) 이라고한다.
일반적으로 피벗값*은 가장 앞의 값을 선택한다.
3* 7 8 1 5 9 6 10 2 4
이를 기준으로 왼쪽에서부터 피벗값 3* 보다 큰값을 찾는다.
7은 3보다 크다, 찾으면 오른쪽부터 3* 보다 작은 값을 찾는다.
2가 3보다 작다.
그 둘의 자리를 바꿔준다.
3* 2 8 1 5 9 6 10 7 4
다시, 왼쪽부터 3* 보다 큰값을 찾고 찾으면 오른쪽부터 작은값을 찾는다.
8은 3보다 크고 1은 3보다 작으므로 자리를 변경해준다.
3* 2 1 8 5 9 6 10 7 4
위의 상황에서 왼쪽에서 큰값, 오른쪽에서 작은 값을 찾는데
8과 1일 조건에 해당한다.
하지만 이전과는 다르게 8과 1이 서로 지나쳐서 선택이 되는데 이를 엇갈린다 라고 표현한다.
이때 피벗값 3* 과 엇갈린 1의 자리를 변경해준다.
이렇게 되면 피벗값 3*은 정렬이 종료된다.
1 2 3* 8 5 9 6 10 7 4
이 상태를 보면 피벗값 3보다 왼쪽의 숫자들은 3보다 작은 수의 집합, 오른쪽은 큰 값들의 집합이다.
왼쪽의 배열과 오른쪽의 배열에서 각각 피벗값을 선택한뒤 이전의 과정을 해준다.
1* 2 (3) 8* 5 9 6 10 7 4
왼쪽의 피벗값 1*은 왼쪽부터 찾고 오른쪽부터 찾았을 때 값이 변화가 없으므로 종료한다.
(1) (2) (3) 8* 5 9 6 10 7 4
8은 왼쪽부터 큰 값을 찾고 9, 오른쪽에서 작은값 4의 자리를 변경한다.
(1) (2) (3) 8* 5 4 6 10 7 9
다시 왼쪽부터 큰 값 10, 오른쪽에서 작은값 7 자리를 변경한다.
(1) (2) (3) 8* 5 4 6 7 10 9
다시 왼쪽부터 큰값 10, 오른쪽에서 작은값 7 인데 엇갈리므로
8과 7의 자리를 변경한다.
(1) (2) (3) 7* 5 4 6 (8) 10* 9
새로 피벗값 7과 10이 선택되었다.
이런식으로 전개해나가면
최종적으로
1 2 3 4 5 6 7 8 9 10으로 정렬이 완료된다.
// 다음의 배열을 오름차순으로 정렬하시오
const quickArr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
function quickSort(arr, start, end) {
if (start >= end) {
// 원소가 1개인 경우
return;
}
let pivotIndex = start; // 피벗은 첫번째원소
let i = start + 1; // 왼쪽 출발
let j = end; // 오른쪽 출발
let temp; // 잠시 저장할 변수
// 왼쪽에서 출발한 i가 오른쪽에서 출발한 j보다 큰 경우 엇갈린 것이다
while (i <= j) {
// 엇갈릴때 까지 반복한다
// 왼쪽 출발 i와 피벗값을 비교하여
// i번째 요소가 피벗값보다 작으면 다음 요소를 비교하기 위해 i를 증가시킨다
while (arr[i] < arr[pivotIndex]) {
i++;
}
// 오른쪽 출발 j와 피벗값을 비교하여
// j번째 요소가 피벗값보다 크면 j를 감소시킨다
// 이 때, 오른쪽부터 시작하는 j는 start 인덱스보다 커야한다
while (arr[j] >= arr[pivotIndex] && j > start) {
j--;
}
// 위의 두 과정을 진행한 뒤
// i번째 요소와 j번째 요소의 자리를 바꿔준다
if (i > j) {
temp = arr[j];
arr[j] = arr[pivotIndex];
arr[pivotIndex] = temp;
} else {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
// 위의 과정을 하위 배열에서 재귀적으로 호출하여 진행한다.
// 왼쪽 배열에서 진행하고
quickSort(arr, start, j - 1);
// 오른쪽 배열에서 진행한다
quickSort(arr, j + 1, end);
// 위의 두 재귀 함수로 인해 log2로 나타낼 수 있게된다
}
quickSort(quickArr, 0, quickArr.length - 1);
console.log(quickArr);3. Quick Sort(퀵 정렬)의 효율성
퀵 정렬의 경우 한번 정렬을 수행했을 때, 왼쪽 오른쪽 나뉜다.
이로 인해 이전에 알아본 정렬(선택, 삽입, 버블)들과 속도에서 차이가 난다.
예를 들어 선택 정렬의 경우 O(n^2)을 따르는데,
1 2 3 4 5 6 7 8 9 10을 정렬할경우
빅오 표기법에 의해 10^2 = 100의 연산(시간)이 필요하다.
반면 퀵 정렬의 경우 반씩 쪼개서 각각 계산을 하므로,
5^2 + 5^2 = 50
대략적으로 보았을 때, 시간이 절반으로 줄어든다.
배열을 쪼개는(분할) 과정에서 n번의 연산을 하고,
이후에 분할된 배열 안에서 정렬하는데 2개로 분할하기 때문에 밑이 2인 로그의 횟수를 가진다.
따라서 평균적으로 n*log2(n)의 시간 복잡도를 가지게 된다.
그래도 대부분의 경우에는 n*log2(n)을 만족한다.
일반적으로는 큌 정렬 O(n*log(n))의 시간 복잡도를 가진다.
+) 퀵정렬의 한계점
하지만 최악의 경우에는 O(n^2)의 시간 복잡도를 갖는다.
특정한 경우에 있어서 비효율적이다.
ex) 1 2 3 4 5 6 7 8 9 10
위와 같이 이미 정렬되어있는 경우를 직접 정렬해보면 알 수 있다.
반면, 삽입 정렬의 경우 이미 정렬되어 있을때 O(n)의 복잡도를 가지게 된다.
따라서 무조건적으로 퀵정렬이 옳다 생각하지 말고 상황에 따라 적절한 알고리즘을 적용하는 것이 중요하다.
참고자료
동빈나 유튜브
https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz
