퀵 정렬
퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예시 중 하나로, 정렬을 수행하는 알고리즘 중 가장 빠른 속도를 가지는 알고리즘 중 하나 입니다.
퀵 정렬 나무위키
퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬합니다.
1.
리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3.
분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
퀵 정렬 장단점
장점
•
대부분의 데이터셋에서 빠른 속도로 정렬을 수행합니다.
•
메모리 사용량이 적습니다.
•
정렬을 수행하는 동안 입력 데이터를 거의 변경하지 않습니다.
단점
•
최악의 경우, 즉 이미 정렬되어 있는 데이터나 역순으로 정렬된 데이터와 같은 특정한 경우에는 성능이 떨어집니다.
•
피벗을 잘못 선택하는 경우 성능이 급격히 저하됩니다.
•
구현이 다른 정렬 알고리즘보다 복잡합니다.
퀵 정렬의 정확한 구현,
퀵 정렬의 정확한 구현을 아래 그림과 같이 설명하겠습니다.
1.
초기 상태 5,3,8,4,9,1,6,2,7 에서 가장 처음을 피봇으로 잡습니다.
2.
다음 인덱스부터 시작해서 5보다 큰 숫자를 선택합니다. (8)
3.
마지막 인덱스부터 시작해서 5보다 작은 숫자를 선택합니다. (2)
두 위치를 바꿉니다.
1.
두 번째 상태 5,3,2,4,9,1,6,8,7
2.
다음 바꾼 인덱스 다음부터 시작해서 5보다 큰 인덱스를 선택합니다. (9)
3.
다음 바꾼 인덱스 다음부터 시작해서 5보다 작은 인덱스를 선택합니다. (1)
두 위치를 바꿉니다.
1.
세 번째 상태 5,3,2,4,1,9,6,8,7
2.
다음 바꾼 인덱스 다음부터 시작해서 5보다 큰 인덱스를 선택합니다. (6)
3.
다음 바꾼 인덱스 다음부터 시작해서 5보다 작은 인덱스를 선택합니다. (1)
위 두 인덱스가 교차되므로, 작은 숫자와 5를 바꿉니다. (1)과 바꾼다는 뜻.
마지막 상태, 1,3,2,4,5,9,6,8,7 그럼 5를 기준으로 왼쪽에는 5보다 작은 숫자들이 오른쪽에는 5보다 큰 숫자들이 나열됩니다.
위 과정을 왼쪽과 오른쪽에도 똑같이 적용합니다. (재귀)
위 과정을 정렬이 완료될 때까지 반복합니다.
퀵 정렬 코드 구현
다음은 C# 코드입니다.
void QuickSort(int[] array, int start, int end)
{
if (start >= end) return;
var pivot = start;
var left = start + 1;
var right = end;
while (left <= right)
{
while (left <= end && array[left] <= array[pivot]) left++;
while (right > start && array[right] >= array[pivot]) right--;
if (left > right)
{
(array[pivot], array[right]) = (array[right], array[pivot]);
}
else
{
(array[left], array[right]) = (array[right], array[left]);
}
}
QuickSort(array, start, right - 1);
QuickSort(array, right + 1, end);
}
var arr = new int[] { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
QuickSort(arr, 0, arr.Length - 1);
sw.WriteLine(string.Join(' ', arr));
C#
복사
1.
QuickSort 알고리즘에 사용될 배열과 시작, 끝 인덱스를 입력 받습니다.
2.
만약 start≥end이면, (배열의 원소가 하나라면) 반환합니다.
3.
pivot을 시작점으로 정합니다.
4.
left를 시작 다음 점으로, 즉 start+1로 정합니다.
5.
right를 끝점으로 정합니다.
6.
left 인덱스를 pivot보다 큰 숫자를 찾을 때까지 증가시킵니다.
7.
right 인덱스를 pivot보다 작은 숫자를 찾을 때까지 증가시킵니다.
8.
만약 left와 right가 교차하면, pivot과 right를 교환합니다.
9.
교차하지 않았다면, left와 right 인덱스의 숫자를 교환합니다.
10.
left와 right가 교차할 때까지 위의 과정을 반복합니다.
그리고 pivot을 기준으로 (right) 왼쪽과 오른쪽 부분 배열을 각각 정렬합니다.
