Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- mongoose
- class
- cookie
- Dinosaur
- flask
- 정렬
- MySQL
- game
- typeORM
- GIT
- jest
- MongoDB
- Bull
- nodejs
- nestjs
- 공룡게임
- OCR
- Nest.js
- Queue
- TypeScript
- JavaScript
- dfs
- Express
- 자료구조
- 게임
- Sequelize
- react
- Python
- AWS
Archives
- Today
- Total
포시코딩
퀵 정렬(Quick Sort) 본문
728x90
퀵 정렬(Quick Sort)
- 정렬 알고리즘의 꽃
- 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성
- 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해 다시 동일 함수를 호출하여 위 작업을 반복
- 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴한다.
배우기 앞서 기대한 알고리즘 중 하나
파이썬에서 구현 시 아름다울 정도라는데 얼마나 감동할 수 있을지 기대를 잔뜩 하고 들어갔던 것 같다.
크게는 아래 순서를 따라간다.
- pivot은 보통 제일 앞에걸로 지정
- pivot을 기준으로 분류
- 분리된 left, right를 재귀 함수를 통해 1~2 반복
- 그렇게 데이터 수가 1개가 될 때 까지 반복한다.
구현
def qsort(list):
if len(list) <= 1:
return list
pivot = list[0]
left, right = [], []
for i in range(1, len(list)):
if list[i] < pivot:
left.append(list[i])
else:
right.append(list[i])
return qsort(left) + [pivot] + qsort(right)
import random
arr = random.sample(range(100), 10)
print(qsort(arr))
배운 개념으로 코드 구현 후 나도 모르게 박수를 치고 있었다.
문자, 그림 등으로 설명할 때는 장황하기 그지 없었는데
막상 코드로 표현하니 진짜 간결 그 자체.
이걸 발견한 사람은 얼마나 뿌듯했을까
위 코드를 리스트 컴프리헨션을 사용하면 훨씬 간단하게 표현할 수 있다고 한다.
def qsort(list):
if len(list) <= 1:
return list
pivot = list[0]
left = [x for x in list[1:] if x < pivot]
right = [x for x in list[1:] if x > pivot]
return qsort(left) + [pivot] + qsort(right)
리스트 컴프리헨션을 사용한 코드.
분석
시간복잡도
pivot 기준 두 개로 나뉘니 logn
하짐나 나뉜 데이터에서 각각 비교할 때 결국 n개 모두 비교해야 하니
O(nlogn)이 된다.
* 단, 최악의 경우 맨 처음 pivot이 가장 크거나 작으면 모든 데이터를 비교해야되서 O(n2)
728x90
'자료구조알고리즘 > 이론' 카테고리의 다른 글
탐색 알고리즘 - 이진 탐색(Binary Search) (0) | 2023.04.14 |
---|---|
병합 정렬(Merge Sort) - 복습필요 (0) | 2023.04.14 |
동적 계획법(DP), 분할 정복(Divide and Conquer) (0) | 2023.04.13 |
재귀 활용 - 회문(팰린드롬), 더하기 조합 (0) | 2023.04.13 |
힙(Heap) (0) | 2023.04.12 |