정렬 알고리즘과 시간복잡도

동일한 Big O를 가진 알고리즘이지만 실제 퍼포먼스는 다른 알고리즘들이 있다. 그 예가 바로 정렬 알고리즘이다.

오늘은 정렬 알고리즘은 Bubble Sort, Selection Sort, Insert Sort를 정리해보려 한다.

Bubble Sort

Bubble Sort는 정렬 알고리즘 중 가장 단순한 알고리즘이다.

배열의 2개의 아이템을 선택하고 왼쪽이 오른쪽보다 크면 교환하고 크지 않으면 오른쪽으로 이동하면서 사이클이 끝날 때 가장 큰 아이템은 배열의 마지막 위치에 배치된다. 다음 사이클은 아이템을 비교, 교환하는 과정을 거친 후 정렬된 배열 이전 위치에 가장 큰 아이템을 배치한다.

사이클마다 비교, 교환 과정을 반복하는 것이 버블 정렬이다.

위 이미지를 보면 18보다 32의 크기가 더 크기 때문에 교환하지 않고 오른쪽으로 넘어간 후 다시 -11과 32를 비교해서 32와 -11을 교환해줬다.

한 사이클이 끝나면 크기가 큰 아이템이 배열의 끝에 정렬된다.

def bubble_sort(arr):
    global cnt
    cnt = 0
    for j in range(len(arr)-1):
        cnt+=1
        swap_cnt = 0
        for i in range(len(arr)-j-1):
            if arr[i] > arr[i+1]:
                swap_cnt+=1
                print(f'swap [{swap_cnt}] : {arr[i]} <-> {arr[i+1]}')
                arr[i], arr[i+1] = arr[i+1], arr[i]                

        print(f"STEP [{cnt}] : {arr}")
        print('='*40)
    return arr



arr = [18, 32, -11, 6, 68, 2, -34]
print(f"arr : {arr}")
print('='*40)
bubble_sort(arr)

arr : [18, 32, -11, 6, 68, 2, -34]
========================================
swap [1] : 32 <-> -11
swap [2] : 32 <-> 6
swap [3] : 68 <-> 2
swap [4] : 68 <-> -34
STEP [1] : [18, -11, 6, 32, 2, -34, 68]
========================================
swap [1] : 18 <-> -11
swap [2] : 18 <-> 6
swap [3] : 32 <-> 2
swap [4] : 32 <-> -34
STEP [2] : [-11, 6, 18, 2, -34, 32, 68]
========================================
swap [1] : 18 <-> 2
swap [2] : 18 <-> -34
STEP [3] : [-11, 6, 2, -34, 18, 32, 68]
========================================
swap [1] : 6 <-> 2
swap [2] : 6 <-> -34
STEP [4] : [-11, 2, -34, 6, 18, 32, 68]
========================================
swap [1] : 2 <-> -34
STEP [5] : [-11, -34, 2, 6, 18, 32, 68]
========================================
swap [1] : -11 <-> -34
STEP [6] : [-34, -11, 2, 6, 18, 32, 68]
========================================
[-34, -11, 2, 6, 18, 32, 68]

버블 정렬은 배열의 n-1의 아이템을 비교해야 한다. step 1에서는 n-1 아이템을 비교하고 step 2 에서는 n-2를 비교 이런 식으로 아이템 비교와 교환 과정이 반복된다.

최악의 경우 모든 step마다 모든 아이템을 교환하는 경우도 발생한다. 따라서 버블 정렬의 시간복잡도는 $O(n^2)$ 이다.

Selection Sort

선택정렬은 전체 아이템 중 가장 작은 아이템의 위치를 변수에 저장한 후 사이클이 끝날 때 가장 작은 원소와 배열의 첫 번째 아이템과 교환한다. 그다음 사이클은 정렬된 아이템 이후의 위치부터 사이클을 시작하고 같은 과정을 반복해준다.

def selection_sort(arr):
    global cnt
    cnt = 0
    for i in range(len(arr)-1):
        cnt+=1
        idx = i
        for j in range(i,len(arr)):
            if arr[idx] > arr[j]:
                idx = j
        
        if i != idx:        
            print(f"swap[{cnt}] : {arr[i]} <-> {arr[idx]}")
            arr[i], arr[idx] = arr[idx], arr[i]
            
        print(f"STEP[{cnt}] : {arr}")
        print('='*40)
        
    return arr



arr = [18, 32, -11, 6, 68, 2, -34]
print(f"arr : {arr}")
print('='*40)
selection_sort(arr)

