[Python]정렬 알고리즘
정렬 알고리즘Permalink
버블 정렬(단순 교환 정렬)Permalink
- 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
- 패스 : 이웃한 원소를 비교하고, 필요하면 교환하는 과정
- 배열의 크기가 n일때, 첫번째 패스 과정에서의 비교 횟수는 n-1번이다.
- 한번의 패스 과정이 끝나면, 정렬해야 하는 원소의 갯수는 n-2개이다.
- 모든 정렬이 끝나려면 패스를 n-1번 수행해야 한다.
구현Permalink
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(n-1):
exchange = 0
for j in range(n-i-1):
if a[j] > a[j+1]:
a[j],a[j+1] = a[j+1],a[j]
exchange += 1
if exchange == 0:
break
1
2
3
4
5
print('버블 정렬')
sort = bubble_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
버블 정렬
[1, 3, 4, 6, 7, 8, 9]
단순 선택 정렬Permalink
- 가장 작은 원소부터 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘
- 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고, 정렬하지 않은 부분의 맨 앞 원소와 교환
구현Permalink
1
2
3
4
5
6
7
8
9
10
from typing import MutableSequence
def selection_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(n-1):
min = i
for j in range(i,n-1):
if a[j] < a[min]:
min = j
a[i],a[min] = a[min],a[i]
1
2
3
4
5
print('단순 선택 정렬')
sort = selection_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
단순 선택 정렬
[1, 3, 4, 6, 7, 9, 8]
단순 삽입 정렬Permalink
- 두번째 원소부터 주목하여 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
from typing import MutableSequence
def insertion_sort(a:MutableSequence) -> None:
n = len(a)
for i in range(1,n):
tmp = a[i]
j = i
while j > 0 and a[j - 1] > tmp:
a[j] = a[j-1]
j -= 1
a[j] = tmp
1
2
3
4
5
print('단순 삽입 정렬')
sort = insertion_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
단순 삽입 정렬
[1, 3, 4, 6, 7, 8, 9]
셸 정렬Permalink
- 배열의 원소를 그룹으로 나누어 각 그룹별로 정렬을 수행
- 그 후 정렬된 그룹을 합치는 작업을 반복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from typing import MutableSequence
def shell_sort(a : MutableSequence) -> None:
n = len(a)
h = n // 2
while h > 0:
for cur in range(h,n):
nex = cur - h
tmp = a[cur]
while nex >= 0 and a[nex] > tmp:
a[nex + h] = a[nex]
nex -= h
a[nex + h] = tmp
h //= 2
1
2
3
4
5
print('셸 정렬')
sort = shell_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
셸 정렬
[1, 3, 4, 6, 7, 8, 9]
퀵 정렬Permalink
- 그룹에서 pivot을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료
- pivot: 그룹을 나누는 기준
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
from typing import MutableSequence
def partition(a:MutableSequence) -> None:
n = len(a)
pl = 0
pr = n - 1
pivot = a[n//2]
while pl < pr :
while a[pl] < pivot :
pl += 1
while a[pr] > pivot :
pr -= 1
if pl <= pr:
a[pl],a[pr] = a[pr],a[pl]
pl += 1
pr -= 1
print(f'pivot : {pivot}')
print(f'pivot 아래 그룹')
print(*a[0:pivot])
print(f'pivot과 일치하는 그룹')
print(*a[pr + 1: pl])
print(f'pivot 위의 그룹')
print(*a[pr + 1 : n])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def qsort(a: MutableSequence, left : int, right : int) -> None:
pl = left
pr = right
pivot = a[(left + right)// 2]
while pl <= pr:
while a[pl] < pivot :
pl += 1
while a[pr] > pivot :
pr -= 1
if pl <= pr :
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr : qsort(a,left,pr)
if pl < right : qsort(a,pl,right)
def quick_sort(a: MutableSequence) -> None:
left = 0
right = len(a) - 1
qsort(a,left,right)
1
2
3
4
5
print('퀵 정렬')
sort = quick_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
퀵 정렬
[1, 3, 4, 6, 7, 8, 9]
힙 정렬Permalink
- 힙: 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진 트리
- 힙에서 최대값인 루트를 꺼낸 뒤 나머지 부분을 힙으로 만든다
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
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
def down_heap(a: MutableSequence,left : int, right : int) -> None:
temp = a[left]
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1
cr = cl + 1
child = cr if cr <= right and a[cr] > a[cl] else cl
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
for i in range((n-1) // 2,-1,-1):
down_heap(a,i,n-1)
for i in range(n-1,0,-1):
a[0],a[i] = a[i],a[0]
down_heap(a,0,i-1)
1
2
3
4
5
print('힙 정렬')
sort = heap_sort
a = [6,4,3,7,1,9,8]
sort(a)
print(a)
1
2
힙 정렬
[1, 3, 4, 6, 7, 8, 9]
1