정렬알고리즘 (Python 코드까지)
Bubble Sort, Selection Sort, Insertion sort, Counting sort, Merge Sort, Quick sort, Python Sort 의 기본적인 개념과 Python 코드 그리고 시간복잡도까지 알아보자.
먼저 설명에 앞서, 각 정렬별 시간복잡도를 살펴보면 아래와 같다.
1. Bubble sort
n 개의 원소를 가진 배열을 정렬할 때, In-place sort 로 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.
애니메이션으로 보면 더 빠르게 이해가 갈것이다.
결국 앞에서 부터 옆의 숫자와 비교해가면서 스위칭해주는 것이다.
시간 복잡도 : O(n^2)
Python 코드
1
2
3
4
5
def bubble_sort(arr):
for i in range(0, len(arr)):
for j in range(len(arr)-1, i, -1):
if arr[j-1] > arr[j]:
arr[j-1], arr[j] = arr[j], arr[j-1]
2. Selection sort
n 개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index 를 저장해둔다. 그리고 최종적으로 한 번만 바꿔준다. 하지만 여러 번 비교를 하는 것은 마찬가지이다.
.gif)
Selection Sort는 앞에서 부터 차례차례로 첫번째올 인덱스에 올 친구를 찾는 것이다. 결국 인덱스를 기준으로 그 인덱스 자리에 누가올 것인가를 나머지 인덱스에서 찾는것이다! 따라서 만약, 현재 찾는 인덱스가 3 이라고 치면 앞의 0,1,2 는 이미 올바른 친구들이 자리를 차지하고 있으므로 3번 인덱스 부터 끝까지 돌며 찾는 것이다!
시간 복잡도 : O(n^2)
Python 코드
1
2
3
4
5
6
7
def selection_sort(arr):
for i in range(len(arr) - 1):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
3. Insertion sort
삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘이다.
.gif)
시간 복잡도 : O(n^2)
Python 코드
1
2
3
4
5
def insertion_sort(arr):
for i in range(1,len(arr)):
for j in range(i,0,-1):
if arr[j-1] > arr[j]:
arr[j-1], arr[j] = arr[j], arr[j-1]
4. Counting sort
먼저 Counting Sort를 사용하는 경우는 데이터가 정수인 경우에만 사용할 수 있으며 **주로 **데이터 중복이 많은 경우에 사용한다.
사실 굉장히 빠른 정렬 알고리즘이지만 모든 데이터가 어떤 수 이하이다. 라고 할때 그리고 중복된 데이터가 많을 때 이 알고리즘을 사용하는 것이 좋다. 다른 정렬알고리즘과 다르게 Counting sort는 크기를 기준으로 정렬하는 알고리즘이다. 간단한 예시를 살펴보자.
arr 배열은 모든 값이 5 이하이다.
arr = [ 1, 2, 5, 1, 3, 4, 2, 2, 3, 5 ] 이러한 배열이 있다고 했을때. 문제의 조건의 5 이하이다 라는 조건과 같게 동일한 크기의 배열을 만들어준다. check = [0, 0, 0, 0, 0] 로 총 길이가 5인 배열을 만들어준다.
그리고 arr 배열을 0 인덱스 부터 시작해서 끝까지 탐색하는데, check의 index보다 하나 큰 값과 동일한 arr 데이터를 만났을때 check의 해당 index를 증가시켜주는 것이다.
arr = [ 1, 2, 5, 1, 3, 4, 2, 2, 3, 5]
check = [ 1, 0, 0, 0, 0]
arr = [ 1, 2, 5, 1, 3, 4, 2, 2, 3, 5]
check = [ 1, 1, 0, 0, 0]
처음 arr의 0 인덱스 자리에서 1을 만났으므로 check의 0인덱스 하나를 증가시킨다.
그리고 이번에는 arr 에서 2를 만났으니 check[1]을 증가시켜준다.
이 과정을 반복하게 되면, check = [ 2, 3, 2, 1,2] 가 될것이고, 이제 정렬은 (i+1) * check[ i ] 을 하면 끝이다!
시간 복잡도: O(n)
Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def Counting_Sort(A, B, k):
# A [1 .. n] 입력 배열
# B = [0]*len(a) 정렬된 배열
# C count list 카운트 배열
C = [0] * k
# 카운트 리스트에 각 숫자 발생 빈도를 C 리스트에 저장
for i in range(0, len(B)):
C[A[i]] += 1
# C 리스트에서 앞 인덱스 크기를 더해주기, 누적하여 인덱스 만들기
for i in range(1, len(C)):
C[i] += C[i-1]
print(C)
for i in A:
print(C[i]-1,end=' ')
B[C[i]-1] = i
C[i] -= 1
return B
a = [0, 4, 1, 3, 1, 2, 4, 1]
b = [0] * len(a)
k = max(a) + 1
print(Counting_Sort(a, b, 5))
5. Merge sort
병합 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬 알고리즘이다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.
배열을 반으로 쪼개고 또 쪼개기를 반복하다가, 더이상 쪼개질 수 없을때 두개씩 합치기를 시작한다. 그런데 합칠 때는 작은 숫자가 앞에 큰 숫자가 뒤에 위치를 시킨다. 그리고다시 4개를 합칠때도 작은 순으로 합친다. 반복..!
시간복잡도 : O(NlogN)
python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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
def merge_sort(arr):
def sort(low, high):
if high - low < 2:
return
mid = (low + high) // 2
sort(low, mid)
sort(mid, high)
merge(low, mid, high)
def merge(low, mid, high):
temp = []
l, h = low, mid
while l < mid and h < high:
if arr[l] < arr[h]:
temp.append(arr[l])
l += 1
else:
temp.append(arr[h])
h += 1
while l < mid:
temp.append(arr[l])
l += 1
while h < high:
temp.append(arr[h])
h += 1
for i in range(low, high):
arr[i] = temp[i - low]
return sort(0, len(arr))
6. Quick sort
Merge sort와 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.
.gif)
병합 정렬은 항상 정 가운데를 기준으로 분할하지만 퀵정렬은 피봇이라는 임의의 기준값을 사용한다. 퀵소트에서 중요한 것이 피봇(pivot) 이라는 개념인데, 이 pivot은 사용자가 정하기 나름이다. 그래서 이 피봇을 기준으로 큰 값, 작은 값인 그룹으로 각각 나눈다. 그래서 피봇을 기준으로 [3, 2, 1] < 4 < [7, 5, 6] 이렇게 정렬이 된다. 그리서 이제 피봇 4의 자리는 결국 fix 된 것이다. 이렇게 나눠진 두그룹도 정렬할기 위해서 그룹별로 피봇을 하나씩 정한다.
시간복잡도 : O(n^2)
Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quickSort(a, begin, end):
if begin < end:
p = partition(a, begin, end)
quickSort(a, begin, p-1)
quickSort(a, p+1, end)
def partition(a, begin, end):
pivot = (begin + end) // 2
L = begin
R = end
while L < R:
while a[L] < a[pivot] and L < R:
L += 1
while a[R] >= a[pivot] and L < R:
R -= 1
if L < R:
if L == pivot:
pivot = R
a[L], a[R] = a[R], a[L]
a[pivot], a[R] = a[R], a[pivot]
return R
a = [5, 4, 3, 2, 1]
quickSort(a, 0, 4)
print(a)
7. Python sorted
Python에서도 정렬 메소드를 제공한다. 사실 코딩문제를 풀어보면서 python의 sorted 혹은 sort 함수가 시간복잡도가 크지 않을까라고 생각했지만.. 역시 Python이다. 시간복잡도는 최악은 O(nlogn) 최고는 O(n) 으로 굉장히 빠른 편이다. 그리고 Python에서 제공하는 정렬메소드는 Merge sort 와 Insertion sort를 합친 알고리즘이라고 한다.
사용방법은 아래의 링크를 참고하면 된다.