나만 보려고 기록하는 CS 개념
왜 알아야 돼?
기술 면접 빈출이야. 취직 안 할 거야?
--그렇구나...
개념 설명해 줘
퀵 정렬(quick sort)는 분할 정복을 활용하는 정렬 알고리즘이야.
이름만큼 빠른 알고리즘이래.
시간복잡도 기준 평균적으로 O(nlogn) 최악은 O(n^2)
--O(n^2)이면 안 좋은 거 아냐?
맞아. 불안정 정렬이라는 특성이 있어서,
정렬된 배열에 대해서는 O(n^2)의 시간 복잡도를 가져.
대신 다른 O(nlogn)의 알고리즘보다 평균적으로 빠른 속도를 보장해서 좋아.
매번 수행마다 하나의 요소를 정렬에서 제거하거든.
의사 코드로 설명해 줘
1. 피봇 정하기
주어진 배열에서 요소 하나를 선택해.
이게 피봇이 될 거야.
피봇은 쉽게 말하면 기준점이야.
기준점을 정하는 방법에는 4가지 정도 있어.
- 처음
- 마지막
- 중간
- 랜덤
완벽한 기준은 없고, 여기서는 처음으로 진행해보자.
2. 분할
(피봇보다 작은 원소) + (피봇) + (피봇보다 큰 원소)
배열을 위와 같이 정렬해.
정렬을 마치고 나면, 기존 배열은 피봇을 기준으로 2개의 부분 배열로 나뉘어.
이러면 첫 번째 분할이 종료된 거야.
분할을 마치고 나면 피봇은 더 이상 움직이지 않아 (퀵 정렬이 빠른 이유)
3. 반복
분할된 2개의 부분 배열에 대해 각각 1~2번 과정을 재귀적으로 반복해.
작은 리스트 크기가 0이나 1이 되면 종료.
구현해 줘
- 일반적인 방식
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
# 부분 배열의 원소가 1개인 경우 정렬 종료
if start >= end:
return
pivot = start # 피봇을 첫 번째 원소로 지정 (임의로 고른 거임)
left = start + 1
right = end
while left <= right: # index가 왼쪽 < 오른쪽일 때만 동작
# 왼쪽 커서가 피봇보다 작은 값을 찾을 때까지
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)
quick_sort(array, 0, len(array)-1)
print(array)
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]- 놀라운 방식
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 = [x for x in tail if x <= pivot] # 피봇보다 작거나 같은 요소 left 배열에 추가
right = [x for x in tail if x > pivot] # 피봇보다 큰 요소 right 배열에 추가
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]레퍼런스
독학 머신