아~ (무슨 말이지?)
알고리즘... 예상은 했지만 예상밖으로 난해하네?
오늘부터 알고리즘 파트를 공부하기 시작했다.
역시나 초반부터 이해하기 힘든 녀석을 맞이했다.
그래서 적기 시작하는 TIL
Quick Sort(퀵 정렬) 알고리즘
코드에 앞서 퀵 정렬 알고리즘에 대해 알아보자.
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
출처 : 위키백과
음... 오늘 배운 코드를 보도록 하자
void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
핵심은 Partition 메서드이다.
int[] arr = [ 5, 3, 6, 1, 2, 4 ] 기준으로 설명해보자.
QuickSort 메서드의 매개변수로 (arr, 0, arr.Length - 1) 을 전달하자.
left == 0, right == 5 이므로 if 문의 첫 줄인 Partition 함수가 실행된다.
이 때, for문을 루프하면 다음과 같이 진행된다.
현재 배열에서 Partition 메서드의 pivot == 4이다.
for 문을 루프 해 배열의 각 값[ j = 0 ~ 5 (j < arr.Length - 1) ] 을 pivot 과 비교한다.
pivot 보다 작으면?
1. i++;
2. arr[i] 와 arr[j] 교체
3. j++;
pivot 보다 크면?
1. j++;
위 조건을 따르면 pivot 보다 큰 값들이 점점 오른쪽으로 옮겨진다.
for문이 끝나고 마지막으로 i + 1 값과 pivot을 교체 하게되면
pivot의 위치를 기준으로 오른쪽은 pivot 보다 큰 값이, 왼쪽은 작은값이 위치한다.
중요한 것은 이 한 번의 Partition으로 정렬이 되는것이 아니라
pivot이 중간값이 되고 그 위치의 Index를 반환한다는 것이다.
만약 배열이 [1, 2, 3, 4, 5, 6] 이었다면?
for문 루프에서 모든 조건이 true가 되어 자기 자신의 값을 교체 하며 for문 밖의 Swap 에도 변화가 없다.
만약 배열이 [6, 5, 4, 3, 2, 1] 이었다면?
for문 루프에서 모든 조건이 false 가 되어 i = -1을 유지하고 Swap은 일어나지 않는다.
for문을 빠져나와 Swap 시 arr[0] 과 arr[5]가 교체되어 [1, 5, 4, 3, 2, 6] 이 된다.
하나도 정렬이 안 된것 같지만 pivot을 제외한 모든 값이 1 보단 크다.
그러므로 "pivot 기준 오른쪽은 pivot 보다 큰 값" 에 부합한다.
이렇게 첫 Partition으로 pivot을 중간값에 위치했고 어느정도 정렬도 되었다.
그 후 Partition 으로 반환된 pivot Index를 기준으로 좌, 우 부분에 대한 QuickSort를 재귀적 호출한다.
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
위에서 보듯 모든값에 대한 조건이 true이든 false이든 반드시 끝나게 되고 정렬이 이루어지게 된다.
이를 반복하면 결국 각각의 부분들의 정렬이 완료되고 최종적으로 완전 정렬된 배열이 나오게 된다.
[다만 중복된 값이 있을 경우엔 이들에 대한 순서는 달라질 수 있어 불안정 정렬이라 부른다.]
이를 그림으로 표현하면 이런 느낌일 것이다.
'스파르타 내배캠' 카테고리의 다른 글
스파르타 내배캠 Unity 3기 10일차 (0) | 2024.01.05 |
---|---|
스파르타 내배캠 Unity 3기 9일차 (1) | 2024.01.04 |
스파르타 내배캠 Unity 3기 7일차 (1) | 2024.01.02 |
스파르타 내배캠 Unity 3기 6일차 (1) | 2023.12.29 |
스파르타 내배캠 Unity 3기 5일차 (0) | 2023.12.28 |