[알고리즘] 퀵 정렬 (quick sort)
1. 퀵 정렬 (quick sort) 이란?
- 정렬 알고리즘의 꽃
- 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
- 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
- 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함
2. 알고리즘 구현
quicksort 함수 만들기
- 만약 리스트 갯수가 한개이면 해당 리스트 리턴
- 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(
pivot)으로 놓기 left,right리스트 변수를 만들고,- 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(
pivot)
- 기준점보다 작으면left.append(해당 데이터)
- 기준점보다 크면right.append(해당 데이터) return quicksort(left) + pivot + quicksort(right)로 재귀 호출
리스트로 만들어서 리턴하기:
return quick_sort(left) + [pivot] + quick_sort(right)
프로그래밍 연습
def qsort(data):
if len(data) <= 1:
return data
left, right = list(), list()
pivot = data[0]
for i in range(1, len(data)):
if data[i] < pivot:
left.append(data[i])
else:
right.append(data[i])
return qsort(left) + [pivot] + qsort(right) # [pivot] 형태로 리스트로 만들어서 합쳐야 한다.
코드 이미지
테스트
위 퀵정렬 코드를 파이썬 list comprehension을 사용해서 더 깔끔하게 작성해보기
🌟 파이썬 Comprehension을 잘 모른다면, 이 사이트를 참고하자!
# 파이썬의 list comprehension 사용
def qsort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [x for x in data[1:] if x < pivot]
right = [x for x in data[1:] if x >= pivot]
return qsort(left) + [pivot] + qsort(right) # [pivot] 형태로 리스트로 만들어서 합쳐야 한다.
코드 이미지
테스트
3. 알고리즘 분석
- 병합정렬과 유사, 시간복잡도는 $O(nlogn)$
- 단, 최악의 경우
- 맨 처음 pivot이 가장 크거나, 가장 작으면
- 모든 데이터를 비교하는 상황이 나옴
- $O(n^2)$
💛 개인 공부 기록용 블로그입니다. 👻