arr : [18, 32, -11, 6, 68, 2, -34]
========================================
swap[1] : 18 <-> -34
STEP[1] : [-34, 32, -11, 6, 68, 2, 18]
========================================
swap[2] : 32 <-> -11
STEP[2] : [-34, -11, 32, 6, 68, 2, 18]
========================================
swap[3] : 32 <-> 2
STEP[3] : [-34, -11, 2, 6, 68, 32, 18]
========================================
STEP[4] : [-34, -11, 2, 6, 68, 32, 18]
========================================
swap[5] : 68 <-> 18
STEP[5] : [-34, -11, 2, 6, 18, 32, 68]
========================================
STEP[6] : [-34, -11, 2, 6, 18, 32, 68]
========================================
[-34, -11, 2, 6, 18, 32, 68]

버블 정렬과 유사하게, 아이템 비교 교환이 이루어지지만, 사이클마다 1번의 교환만 이루어지므로 버블 정렬보다 훨씬 효율적이다.

버블정렬과 다르게 최악의 상황에도 사이클마다 모든 아이템을 교환해야 하는 경우도 없다!!

하지만 선택정렬의 시간복잡도 또한, 버블정렬과 동일한 $O(n^2)$ 이다.

insertion Sort

삽입정렬은 인덱스 1번에서 시작한다. 왼쪽에 있는 아이템이 더 작은 경우에 교환이 이루어진다. 다음 사이클은 인덱스 2번 아이템부터 시작하고 왼쪽에 더 큰 아이템이 존재하는 경우에는 교환이 이루어지지만, 작은 아이템이 존재한다면 다음 루프로 넘어간다.

def insert_sort(arr):
    global cnt
    cnt = 0
    for i in range(1,len(arr)):
        swap_cnt = 0
        cnt+=1
        idx = i
        for j in range(i-1, -1,-1):
            if arr[j] > arr[idx]:
                swap_cnt+=1
                arr[idx] , arr[j] = arr[j], arr[idx]
                print(f"swap[{swap_cnt}] : {arr[j]} <-> {arr[idx]}")
                idx = j
            else:
                continue

        print(f"STEP[{cnt}] : {arr}")
        print('='*40)
            
    
    return arr


arr = [18, 32, -11, 6, 68, 2, -34]
print(f"arr : {arr}")
print('='*40)
insert_sort(arr)

arr : [18, 32, -11, 6, 68, 2, -34]
========================================
STEP[1] : [18, 32, -11, 6, 68, 2, -34]
========================================
swap[1] : -11 <-> 32
swap[2] : -11 <-> 18
STEP[2] : [-11, 18, 32, 6, 68, 2, -34]
========================================
swap[1] : 6 <-> 32
swap[2] : 6 <-> 18
STEP[3] : [-11, 6, 18, 32, 68, 2, -34]
========================================
STEP[4] : [-11, 6, 18, 32, 68, 2, -34]
========================================
swap[1] : 2 <-> 68
swap[2] : 2 <-> 32
swap[3] : 2 <-> 18
swap[4] : 2 <-> 6
STEP[5] : [-11, 2, 6, 18, 32, 68, -34]
========================================
swap[1] : -34 <-> 68
swap[2] : -34 <-> 32
swap[3] : -34 <-> 18
swap[4] : -34 <-> 6
swap[5] : -34 <-> 2
swap[6] : -34 <-> -11
STEP[6] : [-34, -11, 2, 6, 18, 32, 68]
========================================
[-34, -11, 2, 6, 18, 32, 68]

선택정렬에서는 사이클마다 전체 아이템을 비교하면서 가장 작은 아이템의 인덱스 위치를 찾았다면 삽입정렬에서는 왼쪽에 큰 아이템이 존재할 때만 비교가 이루어지므로 선택정렬보다 효율적이다!

하지만 여전히 시간복잡도는 동일하게 $O(n^2)$ 이다.

알고리즘마다 다른 퍼포먼스를 보이지만 시간복잡도로 표현하면 모두 동일한 퍼포먼스를 보여준다.

이런 경우에는 최악의 시나리오가 아닌 평균 시나리오로 시간복잡도를 살펴봐야 한다.

대부분의 경우 최고/최악의 시나리오는 자주 발생하지 않으며, 높은 확률로 평균에 속한다.

이렇게 동일한 시간복잡도를 갖고 있다고 하더라도, 상황에 따라 매우 다른 퍼포먼스를 보여줄 수 있다.

결론

언제나 시간복잡도가 성능을 증명해주진 않는다. 다양한 시나리오를 생각한 후 알고리즘을 사용하자.

버블, 삽입, 선택 정렬 중에서는 평균적으로 삽입정렬의 퍼포먼스가 가장 좋다!!

---

Reference

• Best, Average, Worst 시간복잡도 : Summary of 5 types of sorting in programming
• Bubble-Selection-Insertion Sort: SW TEST ACADEMY
• 알고리즘 & 데이터 구조 : 노마드 코더 Nomad Coders