2024. 2. 13. 09:23ㆍ카테고리 없음
퀵 정렬
퀵 정렬은 분할과 재귀로 이뤄진다.
분할
분할은 임의의 피벗값(주로 제일 마지막 인덱스)을 정하여 피벗값을 기준으로 작은값들은 왼쪽, 큰값들은 오른쪽에 위치하도록 배열을 구분하는 작업이다. 피벗값을 기준으로 큰지 작은지만 구분이 되면 충분하며, 구분된 한 쪽이 온전히 정렬되어 있지 않아도 좋다.
재귀
분할이 1회 완료되면 피벗값을 기준으로 왼쪽배열, 오른쪽 배열로 구분된다. 그러면 이때 재귀로직이 들어간다. 왼쪽과 오른쪽 배열에 대해서 각각 분할과정을 실행하는 것이다. 그리고 배열이 완전히 정렬 될 때까지 재귀적으로 반복해서 실행한다. 최하위까지 완료되면 배열은 온전히 정렬되어있다.
퀵 정렬의 효율성
퀵 정렬 단계 수N x LogN
| 8 | 8 |
| 24 | 24 |
| 64 | 64 |
| 160 | 160 |
위 표를 보면 알 수 있듯이 퀵정렬의 빅오는 O(NlogN)이다. 다른 빅오와 효율성 차이를 보면 아래와 같다.
퀵 정렬을 삽입 정렬과 비교해보면
최악의 경우는 같지만 평균과 최선일 경우효율성이 매우 빠르다.
대부분의 프로그래밍 언어의 내장 메서드로서 정렬은 퀵 정렬으로 구현되어 있다고 합니다.
이야기로 풀어보는 퀵정렬
상상해보세요, 당신은 엄청 많은 숫자 카드를 가지고 있어요. 이 카드들을 순서대로 정리해야 하는데, 어떻게 할까요? 여기서 퀵정렬 방법을 사용해보려고 해요.
- 카드 고르기: 먼저, 이 많은 카드 중에서 하나를 골라요. 이 카드를 '기준 카드'라고 해볼게요.
- 팀 나누기: 모든 카드를 보고, '기준 카드'보다 숫자가 작은 카드는 왼쪽에, 큰 카드는 오른쪽에 둬요. 이제 카드가 두 팀으로 나뉘었죠?
- 각 팀 정리하기: 이제 왼쪽 팀과 오른쪽 팀을 각각 다시 정리해야 해요. 그래서 또 '기준 카드'를 고르고, 똑같이 왼쪽과 오른쪽으로 나눠요.
- 반복: 각 팀 안에서도 계속 같은 방법으로 정리해요. 팀 안의 카드가 하나만 남을 때까지 이 과정을 반복해요.
왜 인가?
이제, 왜 이 방법이 의 시간이 걸린다고 하는지 설명해볼게요.
- : 이건 당신이 가진 카드의 총 수를 뜻해요. 모든 카드를 한 번씩은 봐야 하니까, 카드의 수만큼 일을 해야 해요.
- : 여기서 재미있는 부분이에요. 매번 카드를 나눌 때마다, 카드의 수가 반으로 줄어들어요. 예를 들어, 100장의 카드가 있다면, 첫 나누기에는 50장씩 두 팀이 되고, 다음에는 25장씩, 그 다음에는 12장씩... 이렇게 계속 반으로 줄어들죠. 이 '반으로 줄어드는' 과정을 몇 번이나 해야 모든 팀이 한 장의 카드만 남는지 생각해보면, 그 횟수가 바로 이에요.
즉, 카드를 한 번씩 다 보는 일()과 카드를 반으로 계속 나누는 일()을 합치면, 전체 작업 시간이 이 되는 거예요.
파이썬 예제코드
# 퀵정렬 함수
def quick_sort(arr):
if len(arr) <= 1:
return arr
# 피벗은 배열의 첫 값으로 지정
pivot = arr[0]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 예시 배열
unsorted_array = [3, 6, 8, 10, 1, 2, 1]
1 회 분할 후
[3, 6, 8, 10, 1, 2, 1]
Pivot: 3
Left: [1, 2, 1]
Middle: [3]
Right: [6, 8, 10]
[1, 2, 1] [3] [6, 8, 10]
Left 의 경우 (2회 분할 후)
[1, 2, 1]
Pivot: 1
Left: []
Middle: [1, 1]
Right: [2]
[1, 1], [2]
Right 의 경우 (2회 분할 후)
[6, 8, 10]
Pivot: 6
Left: []
Middle: [6]
Right: [8, 10]
[6] , [8, 10]
분할 정복 후 결과 병합
Left: [1, 1, 2] + Middle: [3] + Right: [6, 8, 10] --> [1, 1, 2, 3, 6, 8, 10]
Sorted_Array = [1, 1, 2, 3, 6, 8, 10]