기초정렬
arr = [3, 2, 7, 116, 62, 235, 1, 23, 55, 77]
n = 10
for i in range(n-1, -1, -1):
max_idx = 0
for j in range(1, i+1):
if arr[max_idx] < arr[j]: max_idx = j
arr[max_idx], arr[i] = arr[i], arr[max_idx]
print(arr)
arr = [3, 2, 7, 116, 62, 235, 1, 23, 55, 77]
n = 10
for i in range(n-1, -1, -1):
arr[arr.index(max(arr[:i+1]))], arr[i] =\
arr[i], arr[arr.index(max(arr[:i+1]))]
print(arr)
## 버블 정렬
arr = [3, 2, 7, 116, 62, 235, 1, 23, 55, 77]
for i in range(len(arr)):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)Merge Sort
연습문제
boj-11728
import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
first_arr = list(map(int, input().rstrip().split()))
second_arr = list(map(int, input().rstrip().split()))
left = 0
right = 0
sorted_arr = []
while left < N and right < M:
if first_arr[left] < second_arr[right]:
sorted_arr.append(first_arr[left])
left+=1
else:
sorted_arr.append(second_arr[right])
right+=1
if right == M:
sorted_arr += first_arr[left:]
elif left == N:
sorted_arr += second_arr[right:]
print(*sorted_arr)이 코드는 머지소트의 조각코드라고 볼 수 있다. 이제 재귀를 통해서 머지소트를 구현해보자.
def merge(start:int, end:int) -> None:
mid = (start + end)// 2
left_idx = start
right_idx = mid
for i in range(start, end):
if left_idx == mid:
tmp[i] = arr[right_idx]
right_idx+=1
elif right_idx == end:
tmp[i] = arr[left_idx]
left_idx +=1
elif arr[left_idx] <= arr[right_idx]:
tmp[i] = arr[left_idx]
left_idx+=1
else:
tmp[i] = arr[right_idx]
right_idx+=1
for i in range(start, end):
arr[i] = tmp[i]
def merge_sort(start:int, end:int)-> None:
if start == end-1:
return
mid = (start + end) // 2
merge_sort(start, mid)
merge_sort(mid, end)
merge(start, end)
if __name__ == "__main__":
N = int(input())
arr = list(map(int, input().split()))
tmp_arr = [0] * N
merge_sort(0, N)
print(arr)Stable Sort
[38, 21, 21, 21] 이라는 나이가 담긴 배열이 있다고 했을 때 정렬을 하면 21 21 21 38로 21에 해당하는 수들은 어디에 위치해도 정렬되어 있다고 말할 수 있다.
이때 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable sort이다.
머지소트는 Stable Sort이다.
이 Stable Sort의 성질을 기억하고 있으면 시간순으로 정렬되어 있는 파일을 크기순으로 정렬하고 싶을 때 시간순을 신경쓰지 않고 파일 크기 순으로 정렬하면 파일 크기순으로 정렬하되 크기가 같다면 생성된 시간 순으로 정렬할 수 있다.
Quick Sort
이름에서 볼 수 있듯이 거의 모든 정렬 알고리즘 보다 빨라서 각종 라이브러리의 정렬은 대부분 퀵소트를 바탕으로 만들어져 있다.
코딩테스트에서 라이브러리 없이 정렬을 구현해야 한다면 절대 x 1000 퀵소트를 쓰지말고 머지소트로 정렬을 해라. 물론 퀵소트를 알 필요 없다는 건 아니다.
arr = [3, 2, 7, 116, 62, 235, 1, 23, 55, 77]
N = len(arr)
def quick_sort(start:int, end:int) -> None:
if start >= end - 1: return
pivot = arr[start]
left = start+1
right = end-1
while left <= right:
while arr[left] <= pivot: left +=1
while arr[right] > pivot: right -=1
if left > right: break
arr[left], arr[right] = arr[right] , arr[left]
arr[start] , arr[right] = arr[right], arr[start]
quick_sort(start, right)
quick_sort(right+1, end)
quick_sort(0, N)
print(arr)치명적인 단점
1,2,3,4,5,6,7,8을 퀵소트로 정렬한다면 시간복잡도가 얼마인가?
매번 선택되는 pivot은 중앙에 위치하게 되고 그로인해 반복되는 단계는 logN이 아니고 N이 된다. 따라서 시간복잡도는 O(N**2)가 된다.
이 경우에서 볼 수 있듯이 퀵소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N**2)이 된다.
라이브러리를 사용못한다면 퀵소트 보다 머지소트를 사용하라고 한 이유가 이 이유 때문이다. 퀵소트가 머지소트보다 빠른건 사실이나 같은 O(NlogN)에 돌아가기 때문에 충분히 빠르다.
최악의 경우 O(N**2)인 퀵소트를 쓸 필요가 전혀 없다.
라이브러리에서 극복하는방법 → 랜덤하게 피벗값을 고르는 방법, 일정깊이 이상 들어가면 힙소트로 정렬하는 등 다양한 방법으로 극복함
| Merge Sort | Quick Sort | |
|---|---|---|
| 시간복잡도 | O(NlogN) | 평균 O(NlogN)이고 최악 O(N**2) 단 평균적으로 merge sort보다 빠름 |
| 추가적으로 필요한 공간 | O(N) | O(1) → inplace sort |
| Stable Sort 여부 | O | X |
