퀵 정렬
퀵 정렬은 분할 정복 (Divide and Conquer) 에 기반한 알고리즘이다.
분할 정복 전략은 적군 전체를 공략하는 대신, 전체를 구성하는 구성요소 들을 나누어 잘개 쪼개진 적을 공략하는 전법이다.
알고리즘
1.
데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다.
2.
기준 요소 왼편에는 기준 요소 보다 작은 요소들이 모여 있고, 오른편에는 큰 요소들이 모여 있으므로 이렇게 나눈 데이터 집합을 대상으로 다시 1번 작업을 수행한다.
3.
1번과 2번의 과정을 더 이상 데이터 집합을 나눌 수 없을 때 까지 반복하면 정렬된 데이터 집합을 얻게 된다.
1. 재귀 호출
void QuickSort(int DataSet[], int Left, int Right)
{
if (Left < Right)
{
int Index = Partition(DataSet, Left, Right);
QuickSort(DataSet, Left, Index - 1);
QuickSort(DataSet, Index + 1, Right);
}
}
C
2. Partition 함수
void Swap(int* A, int* B)
{
int Temp = *A;
*A = *B;
*B = Temp;
}
int Partition(int DataSet[], int Left, int Right)
{
int First = Left;
int Pivot = DataSet[First];
++Left;
while(Left <= Right)
{
while(DataSet[Left] <= Pivot && Left < Right)
++Left;
while(DataSet[Right] > Pivot && Left <= Right)
--Right;
if(Left < Right)
Swap(&DataSet[Left], &DataSet[Right]);
else
break;
}
Swap(&DataSet[First], &DataSet[Right]);
return Right;
}
C
파이썬 코드
def quick_sort(array: List):
if len(array) <= 1:
return array
pivot = array[len(array) // 2]
lesser, equal, greater = [], [], []
for num in array:
if num < pivot:
lesser.append(num)
elif num > pivot:
greater.append(num)
else:
equal.append(num)
return quick_sort(lesser) + equal + quick_sort(greater)
Python
•
매번 재귀 호출될 때마다 새로운 리스트 3개를 생성하고 리턴해야 하므로 메모리 사용 측면에서 비효율적이다.
•
따라서 추가 메모리 사용이 적은 in-place 정렬을 사용해야 한다.
•
대소 비교를 위해 pivot 값을 사용하지만, 분할의 기준점이 pivot 값이 아닐 수도 있다. 이유는 pivot 값을 기준으로 대소 비교를 했을 때 좌측과 우측에 여유 공간이 딱 맞는 경우는 드물기 때문이다.
최적화 코드
def quick_sort(nums: List[int]):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = nums[(low + high) // 2]
while low <= high:
while nums[low] < pivot:
low += 1
while nums[high] > pivot:
high -= 1
if low <= high:
nums[low], nums[high] = nums[high], nums[low]
low, high = low + 1, high - 1
return low
return sort(0, len(nums) - 1)
Python
•
quick_sort 는 sort 와 partition 으로 나뉜다.
•
sort는 재귀 함수이고 정렬 범위를 시작 인덱스와 끝 인덱스로 인자를 받는다
•
partition 함수는 정렬 범위를 인자로 받고 다음 로직을 따라서 좌우측의 값들을 정렬하고 분할 기준점의 인덱스를 리턴한다.
◦
이때 분할 기준점(mid)는 sort 를 재귀적으로 호출할 때 우측 리스트의 시작 인덱스로 사용한다.
