고정 헤더 영역
상세 컨텐츠
본문
안녕하세요. 알고리즘을 공부하던 중, 퀵 정렬(Quick sort) 이 한 번에 이해가 가지 않아서, 원리를 파헤치는 글을 올리게 되었습니다!!
퀵 정렬 방식은 간단합니다.
1) pivot(기준)을 정한다.
2) pivot의 제자리를 찾아준다.
이를 반복하는 것이 퀵 정렬입니다.
퀵 정렬을 하는 방식은 여러 가지가 있지만 저는 제가 배운 호어 분할(Hoare Partition) 방식으로 설명하겠습니다.
예를 들어 1~5 의 숫자가 적힌 카드가 무작위로 나열되어있다고 해봅시다. 이를 오름차순으로 정렬하는 것이 우리의 목표입니다.
| ? | ? | ? | ? | ? |
먼저 가장 첫 번째 카드의 원소를 pivot으로 정합니다.
| Pivot | ? | ? | ? | ? |
그럼 뒤에 나열된 4장은 각각 Pivot의 카드에 적힌 수보다 작거나, 큰 수들일 것입니다.
5장의 카드 나열을 Pivot 기준으로 생각해본다면 다음과 같은 경우의 수들이 있을 것입니다.
1) Pivot + Pivot 보다 큰 카드 4장
| Pivot | ⬆️ | ⬆️ | ⬆️ | ⬆️ |
2) Pivot + Pivot 보다 큰 카드 3장 + Pivot 보다 작은 카드 1장
| Pivot | ⬆️ | ⬆️ | ⬆️ | ⬇️ |
3) Pivot + Pivot 보다 큰 카드 2장 + Pivot 보다 작은 카드 2장
| Pivot | ⬆️ | ⬆️ | ⬇️ | ⬇️ |
4) Pivot + Pivot 보다 큰 카드 1장 + Pivot 보다 작은 카드 3장
| Pivot | ⬆️ | ⬇️ | ⬇️ | ⬇️ |
5) Pivot + Pivot 보다 작은 카드 4장
| Pivot | ⬇️ | ⬇️ | ⬇️ | ⬇️ |
이 때, 왼쪽부터 원소들을 검사하는 Left Filter 와, 오른쪽부터 원소들을 검사하는 Right Filter를 돌립니다.
Left Filter 는 왼쪽부터 돌면서 Pivot에 쓰인 값보다 작다면 넘어가고, 크다면 저장합니다.
Right Filter 는 오른쪽부터 돌면서 Pivot에 쓰인 값보다 크다면 넘어가고, 작다면 저장합니다.
카드가 다음과 같이 나열되어있을 때를 예시로 설명해보겠습니다.
3) Pivot + Pivot 보다 큰 카드 2장 + Pivot 보다 작은 카드 2장
| Pivot | ⬆️ | ⬆️ | ⬇️ | ⬇️ |
Left Filter와 Right Filter를 돌립니다.
| Pivot | ⬆️ (Left) |
⬆️ | ⬇️ | ⬇️ (Right) |
2번째 카드가 Pivot 보다 크므로, Left Filter 에는 2번째 카드가 저장되었고,
5번째 카드가 Pivot보다 작으므로 Right Filter에는 5번째 카드가 저장되었습니다.
두 필터에 값이 모두 저장되었다면, 그 두 카드의 위치를 바꿉니다.
| Pivot | ⬇️ | ⬆️ | ⬇️ | ⬆️ |
그리고 다음 카드부터 각각 또 필터를 돌립니다.
| Pivot | ⬇️ | ⬆️ (Left) |
⬇️ (Right) |
⬆️ |
3번째 카드가 Pivot 보다 크므로, Left Filter 에는 3번째 카드가 저장되었고,
4번째 카드가 Pivot보다 작으므로 Right Filter에는 4번째 카드가 저장되었습니다.
두 필터에 값이 모두 저장되었다면, 그 두 카드의 위치를 바꿉니다.
| Pivot | ⬇️ | ⬇️ | ⬆️ | ⬆️ |
그리고 다음 카드부터 각각 또 필터를 돌립니다.
| Pivot | ⬇️ | ⬇️ (Right) |
⬆️ (Left) |
⬆️ |
이 때, Left Filter와 Right Filter의 인덱스가 교차되었습니다.
이 때, Left FIlter 가 지나온 자리들은 Pivot보다 작은 수 이거나, 큰 수였다면 Right Filter의 Pivot 보다 작은 수로 교체된 수 입니다.
결국, Left FIlter 가 지나온 자리들은 Pivot보다 작은 수들로 이루어져있습니다.
Right Filter도 마찬가지입니다.
Right FIlter 가 지나온 자리들은 Pivot보다 큰 수 이거나, 작은 수였다면 Right Filter의 Pivot 보다 작은 수로 교체된 수 입니다.
결국, Left FIlter 가 지나온 자리들은 Pivot보다 큰 수들로 이루어져있습니다.
그렇기에 Right Filter 자리의 카드와 Pivot 자리의 카드를 바꾸면, 그 자리가 바로 Pivot 카드의 자리가 됩니다.
| ⬇️ | ⬇️ | Pivot | ⬆️ | ⬆️ |
Pivot의 제 자리를 찾아줬습니다.
이제 Pivot의 왼쪽 카드들과 오른쪽 카드들도 지금 했던 방식인
1) Pivot을 정하고
2) 그 자리를 찾아준다.
을 반복하면 퀵 정렬로 카드들을 오름차순으로 정렬하게 됩니다.
