Remarks
본 글은 위키백과, 나무위키 등의 자료를 참고하여 작성되었습니다.
성능 정리
| Worst | Average | Best | Space complexity | |
|---|---|---|---|---|
| Bubble | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Quick | $O(n^2)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ |
| Insertion | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ |
| Heap | $O(n)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ |
| Merge | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ |
1. 비교에 의한 정렬(comparative sort)
1.1 교환법
1.1.1 Bubble sort
- 거품(maximum)이 수면(배열의 뒷부분)으로 올라오는 듯한 모습을 보여 지어진 이름
- 거의 모든 상황에서 최악의 성능
1
2
3
4
5
6
7
def bubbleSort(x):
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
1.1.2 Selection sort
- 가장 작은 값을 선택하여 맨 앞에 넣는 방식
- Selection sort는 bubble sort보다 우수하다
- 알고리즘이 단순하고 메모리가 제한적인 경우 사용할만함
1
2
3
4
5
6
7
8
9
def selectionSort(x):
length = len(x)
for i in range(length-1):
indexMin = i
for j in range(i+1, length):
if x[indexMin] > x[j]:
indexMin = j
x[i], x[indexMin] = x[indexMin], x[i]
return x
1.1.3 Quick sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quicksort(x):
if len(x) <= 1:
return x
pivot = x[len(x) // 2]
less = []
more = []
equal = []
for a in x:
if a < pivot:
less.append(a)
elif a > pivot:
more.append(a)
else:
equal.append(a)
return quicksort(less) + equal + quicksort(more)
1.2 삽입법
1.2.1 Insertion sort
- 앞에서부터 정렬된 배열에 들어갈 자신의 위치에 삽입하는 방식
- Bubble, selection sort에 비해 빠르다.
- In-place 알고리즘
- 이미 정렬이 되어 있는 경우, 현실적으로 가장 빠른 정렬 알고리즘
- 배열이 길수록 비효율적
1
2
3
4
5
6
7
8
9
def insert_sort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j]
j = j - 1
x[j+1] = key
return x
1.3 선택법
1.3.1 Heap sort
1
2
3
4
5
6
7
8
def heap_sort(unsorted):
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
1.4 병합법
1.4.1 Merge sort
- 원소의 개수가 1개 혹은 0개가 될 때까지 나눈 다음 분할 정복을 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
low_arr = merge_sort(arr[:mid])
high_arr = merge_sort(arr[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
return merged_arr
2. 분산에 의한 정렬(distributive sort)
2.1 분배법
2.1.1 Radix sort(기수 정렬)
…
PREVIOUSEtc