[CS공부] 6. 정렬 알고리즘(1)

깃허브 정리본

용어

sorting(정렬): 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
-> ascending(오름차순) / descending(내림차순)

'안정적인' 정렬 알고리즘: 값이 같은 원소의 순서가 정렬 후에도 유지되는 알고리즘

internal sorting(내부정렬): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 정렬 알고리즘
external sorting(외부정렬): 정렬할 데이터가 많아 하나의 배열에 저장할 수 없는 정렬 알고리즘

bubble sorting(버블정렬)=단순교환정렬: 이웃한 두원소의 대소관계를 비교하며 교환을 반복하는 알고리즘
-> 안정적인 정렬 알고리즘, 복잡도 O(n^2)

straight selection sorting(단순선택정렬): 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하는 알고리즘
-> 불안정적인 정렬 알고리즘, 복잡도 O(n^2)

straight insertion sorting(단순삽입정렬): 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
-> 안정적인 정렬 알고리즘, 복잡도 O(n^2)

실습

버블 정렬

"""
기본 개념: 바로 옆 원소와 계속 비교하며 scan
개선 1. 원소 교환횟수가 0이면 정렬을 마친것으로 보고 종료
개선 2. 각 패스에서 비교/교환을 하다가 특정한 원소 이후부터 교환하지 않는다면,
        그 원소보다 앞쪽에 있는 원소들은 정렬을 마친 것으로 간주함.
        이후 패스에서는 스캔범위를 좁혀 진행
"""
def bubble_sorted(lst: list) -> list:
    n = len(lst)
    i = 0
    num = 1
    while i < n-1:
        exchanging = 0
        last = n-1
        print(f"{num}번 패스")
        for j in range(n-1, i, -1):
            for k in range(n-1):
                print(f"{lst[k]:2}{'    ' if k != j-1 else ' -- ' if lst[j-1] < lst[j] else ' <> '}", end='')
            print(f'{lst[n-1]:2}')
            if lst[j-1] > lst[j]: 
                lst[j-1], lst[j] = lst[j], lst[j-1]
                exchanging += 1
                last = j
        for k in range(n-1):
            print(f"{lst[k]:2}", end="    ")
        print(f"{lst[n-1]:2}")
        if not exchanging: break
        i = last
        num += 1

lst_1 = [1, 3, 9, 4, 7, 8, 6]

bubble_sorted(lst_1)


# 실행결과 ==========================================
1번 패스
 1     3     9     4     7     8 <>  6
 1     3     9     4     7 <>  6     8
 1     3     9     4 --  6     7     8
 1     3     9 <>  4     6     7     8
 1     3 --  4     9     6     7     8
 1 --  3     4     9     6     7     8
 1     3     4     9     6     7     8
2번 패스
 1     3     4     9     6     7 --  8
 1     3     4     9     6 --  7     8
 1     3     4     9 <>  6     7     8
 1     3     4     6     9     7     8
3번 패스
 1     3     4     6     9     7 --  8
 1     3     4     6     9 <>  7     8
 1     3     4     6     7     9     8
4번 패스
 1     3     4     6     7     9 <>  8
 1     3     4     6     7     8     9

단순 선택 정렬

"""
기본 개념: i번째 원소 ~ n번째 원소까지를 스캔해 가장 작은 원소를 맨앞으로 이동시킴
"""
def straight_selection_sorted(lst: list) -> list:
    n = len(lst)
    for i in range(n-1):
        m = i
        for j in range(i + 1, n):
            if lst[m] > lst[j]: m = j
        lst[i], lst[m] = lst[m], lst[i]
    return lst

lst_1 = [1, 3, 9, 4, 7, 8, 6]

print(straight_selection_sorted(lst_1))


# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9]

단순 삽입 정렬

"""
기본 개념: 카드를 정리하듯 주목한 원소를 알맞은 위치에 삽입
"""
def straight_insertion_sortied(lst: list) -> list:
    n = len(lst)
    for i in range(1, n):
        temp = lst[i]
        for j in range(i-1, -1, -1):
            if lst[j] > temp: 
                lst[j+1] = lst[j]
            else:
                lst[j+1] = temp
                break
        print(lst)
    return lst

lst_1 = [1, 3, 9, 4, 7, 8, 6]

print(straight_insertion_sortied(lst_1))


# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9]

정리

복잡도가 n^2인 정렬 알고리즘을 먼저 정리했다.

모두 간단한 아이디어의 정렬이어서
구현에 크게 어렵지는 않았다.

특히 버블 정렬에서 알고리즘을 개선하는 과정은
생각해보지 못한 아이디어가 있어 흥미로웠다.

다음 정리에서는 복잡도를 nlogn까지 낮춘
나머지 정렬 알고리즘을 정리해봐야겠다.