[Algorithm] 퀵 정렬 (Quick Sort) .04Programming/Algorithm2020. 12. 29. 20:38
Table of Contents
이번에 알아볼 알고리즘은 퀵 정렬 (Quick Sort) 입니다.
불안정 정렬이며, 다른 원소와 비교만으로 정렬하는 비교 정렬에 속합니다
분할정복알고리즘 중에 하나로, 평균적으로 매우 빠른 수행속도를 자랑합니다.
분할정복이란?
큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
🤔 과정 및 코드
원소 안에서 원소 하나를 선택합니다. 선택한 원소를 피벗(Pivot)이라고 합니다.
피벗의 값을 기준으로 작은 원소는 왼쪽으로 큰 값은 오른쪽으로 정렬하고, 피벗 값은 사이로 들어가게 됩니다.
이후 왼쪽과 오른쪽 리스트에 각각 다시 퀵정렬을 반복하며 정렬하여 더 이상 리스트들이 분할되지 않을때 까지 반복합니다.
📝 Python 예시 코드.
def QuickSort(arr):
if len(arr) <= 1:
return arr
left, right = [], []
pivot = arr[0]
for a in range(1, len(arr)):
if pivot < arr[a]:
right.append(arr[a])
else:
left.append(arr[a])
return QuickSort(left) + [pivot] + QuickSort(right)
🕒 시간 복잡도.
최선인 경우 O(N * logN)의 시간 복잡도를 가지며, 보통인 경우도 O(N * logN)의 시간 복잡도를 가진다.
리스트가 불균형하게 나눠지는(한쪽이 작은 길이의 리스트를 가지는) 최악의 경우 O(N^2)의 시간 복잡도를 가지게 된다. 그러나 일반적인 경우 O(N * logN) 시간복잡도를가지기 때문에 앞선 정렬 알고리즘 보다 빠르다.
💾 공간 복잡도.
배열외 공간을 쓰지 않기 때문에 O(N)이다.
✋ 장점과 단점.
장점.
속도가 빠르며, 다른 공간을 필요로 하지 않는다.
단점.
정렬된 리스트에 대해서는 불균형 분할이여서 수행시간이 더 오래 걸린다.
참조.
'Programming > Algorithm' 카테고리의 다른 글
Javascript로 백준 풀기. (0) | 2023.03.13 |
---|---|
[Algorithm] 병합 정렬 (Merge Sort) .05 (0) | 2021.01.07 |
[Algorithm] 삽입 정렬(Insertion Sort) .03 (0) | 2020.12.22 |
[Algorithm] 선택 정렬(Selection Sort) .02 (0) | 2020.12.22 |
[Algorithm] 거품 정렬(Bubble Sort) .01 (0) | 2020.12.21 |
@RyuWoong :: #깜깜한 방에서 코딩하기
삽질의 기록과 일상을 남기는 블로그입니다. 주로 React Native를 다룹니다.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!