정렬 알고리즘
작성 중
- 데이터를 오름차순으로 정렬해보자!
1 크기가 $n$인 정렬되지 않은 리스트가 있다
List = [5, 8, 7, 1, 2]
2 첫 번째 인덱스와 나머지 $n - 1$개의 수를 비교하여 가장 작은 수와 위치를 바꾼다
3 5와 비교하여 1이 가장 작으므로 5와 1의 위치를 바꾼다
List = [1, 8, 7, 5, 2]
4 이제 두 번째 인덱스와 나머지$n - 2$개의 수를 비교하여 남은 수 중 가장 작은 수와 위치를 바꾼다
5 8과 비교하여 2가 가장 작으므로 8과 2의 위치를 바꾼다
List = [1, 2, 7, 5, 8]
6 이런 식으로 $n-1$번째 인덱스와 나머지 1개의 수를 비교하여 오름차순 정렬을 마친다
List = [1, 2, 5, 7, 8]
List = [5, 8, 7, 1, 2]
n = len(List)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if List[j] < List[min_idx]:
min_idx = j
List[i], List[min_idx] = List[min_idx], List[i]
print(List)
- 연속된 인덱스를 비교하여 더 큰 값을 오른쪽으로 보냄
- 한 사이클을 돌면 가장 큰 값이 맨 뒤에 위치
- 사이클마다 남은 수 중 가장 큰 값이 뒤에 위치함
1 크기가 $n$인 정렬되지 않은 리스트가 있다
List = [5, 8, 7, 1, 2]
2 첫 번째 인덱스와 두 번째 인덱스를 비교하여 더 큰값을 오른쪽에 위치시킨다
3 5와 8을 비교하면 8이 더 크므로 8을 오른쪽을 보낸다
List = [5, 8, 7, 1, 2]
4 이제 두 번째 인덱스와 세 번째 인덱스를 비교한다
5 8과 7을 비교하면 8이 더 크므로 8을 오른쪽으로 보낸다
List = [5, 7, 8, 1, 2]
6 이런식으로 한 사이클을 돌면 8이 마지막에 위치한다
List = [5, 7, 1, 2, 8]
7 다시 사이클을 돌면 7이 8 왼쪽에 위치한다
List = [5, 1, 2, 7, 8]
8 이런식으로 $n - 1$ 번의 사이클을 돌면 자료가 오름차순으로 정렬된다
List = [1, 2, 5, 7 ,8]
List = [5, 8, 7, 1, 2]
n = len(List)
for i in range(n - 1, 0, -1):
for j in range(i):
if List[j + 1] < List[j]:
List[j + 1], List[j] = List[j], List[j + 1]
print(List)
1 크기가 $n$인 정렬되지 않은 리스트가 있다
List = [5, 8, 7, 1, 2]
2 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입
List = [5, 8, 7, 1, 2]
3 5와 8을 비교하면 8이 더 크므로 8을 오른쪽을 보낸다
List = [5, 8, 7, 1, 2]
4 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입
5 7과 8을 비교하면 8이 더 크고 5와 7을 비교하면 7이 더 크므로 5와 8사이에 위치한다
List = [5, 7, 8, 1, 2]
6 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입
7 1이 부분 리스트 중 가장 작으므로 맨 앞에 삽입
List = [1, 5, 7, 8, 2]
8 마지막 원소를 부분 리스트에서 적절한 위치에 삽입
9 2는 부분 리스트 중 1 다음으로 작으므로 1 오른쪽에 삽입
List = [1, 2, 5, 7, 8]
List = [5, 8, 7, 1, 2]
n = len(List)
for i in range(1, n):
j = i - 1
key = List[i]
while List[j] > key and j >= 0:
List[j + 1] = List[j]
j = j - 1
List[j + 1] = key
print(List)
병합 정렬 알고리즘
1 크기가 $n$인 정렬되지 않은 리스트가 있다
List = [5, 8, 7, 1, 2, 3, 9, 4]
2 그룹을 두 그룹으로 나눈다
[5, 8, 7, 1], [2, 3, 9, 4]
3 각 그룹을 두 그룹으로 나눈다
[5, 8], [7, 1], [2, 3], [9, 4]
4 이를 요소가 1개 남을 때까지 반복한다
[5], [8], [7], [1], [2], [3], [9], [4]
5 이제 나눈 순서의 역순으로 두 그룹씩 오름차순으로 병합한다
[5, 8], [1, 7], [2, 3], [4, 9]
6 이를 정렬이 끝날 때까지 반복한다
[1, 5, 7, 8], [2, 3, 4, 9]
List = [1, 2, 3, 4, 5, 7, 8, 9]
- 이 코드는 아래 코드보다 느림
- list.pop(0)은 $O(N)$임
List = [5, 8, 7, 1, 2, 3, 9, 4]
def mergeSort(x):
if len(x) <= 1:
return x
mid = len(x) // 2
left = x[:mid]
right = x[mid:]
next_left = mergeSort(left)
next_right = mergeSort(right)
return merge(next_left, next_right)
def merge(left, right):
sorted_list = []
while left and right:
if left[0] < right[0]:
sorted_list.append(left.pop(0))
else:
sorted_list.append(right.pop(0))
while left:
sorted_list.append(left.pop(0))
while right:
sorted_list.append(right.pop(0))
return sorted_list
mergeSort(List)
- 그래서 pop(0) 함수를 사용하지 않음
- 아래의 코드가 이해가 잘 안될 수 있다
- 그래서 어떻게 split하고 merge가 되는지 알아보기로 하자
- 밑의 출력을 보니 처음으로 merge()에 대입된 left와 right는 [5]와 [8]임을 알 수 있다
- 처음으로 넣은 값은 [5, 8, 7, 1, 2, 3, 9, 4]인데 신기하다
- 자세히 살펴보자
List = [5, 8, 7, 1, 2, 3, 9, 4]
k = 0
def merge_sort(x): ## 나누기
n = len(x)
if n <= 1:
return x
mid = n // 2
left = x[:mid] ## mid를 기준으로 왼쪽
right = x[mid:] ## mid를 기준으로 오른쪽
next_left = merge_sort(left) ## 재귀적으로 나누기
next_right = merge_sort(right) ## 재귀적으로 나누기
global k
k += 1
print('return 횟수 %s' %k)
return merge(next_left, next_right)
def merge(left, right): ## 병합하기
i = 0
j = 0
sorted_list = list()
print(left)
print(right)
while i < len(left) and j < len(right): ## left와 right중 더 작은 값 넣기
if left[i] <= right[j]:
sorted_list.append(left[i])
i += 1
else:
sorted_list.append(right[j])
j += 1
## left와 right 중 남은 값을 넣어주기
while i < len(left):
sorted_list.append(left[i])
i += 1
while j < len(right):
sorted_list.append(right[j])
j += 1
return sorted_list
print('\n정렬된 배열:', merge_sort(List))
- 우선 mergeSort 함수에서 return은 총 7번 일어남을 알 수 있다
- 각 상황에서 어떤일이 일어나는지 알아보자
1. 우리는 print(mergeSort(List))를 통해 mergeSort 함수에 List라는 input을 넣었다
2. mergeSort에는 [5, 8, 7, 1, 2, 3, 9, 4]이 대입됐다
3. left는 [5, 8, 7, 1], right는 [2, 3, 9, 4]이다
4. next_left는 mergeSort([5, 8, 7, 1]), next_right는 mergeSort([2, 3, 9, 4])이다
5. merge(next_left, next_right)값을 return한다
6. 근데 merge(next_left, next_right)를 return하려고 보니까 next_left, next_right 값을 알아야한다
7. 4번으로 돌아가서 보면 mergeSort([5, 8, 7, 1])와 mergeSort([2, 3, 9, 4])를 구해야 한다 ---> 그럼 구하면 되지
8. mergeSort에 [5, 8, 7, 1]이 대입된다
9. 그러면 mergeSort([5, 8, 7, 1])는 merge(mergeSort([5, 8]), mergeSort([7, 1]))를 return한다
10. 근데 mergeSort([5, 8]), mergeSort([7, 1])값은 뭐지?? ---> 이것도 구해야 한다
11. mergeSort([5, 8])을 구하면 next_left = [5], next_right = [8]이다
12. merge(next_left, next_right)는 merge([5], [8])이 되고 드디어 merge함수에 left와 right가 대입된다 ---> 그래서 처음 left와 right로 출력된 값이 [5]와 [8]이었던 것: return1
13. merge([5], [8])은 [5,8]인 sorted_list를 return한다 ---> mergeSort([5, 8])은 [5, 8]을 return한다 즉, mergeSort([5, 8]) = [5, 8]
14. 이제 mergeSort([5, 8])를 구했으니 mergeSort([7, 1])값을 구할 차례이다
15. mergeSort([7, 1])은 merge([7], [1])이고 [1, 7]을 return한다 ---> mergeSort([7, 1]) = [1, 7]: return2
16. 이제 8번을 보자. 8번은 merge([5, 8, 7, 1])이고 merge(mergeSort([5, 8]), mergeSort([7, 1]))를 return한다
17. 이때는 mergeSort([5, 8])와 mergeSort([7, 1])를 모르는 상태였지만 이제는 구해서 알고 있다
18. merge([5, 8], [1, 7])을 구해보면 sorted_list로 [1, 5, 7, 8]을 return한다: return3
19. 이제 mergeSort([2, 3, 9, 4])을 구할 차례이다. 이는 위에서 한 방식대로 따라하면 된다
20. 결과적으로 print(mergeSort(List))는 [1, 2, 3, 4, 5, 7, 8, 9]을 출력하게 된다
- 메모리 아끼는 병합 정렬 참고: https://www.daleseo.com/sort-merge/
- 피벗을 하나 정하고 피벗을 기준으로 왼쪽에는 피벗보다 작거나 같은 원소가 오른쪽에는 피벗보다 큰 원소가 위치하도록 배열을 변경한다
- 위에서 나눠진 왼쪽 배열과 오른쪽 배열에 대해서도 위의 연산을 재귀적으로 반복한다
def partition(arr, left, right):
## left는 입력된 배열의 가장 왼쪽 인덱스. right는 가장 오른쪽 인덱스
pivot = arr[right] ## 피벗은 주어진 배열(arr[left:right+1], 끝 값 포함 X)에서 마지막 위치(right)의 원소이다
i = left - 1 ## 피벗보다 작은 값을 넣을 배열의 위치(인덱스)
for j in range(left, right): ## 피벗을 제외한 배열의 인덱스(left~right-1)
if arr[j] <= pivot: ## 피벗보다 작거나 같은 경우
i += 1 ## 값을 하나 넣을 거니까 배열의 위치에 +1
arr[i], arr[j] = arr[j], arr[i] ## 피벗보다 작은 값을 i 인덱스의 값과 swap 한다(메모리 절약을 위해 새로운 list를 안 만듦 ---> in-place algorithm)
print(f'현재 배열의 상태: {arr}') ## 배열이 정렬되는 과정을 확인하자
## for문이 끝나면 입력된 배열이 다음과 같다 ---> [pivot보다 작거나 같은 값, (p) pivot보다 큰 값, pivot]
## 이제 pivot을 (p) 위치에 있는 값과 swap 하면 된다
## 여기서 (p)의 인덱스는 i + 1이다
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1 ## 피벗의 인덱스를 리턴한다
def quick_sort(arr, left, right):
if left < right:
pivot_idx = partition(arr, left, right) ## 피벗을 기준으로 왼쪽에는 작거나 같은 값을 오른쪽에는 큰 값이 위치하도록 한다
quick_sort(arr, left, pivot_idx - 1) ## 다시 왼쪽 배열에 대해서 partition
quick_sort(arr, pivot_idx + 1, right) ## 다시 오른쪽 배열에 대해서 partition
List = [5, 8, 7, 1, 3, 2, 9, 4]
quick_sort(List, 0, len(List) - 1)
print(f'정렬된 배열: {List}')
- 참고: in-place algorithm 이란?
- 주어진 배열 외에 사용하는 메모리 양을 나타내는 공간복잡도가 $O(1)$임을 의미한다
- 위의 퀵 정렬을 응용하면 배열에서 $k$번째로 작은 값을 select하는 알고리즘을 만들 수 있다
- Quickselect: https://en.wikipedia.org/wiki/Quickselect
계수 정렬
- 카운팅 정렬이라고도 한다
- 양수만 가능, 값의 범위가 크면 안됨(메모리 크기를 넘기면 안됨)
- 수의 범위가 작다면(입력으로 주어지는 값들의 개수: 0 ~ 1이라고 수의 범위가 작은 것이 아님... 0 ~ 1사이의 수는 무한개이다) 카운팅 정렬을 통해 빠르게 정렬할 수 있음
- 비교 정렬이 아님 ---> 위의 코드들은 다른 요소값과 비교하는데 카운팅 정렬은 비교없이 데이터를 정렬함
- 입력으로 주어지는 input의 개수는 큰데 주어지는 값의 개수가 적다면 메모리 관점에서 효율적이다
- 예로 input이 최대1억개인데 값이 1 ~ 10까지라면 위에서 다룬 정렬은 1억크기의 배열이 필요하지만 카운팅 정렬에 경우는 크기가 10인 배열을 만들면 된다
- 하지만, 최대 수를 기준으로 배열을 만든다(최대값이 100인 경우 크기가 100인 리스트 생성)
- 그렇기에 [0, 1, 1, 1, 100]인 리스트를 정렬한다고 보면 숫자는 3개 뿐이지만 최대값이 100이므로 크기가 100인 리스트를 만들어야 한다 ---> 심한 메모리 낭비
1 최대 값이 k인 크기가 $n$인 정렬되지 않은 리스트가 있다
List = [5, 8, 7, 1, 1, 3, 9]
2 k = 10 이라고 가정하자. [0] * (k+1) 리스트를 만든다 --> 파이썬에서 인덱스는 0부터 시작하기 때문
count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 List 요소의 값을 x라 하면 count[x]의 값을 +1 해준다
count = [0, 2, 0, 1, 0, 1, 0, 1, 1, 1, 0]
4 count 리스트에서 자기(x) 앞에 몇개의 숫자가 있는지를 바탕으로 x의 위치를 결정하여 정렬한다. 예로 3의 경우 자기 앞에 숫자 2개가 있으므로 3번째이다
List = [1, 1, 3, 5, 7, 8, 9]
List = [5, 8, 7, 1, 1, 3, 9]
def counting_sort(arr):
count = [0] * (max(arr) + 1)
sorted_list = [0] * len(arr)
for i in arr:
count[i] += 1
## arr에 있는 수를 몇개인지 카운팅함
for j in range(1, max(arr) + 1):
count[j] += count[j - 1]
## count[j] 앞에 몇 개의 숫자가 있는지 저장
## count[5] = 10이라면 5가 x번 등장했다고 할 때 5앞에 10-x개의 숫자가 있다는 의미이므로 sorted_list[10-x : x]에 5가 위치한다. (x 번째 포함 no, x-1번째 까지)
for k in range(len(arr)):
sorted_list[count[arr[k]] - 1] = arr[k] ## 인덱스는 0부터 시작하므로 -1을 해줌
count[arr[k]] -= 1
return sorted_list
print(counting_sort(List))
| Name | $T_{\operatorname{comp}}(n)$ | $T_{\operatorname{swap}}(n)$ | Time(worst case) : $T(n)$ | Space | In-place(Extra) | Stable | Adaptive |
|---|---|---|---|---|---|---|---|
| Selection | $\Theta(n^2)$ | $\Theta(n)$ | $\Theta(n^2)$ | $\Theta(n)$ | Yes : $\Theta(1)$ | No | No |
| Bubble | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n)$ | Yes : $\Theta(1)$ | Yes | No |
| Bubble+ | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n)$ | Yes : $\Theta(1)$ | Yes | Yes |
| Insertion | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n)$ | Yes : $\Theta(1)$ | Yes | Yes |
| Merge | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $\Theta(n)$ | No : $\Theta(n)$ | Yes | No |
| Quick | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n)$ | Yes : $\Theta(\log n)$ | No | No |
| Heap | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $\Theta(n)$ | Yes : $\Theta(1)$ | No | No |
| Counting | No comparison | No swap | $\Theta(n+k)$ | $\Theta(n+k)$ | No : $\Theta(n+k)$ | Yes | No |
| Radix | No comparison | No swap | $\Theta(w(n+k))$ | $\Theta(n+k)$ | No : $\Theta(n+k)$ | Yes | No |
- 시간복잡도의 형태가 재귀 함수꼴로 되어 있어 해를 구할 줄 알아야 된다(ex: 병합 정렬)
- 아래는 이를 구하는 방법들이다
- $T(n)=T(n-1)+C$ 라고 하자
- $T(n) = T(n-1)+C = (T(n-2)+C) + C = \cdots = T(1) + (n-1)C$
- 그러므로 $T(n)=O(n)$
- $T(n) \leq 2T\left(\dfrac{n}{2}+10\right)+n$ 라고 하자
- $T(n)\leq cn\log n$ 이라고 추정한다(어떤 함수로 추정할지 잘 생각해야 됨) $\to$ $T(n)=O(n\log n)$
- $T(i)\leq ci\log i ,\;n_0\leq i< k$ 라고 가정한다
- 이제 $T(k)\leq ck\log k$ 일 때도 성립하는지 증명한다
- 위에 $(1)$번 식에서 $(2)$번 식으로 어떻게 전개되는지 간단히 설명
- 일단 $\text{(1)번 식} \leq \text{(2)번 식}$ 이라는 것은 $c(\log 3 -\log 2)k\geq 20c\log\dfrac{2k}{3}+k $을 뜻한다
- $c(\log 3 -\log 2)k\geq 20c\log\dfrac{2k}{3}$ $\to$ $k$를 매우 크게 하면 된다($k$를 무한히 크게 하면 무한히 큰 차이가 생김)
- $c(\log 3 -\log 2)k\geq k$ $\to$ $c$를 매우 크게 하면 된다($c$를 무한히 크게 하면 무한히 큰 차이가 생김)
- 결론
- $\dfrac{k}{2}+10\leq k,\, \dfrac{k}{2}+10\leq \dfrac{2k}{3}$을 만족하면서 충분히 큰 $k$와 충분히 큰 $c$를 고르면 $\text{(1)번 식} \leq \text{(2)번 식}$ 이 성립한다
- $T(n)=aT\left(\dfrac{n}{b}\right)+f(n)$ 일 때 적용 가능하다
- $a\geq 1,\,b> 1$이며 $f(n)$은 다항식 형태
- $h(n)=n^{\log_b a}$ $\to$ $n=1$인 sub-problems 개수
- case 1) $\lim\limits_{n\to\infty}\dfrac{f(n)}{h(n)}=0 \Longrightarrow T(n)=\Theta\left(h(n)\right)$
- case 2) $\lim\limits_{n\to\infty}\dfrac{f(n)}{h(n)}=\infty$ and $af\left(\dfrac{n}{b}\right) < f(n) \Longrightarrow T(n)=\Theta\left(f(n)\right)$
- case 3) $\lim\limits_{n\to\infty}\dfrac{f(n)}{h(n)}=\Theta(1) \Longrightarrow T(n)=\Theta\left(h(n)\log_2 n\right)$
- exception $\dfrac{f(n)}{h(n)}=\Theta\left(\log^k n\right)\Longrightarrow T(n)=\Theta\left(h(n)\log^{k+1} n\right)$
- 변수를 치환해서 마스터 정리를 적합시키기
- $T(n)=2T\left(\sqrt{n}\right)+\log_2 n$
- 위의 식에는 마스터 정리를 적용시키지 못한다($\sqrt{n}=n^{0.5}$과 $f(n)=\log_2 n$이 문제임, $n^1$ 이고 $f(n)$은 다항식이어야 한다)
- $m =\log_2 n \Longleftrightarrow 2^m=n$
- $T(2^m)=2T\left(2^{0.5m}\right)+m$
- $P(m) = T(2^m)$ 이라고 하자
- $P(m)=2P\left(\dfrac{1}{2}m\right)+m$ $\to$ 마스터 정리를 적용시킬 수 있다!
- 마스터 정리를 적용시키면 $P(m)=\Theta(m\log m)$이 되고 $m$을 다시 $\log_2 n$로 치환시키면 아래와 같다
- $T(n)=\Theta\left(\log n\log(\log n)\right)$