- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
- 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
1. 퀵 정렬 동작 예시
[Step 0]
- 현재 Pivot 값은 5이다.
- 왼쪽에서는 Pivot값 보다 큰 데이터를 선택하고 오른쪽에서는 Pivot값 보다 작은 데이터를 선택한다.
- 왼쪽은 5보다 큰 7을, 오른쪽에서는 5보다 작은 4를 선택한다.
- 이제 두 데이터의 위치를 서로 변경한다.
[Step 1]
- 현재 Pivot 값은 5이다.
- 왼쪽에서는 9는 Pivot보다 크므로 선택, 오른쪽에서는 2가 5보다 작으므로 2를 선택
- 9와 2의 데이터 위치를 서로 변경한다.
[Step 2]
- 9와 2의 위치가 바뀌었다.
- 왼쪽에서는 Pivot보다 큰 값을 다시 찾는다. 6을 발견하는데 이때 1은 작으므로 건너뛴다.
- 오른쪽에서는 5보다 작은 값을 찾는다. 1을 발견하는데 이때 6은 크므로 건너뛴다.
- 이때 위치가 엇갈리는 경우 Pivot과 작은 데이터의 위치를 서로 변경한다.
- 즉, Pivot(5)와 작은 데이터(1)의 위치를 변경
[분할 완료]
- Pivot이 거의 중앙으로 옮겨지고 왼쪽은 Pivot보다 작은 값, 오른쪽은 Pivot보다 큰 값이 들어간다.
- 이렇게 Pivot을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) = (Partition)라고 한다.
[왼쪽 데이터 묶음 정렬]
- 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.
- 여기서 Pivot은 1이다.
- 왼쪽은 1보다 큰 수를 선택하고 오른쪽은 1보다 작은 수를 선택한다.
- 이처럼 계속 반복적으로 정렬을 수행한다.
[오른쪽 데이터 묶음 정렬]
- 오른쪽도 마찬가지로 Pivot이 6이되어 왼쪽은 큰 수, 오른쪽은 6보다 작은 수를 선택하여 바꾼다.
2. 퀵 정렬이 빠른 이유
- 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.
3. 퀵 정렬의 시간 복잡도
4. 퀵 정렬 소스코드
def quick_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료
return
pivot = start #피벗은 첫 번째 인덱스
left = start + 1
right = end
while(left <= right):
#피벗보다 큰 데이터를 찾을 때까지 반복
while(left <= end and array[left] <= array[pivot]):
left += 1
#피벗보다 작은 데이터를 찾을 때까지 반복
while(right > start and array[right] >= array[pivot]):
right -= 1
if(left > right):#엇갈렸다면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right -1)
quick_sort(array, right + 1, end)
- 첫 번째 원소를 Pivot으로 설정
- 첫 번째 반복문 (left <= right)일 경우가 엇갈릴 경우다.
- 왼쪽은 1개씩 올라가면서, 오른쪽은 1개씩 내려가면서 확인한다.
- 엇갈릴 경우 if, else문을 통해 위치를 바꿔준다.
- 가운데에 Pivot값이 위치가 되면 다시 재귀함수를 이용해서 왼쪽, 오른쪽 덩어리를 진행한다.
array = [5,7,9,0,3,1,6,2,4,8]
quick_sort(array, 0, len(array) - 1)
print(array)
파이썬을 이용해서 더욱 간단하게 만들 수 있다.
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array):
#리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] #피벗은 첫 번째 원소
tail = array[1:]#피벗을 제외한 리스트
left_side = [x for x in tail if x <= pivot] #반할된 왼쪽 부분
right_side = [x for x in tail if x > pivot] #반할된 오른쪽 부분
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
5. 새롭게 알게 된 것
[x for x in array if x <= pivot]
array리스트에서 각각 원소를 x로 꺼내고 그 x가 pivot다 작을 때의 경우의 x만 꺼낸다.
'CodingTest > 정렬 알고리즘' 카테고리의 다른 글
두 배열의 원소 교체 (0) | 2022.07.08 |
---|---|
정렬 알고리즘 종류와 특징 비교하기 (0) | 2022.07.08 |
계수 정렬 (0) | 2022.07.08 |
삽입 정렬 (0) | 2022.07.08 |
선택 정렬 (0) | 2022.07.08 |