[자료구조] 정렬 2. 간단한 정렬들

앞서 정렬의 개념에 대해 간략하게 설명했다. 이제 매우 간단한, 그러나 비효율적인 정렬을 쉽게 알아본다.

---

1) 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법을 반복하여 정렬하는 방식이다.
전체 숫자 리스트를 아직 정렬되지 않은 오른쪽 리스트와 정렬이 완료된 왼쪽 리스트로 분류하는데, 맨 처음에는 모든 숫자가 오른쪽 리스트(정렬되지 않은 상태)에 담겨져 있다.
즉 오른쪽 리스트에서 가장 작은 숫자들을 계속해서 선택하여 왼쪽 리스트에 차례로 담는 방식을 반복하여 정렬하는 것이다!

def printStep(arr, val):
    print(" Step %2d = " % val, end='')
    print(arr)

def selection_sort(A):
    n = len(A)
    for i in range(n-1): # 마지막 꺼는 앞에꺼 하면서 자동으로 정렬될 꺼니가 n-1개 까지.
        least = i
        for j in range(i+1, n):
            if A[least] > A[j]:
                least = j

        A[i], A[least] = A[least], A[i]
        printStep(A, i+1)

    return A

코드를 보면… 시간복잡도가 항상 O(n^2)이라 그닥 효율적이지도 않고 안정성을 만족하지도 않는다.
그냥 구현이 쉽고 간단하다는 장점 원툴인 정렬이라… 사용을 추천하지는 않는다.

 

2) 삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬이 안 된 오른쪽 리스트의 숫자들을 순서대로 정렬이 완료된 왼쪽 리스트에서 알맞은 자리에 찾아 넣는 방식이다. 손에 든 카드를 순서대로 정렬하는 방식과 유사하다.

def printStep(arr, val):
    print(" Step %2d = " % val, end='')
    print(arr)

def insertion_sort(A):
    n = len(A)
    for i in range(1, n):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
        printStep(A, i)
    return A

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)이다. 그러나 최선의 경우(이미 정렬된 경우)에는 O(n)으로 굉장히 빠른 성능을 보여준다.
그러나 이미 정렬된 리스트를 또 왜 정렬 하겠는가…? 사실상 삽입 정렬의 시간 복잡도 역시 O(n^2)라고 봐도 무방하다. 물론 비교적 정렬이 되어 있는 리스트를 정렬하는 경우에는 효율적이라고 볼 수 있다.

 

3) 버블 정렬 (Bubble Sort)

버블 정렬은 리스트의 요소를 순서대로 돌면서, 인접한 2개의 레코드를 비교하여 크기의 순서가 맞지 않으면 서로 교환하는 방법을 반복하여 정렬한다.

def printStep(arr, val):
    print(" Step %2d = " % val, end='')
    print(arr)

def bubble_sort(A):
    n = len(A)
    for i in range(n-1, 0, -1): # j의 범위가 n-1, n-2, ... 이 될 수 있게 설정한다. 인덱스 0은 포함 안해도 됨.
        bChanged = False
        for j in range(i):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                bChanged = True

        if not bChanged: # 정렬이 이미 돼있으면 반복문을 빠져나온다
            break
        
        printStep(A, n-i)
    return A

버블 정렬 역시 시간 복잡도는 O(n^2)이다. 삽입 정렬과 같이 이미 정렬이 되어 있는 경우에는 별도의 정렬 과정 없이 바로 알고리즘이 종료되지만… 정렬되어 있는 리스트를 굳이 정렬할 필요는 없을 테니까… 그닥 효율적이라고 볼 수 없다.

---

정리

이번 시간에는 매우 간단한 정렬이라고 알려진 3개의 정렬 – 선택정렬, 삽입정렬, 버블정렬 – 을 공부했다.
공부하면서 알 수 있었 듯 세 정렬 모두 굉장히 비효율적인 시간 복잡도를 가지고 있었다. 간단한 대신 매우 비효율적이다… 세상에 공짜는 없다는 기회비용의 개념이 떠오른다…
물론 합병 정렬이나 퀵 정렬 등 비교적 복잡하지만 효율적인 알고리즘들이 더 있다! 그러나 그것은 추후 알고리즘을 공부할 때 서술하도록 하겠다…

 

 

작성일자: 2023-03-11