1. 가장 비효율적인 정렬, 버블 정렬(Bubble Sort)
시간복잡도: O(n2)
def bubble(a):
n = len(a)
for _ in range(n-1):
for i in range(n-1):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
2. 제자리 정렬, 선택 정렬(Selection Sort)
시간복잡도 : O(n2)
def selection(a):
n = len(a)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if a[min_idx] > a[j]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
3. 제자리 정렬, 삽입 정렬(Insert Sort)
시간복잡도: 평균 O(n2)
def insert(a):
n = len(a)
for i in range(1, n):
j = i
while j > 0 and a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
j -= 1
4. 분할 정복의 진수를 보여주는 정렬, 병합 정렬(Merge Sort)
시간복잡도: 최선과 최악 모두 O(nlogn)
컴퓨터과학 역사상 최고의 천재라 일컬어지는 존 폰 노이만이 1945년에 고안.
퀵 정렬보다는 느리지만 일정한 실행 속도뿐만 아니라 안정 정렬(Stable Sort)라는 점에서 여전히 상용 라이브러리에 많이 쓰이고 있다.
분할 정복을 이미 알고 있다면 알고리즘도 이해하기 쉽다.
def merge(a, lo, hi):
if lo == hi:
return [a[lo]]
mid = lo + (hi-lo)//2
left = merge(a, lo, mid)
right = merge(a, mid+1, hi)
merged = []
while left and right:
if left[0] < right[0]:
merged.append(left.pop(0))
else:
merged.append(right.pop(0))
return merged + left + right
5. 성능이 왔다갔다하는 정렬, 퀵 정렬(Quick Sort)
시간복잡도: 평균 O(nlogn), 최악 O(n2) --> 입력값에 따라 성능 편차가 심한 편
영국의 컴퓨터과학자 토니 호어가 1959년에 고안.
피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬(Partition-Exchange Sort)라고도 불림.
병합 정렬과 마찬가지로 분할 정복 알고리즘. 그러나 불안정 정렬이 문제점이다.
퀵 정렬에는 많은 버전이 있지만 로무토 파티션이 간결하고 이해가 쉬워 잘 사용된다.
def quick(a, lo, hi):
def partition(lo, hi):
pivot = a[hi]
left = lo
for right in range(lo, hi):
if a[right] < pivot:
a[left], a[right] = a[right], a[left]
left += 1
a[hi], a[left] = a[left], a[hi]
return left
if lo < hi:
pivot = partition(lo, hi)
quick(a, lo, pivot-1)
quick(a, pivot+1, hi)
안정 정렬 VS 불안정 정렬
안정 정렬 알고리즘은 중복된 값을 입력 순서와 동일하게 정렬한다.
안정 정렬 - 병합 정렬, 버블 정렬, 삽입 정렬
불안정 정렬 - 선택 정렬, 퀵 정렬
+추가) 계수정렬
계수정렬은 한정된 조건에서만 사용할 수 있다. 데이터의 크기가 한정되어 있고 정수형태로 표현할 수 있을 때만 사용가능하다. 대신 데이터의 개수가 N, 데이터 중 최댓값이 K일때 계수정렬은 최악의 경우에도 시간복잡도 O(N+K)를 보장한다. 또한 중복된 값이 많을 때 매우 유리하다. 원리도 매우 간단하다. 여분의 리스트를 빌려쓴다.
def countsort(A):
## Assume all element are zero or natural number.
sub = [0]*(max(A)+1)
for num in A:
sub[num] += 1
result = []
for i in range(len(sub)):
for k in range(sub[i]):
result.append(i)
return result
a = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
b = countsort(a)
print(b)
>> [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]출처:
<파이썬 알고리즘 인터뷰> 박상길 지음, 정진호 일러스트, 책만, 2020(https://www.onlybook.co.kr/entry/algorithm-interview)
댓글