CS/Data Structure
[자료구조]정렬 알고리즘 비교 정리
frog-in-well
2022. 7. 27. 17:52
1. O(n²) 정렬
1.1 선택 정렬
- 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택
- 1번째 인덱스부터 배열을 탐색하여 1번째로 작은 값을 1번째에 위치 → 2번째 인덱스부터 탐색 & 2번째에 위치 → 3번째부터 탐색 & 3번째에 위치 → … → 총 (n-1)번 반복
- 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
- 시간 복잡도
- 1번째 루프에서 비교 : n-1
- 2번째 루프에서 비교 : n-2
- (n-1)+(n-2)+…+1 = n(n-1)/2
- 최선, 최악, 평군 모두 O(n²)
def selection_sort(L):
for i in range(N): #해당 위치 i에 들어갈 원소를 선택
minVal_idx = i
for j in range(i+1,N):
if L[j] < L[minVal_idx] :
minVal_idx = j
L[i], L[minVal_idx] = L[minVal_idx], L[i]1.2 삽입 정렬
- 원소는 정해져있고, 원소를 넣을 위치를 찾고 삽입하면 된다.
- k번째 원소를 그 앞의 원소들을 차례대로 비교해 적절한 위치에 삽입 후 뒤의 배열을 한 칸씩 뒤로 밀어내기. (k=2번째 원소부터 n번째 원소까지)
- 삽입하고 한 번에 밀어내는 대신에 차례대로 비교하며 왼쪽에 위치한 값이 오른쪽에 위치한 값보다 크다면 왼쪽의 값을 오른쪽에 저장한다. (밀어내는 효과)
- 비교하다 왼쪽 값이 더 작은 경우에 k번째 원소를 넣어준다.
- 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
- 시간 복잡도
- 최선의 경우 O(n)
- 최악, 평균의 경우 O(n²)
#왼쪽에서 나보다 큰거는 뒤로 밀어, (앞에는 정렬 완료)
def insertion_sort(L):
for i in range(1,N):
val = L[i]
leftVal_idx = i-1
while leftVal_idx >=0 and L[leftVal_idx] > val :
L[leftVal_idx+1] = L[leftVal_idx]
leftVal_idx-=1
L[leftVal_idx+1] = val1.3 거품 정렬
- 1번째 원소와 2번째 원소를 비교, 2번째 원소와 3번째 원소를 비교, … , n-1번쨰 원소와 n번째 원소를 비교 → 1번째 원소와 2번째 원소를 비교, … , n-2번째 원소와 n-1번째 원소를 비교 → …
- 루프 1회당 마지막 1개의 원소가 정렬된다.
- 1번째 루프에서 가장 큰 원소가 맨 뒤에 위치하게 된다.
- 2번째 루프에서 2번째로 큰 원소가 뒤에서 2번째에 위치하게 된다.
- 스왑되는 횟수를 체크해 한 번도 스왑되지 않는 경우가 발생하면 정렬을 멈추면 된다.
- 스왑되는 마지막 인덱스를 저장해 해당 위치까지만 스왑하면 추가적인 최적화 가능하다. (저장된 인덱스 이후로는 완전히 정렬되었다는 의미)
- 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도
- 시간 복잡도
- 최선의 경우 O(n)
- 최악, 평균의 경우 O(n²)
#제일 큰 거 뒤로 밀어, 다시 처음으로 가서 두번째로 큰거 뒤로 밀어, (뒤에는 정렬 완료)
def bubble_sort(L):
end = N-1
while end>0:
# isSwapped=False
lastSwapped=0
for i in range(end):
if L[i] > L[i+1]:
L[i], L[i+1] = L[i+1], L[i]
lastSwapped = i
# if not isSwapped : break
end = lastSwapped2. O(n log n) 정렬
2.1 퀵 정렬
- 평균적인 상황에서 최고의 성능
- 배열에서 하나의 원소(pivot)을 고른다.
- 피벗 앞에는 피벗보다 작은 원소들이 오고 뒤에는 큰 원소들이 오도록 피벗을 기준으로 배열을 분할한다.
- 분할된 두 배열에 대하여 재귀적으로 반복한다.
- 공간 복잡도 - O(log n) - 제자리 정렬, 재귀로 인한 스택 메모리
- 시간 복잡도 - pivot을 선택하는 방법에 따라 달라진다.
- 평균, 최선의 경우 O(n log n) - pivot을 기준으로 같은 개수의 값들이 분할
- 최악의 경우 - O(n²) 값들이 한 쪽으로 치우치게 되는 경우
def quick_sort(L,s,e):
if s >= e :
return
pivot = s
l,r = s+1, e
while l<=r :
#pivot 보다 큰 값을 왼쪽에서부터 찾는다.
while l<=e and L[l] <= L[pivot] :
l+=1
#pivot 보다 작은 값을 오른쪽에서부터 찾는다.
while r>=s+1 and L[r] >= L[pivot] :
r-=1
#l,r 이 엇갈린 경우 피벗 이동, l위치에 pivot
if l>r :
L[r] , L[pivot] = L[pivot], L[r]
else:
L[l] , L[r] = L[r], L[l]
quick_sort(L, s, r-1)
quick_sort(L, r+1, e)2.2 병합 정렬 (Merge Sort)
- 요소를 쪼갠 후 다시 병합하며 정렬
- 합치는 배열의 원소 2개 이상이면 최솟값부터 차례대로 하나씩 비교한다.
- 공간 복잡도 - O(n) -> 새로운 배열 필요
- 시간 복잡도
- 평균, 최선,최악 모두 O(n log n)
def merge_sort(L):
def sort(l, r):
if r-l<2 :
return
m = (l+r)//2
sort(l,m)
sort(m+1,r)
merge(l,m,r)
def merge(left,mid,right):
tmp = []
l, r = left, mid
while l < mid and r < right :
if L[l] < L[r]:
tmp.append(L[l])
l+=1
else:
tmp.append(L[r])
r+=1
#l, r 배열 중 아직 병합 안된 것들 처리
while l < mid :
tmp.append(L[l])
l+=1
while r < right:
tmp.append(L[r])
r+=1
for i in range(left, right):
L[i] = tmp[i-left]
return sort(0, len(L))2.3 힙 정렬
- 최대 힙 구성
- 루트의 값을 제거하고(출력) 마지막 요소를 루트에 넣는 것을 반복
- 공간 복잡도 - O(n)
- 시간 복잡도
- 최선의 경우 O(n)
- 평균, 최악의 경우 O(n log n)
3. 하이브리드 정렬
3.1 팀 정렬
- 실제 데이터가 무작위가 아닌 어느 정도 지역 참조성을 따른다는 가정에서의 알고리즘
- python 내장 함수 sort()의 방법
- 병합 정렬 + 삽입 정렬
- 작은 n에 대하여 삽입 정렬이 매우 빠르다.
- 작은 덩어리로 자르고 삽입 정렬을 한 뒤 병합하자는 아이디어
- 2^x 형태의 덩어리 삽입 정렬 이용해서 만들기(min run) → 뒤에도 정렬된 것이 있다면 더 큰 덩어리로 합치기(run)
- run을 스택에 넣으며 병합한다. 스택에 들어간 run의 크기가 피보나치 형태가 되도록 반복해서 병합한다.
- 삽입 정렬을 할 때, 하나 씩 탐색하는 것이 아니라 이분 탐색 이용
- 공간 복잡도 - 병합 정렬에 비해 적은 추가 메모리
- 시간 복잡도
- 최선의 경우 O(n)
- 평균, 최악의 경우 O(n log n)