[TIL] Algorithm - 정렬

⏰ 2023.04.08 ⏰

1. Sorting 

key 를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
데이터를 교환, 선택, 삽입하면서 정렬을 완료한다.

 

★ 정렬 알고리즘의 안전성 ★

값이 같은 원소의 순서는 정렬한 후에도 유지되면 안정적인 정렬 알고리즘이다.

안정적인 정렬 알고리즘	버블 정렬, 삽입 정렬, 병합 정렬, 도수 정렬(계수 정렬)
안정적이지 않는 정렬 알고리즘	선택 정렬, 퀵 정렬, 힙 정렬,

---

2. 버블 정렬(bubble sort)

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘 ( = 단순 교환 정렬 )
시간복잡도 O(n^2)

1. 기본 구현

# 기본 버블 정렬
def bubble_sort(list) :
    n = len(list)
    # 모든 정렬이 끝나기 위해서는 n-1번 수행되어야한다.
    # 패스를 한번 수행하면 자동적으로 앞의 한개는 정렬된다.
    for i in range(n-1) :
        # 패스(비교, 교환) 수행
        # 뒤의 원소부터 2개를 비교한다.
        # 패스가 수행될 때마다 앞에 정렬된 값이 쌓이므로 n-1 부터 i+1까지만 수행한다. 
        for j in range(n-1, i, -1) :
            if list[j-1] > list[j] :
                list[j-1], list[j] = list[j], list[j-1]

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :    
    nums = [5, 4, 3, 2, 1]       
    bubble_sort(nums)
    for i in nums:
        print(i, end=' ')

2. 교환 횟수에 따른 중단을 구현한 버블 정렬 

# 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이므로 
# 그 이후의 패스는 불필요하다고 판단하여 정렬 중단
def bubble_sort(list) :
    n = len(list)
    for i in range(n-1) :
        # 패스를 수행할 때 교환을 실행한 횟수
        exchange = 0
        for j in range(n-1, i, -1) :
            if list[j-1] > list[j] :
                list[j-1], list[j] = list[j], list[j-1]
                exchange += 1
        if exchange == 0 :
            break

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :    
    nums = [5, 4, 3, 2, 1]       
    bubble_sort(nums)
    for i in nums:
        print(i, end=' ')

3. 교환 수행지점을 통한 범위 제한을 구현한 버블 정렬

# 어떤 특정한 원소 이후 교환하지 않는다면
# 그 원소보다 앞쪽에 있는 원소들을 정렬되어 있는 상태이다.
# 즉, 정렬된 부분을 넘기도록 범위를 제한해준다.
def bubble_sort(list) :
    n = len(list)
    
    # 앞에 이미 정렬되어 있는 원소의 수
    k = 0
    while k < n-1 :
        # 마지막으로 교환을 수행한 인덱스를 저장할 변수
        last = n-1
        for i in range(n-1, k, -1) :
            if list[i-1] > list[i] :
                list[i-1], list[i] = list[i], list[i-1]
                last = i
        k = last
    

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :    
    nums = [5, 4, 3, 2, 1]       
    bubble_sort(nums)
    for i in nums:
        print(i, end=' ')

---

3. 삽입 정렬(insertion sort)

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
시간복잡도 O(n^2)

# 단순 삽입 정렬
def insert_sort(list) :
    n = len(list)
    
    for i in range(1, n) :
        # 현재 주목하고 있는 원소의 위치 i
        j = i
        
        # 정렬된 배열의 왼쪽 끝에 도달하지 않은 경우 : j > 0
        # list[j]의 값이 list[j-1]의 값보다 작은 경우 : 왼쪽의 값이 더 큰 경우
        # 패스가 반복된다.
        while j > 0 and list[j-1] > list[j] :
            list[j-1], list[j] = list[j], list[j-1]
            j -= 1    

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :    
    nums = [5, 4, 3, 2, 1]       
    insert_sort(nums)
    for i in nums:
        print(i, end=' ')

 

---

기본적으로 배운 개념들이라 어제, 오늘은 주어진 백준 문제 풀이에 시간을 많이 할애했다.
우선 문제를 풀고 주위의 모르는 동료분들의 질문에 대답을 해주면서 머릿속 복잡한 문제 풀이 정리에 도움이 되었다.

이미 배운 내용이었지만 그 중 정렬은 늘 중요하다고 들었다. 
그래서 이번 기회에 정리를 다시 해보려고 한다.
개념에 대한 설명보다는 한번씩 구현을 하며 주석을 추가하는 방식으로 알고리즘을 익혀야겠다.

 

▶ git 원격 저장소 이름 알아보기

git remote

▶ git clone을 통해 저장소를 복제했을 경우에는 push

git push 원격저장소명 브랜치명

 

구현 코드 github 저장소
https://github.com/ChoSooBeen/PythonWorkspace/tree/main/SortExample

GitHub - ChoSooBeen/PythonWorkspace