정렬 알고리즘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

태그:

카테고리:

업데이트: