[자료구조/알고리즘] 버블 정렬, 선택 정렬, 시간 복잡도 관련 주의점

배열의 정렬 방법에는 여러 가지가 있다. 대부분의 프로그래밍 언어들은 가장 빠른 시간 복잡도인 O(n*logn)을 자랑하는 퀵정렬을 배열의 정렬 알고리즘으로 채택하여 사용하고 있다고 한다. 이 글에서는 보다 느리고 효율은 떨어지지만 기본적이고 쉬운, 버블 정렬과 선택 정렬에 대해 알아보자.

1) 버블 정렬

버블 정렬은 마치 가장 큰 숫자가 버블이 되어 차례로 맨 뒤로 이동하는 정렬 방법이다. 아래의 방법을 따라 정렬이 이루어진다.

 

① 0번째 원소와 1번째 원소를 비교, 순서대로 정렬한다. 그 다음 1번째 원소와 2번째 원소를 비교, 정렬한다. 이를 n-1번째 원소와 n번째 원소까지 반복하고 나면, 배열에서 가장 큰 원소(버블)가 배열의 맨 뒤로 이동한 상태가 되고 하나의 사이클이 종료된다. 

② 다시 ①의 과정을 반복하되, n-2번째 원소와 n-1번째 원소를 비교 정렬하는 것을 마지막으로 사이클을 종료한다. 배열에서 두 번째로 큰 원소가 n-1번째에 위치하게 된다.

③ 정렬이 완료될 때까지 이를 반복한다.

 

이를 코드화하면 아래와 같다.

def bubble_sort(list):
    m = len(list)
    while m != 0:
        m-=1
        for n in range(m):
            if list[n] > list[n+1]:
                list[n], list[n+1] = list[n+1], list[n]
    return list
    
bubble_sort([3,5,6,9,1])

이중 for문과 같으므로, 버블 정렬의 시간 복잡도는 O(N^2)이다.

 

2) 선택 정렬

선택 정렬은 버블 정렬과 반대의 느낌으로, 가장 작은 원소부터 맨 앞에 위치시키는 것을 반복하는 방법을 따른다. 아래의 과정으로 이루어진다.

 

① 0번째의 index를 시작 값으로 정한 뒤, 해당 위치의 원소와 1,2,3,...번째 index의 원소를 차례로 비교하며, 더 작은 원소를 만날 때마다 해당 위치의 index를 기억한다. 이를 n번째 원소까지 진행하고 나면 가장 작은 원소의 index 위치(tmp)를 담고 있어야 한다. 

② 0번째 원소와 tmp번째 원소를 교환한다. 이제 가장 작은 원소가 0번째에 위치하고 있다.

③ 1번째의 index를 시작 값으로 정한 뒤, 2,3,4....번째 index의 원소에 대해 ①, ②를 반복한다.

④ 정렬이 완료될 때까지 위 과정을 반복한다.

 

이를 코드화하면 아래와 같다.

def selection_sort(list):
    m = len(list)
    i=-1
    while i != m-1:
        i+=1
        tmp = i
        for n in range(i+1,m):
            if list[tmp] > list[n]:
                tmp = n
        list[i], list[tmp] = list[tmp], list[i]
    return list
    
selection_sort([3,5,6,9,1])

선택 정렬의 시간복잡도는 O(N^2/2) = O(N^2)이다.

 

같은 시간 복잡도를 갖는 버블 정렬과 선택 정렬?

시간 복잡도 상으로는 버블 정렬과 선택 정렬이 모두 같은 빅오표기법인 O(N^2)을 갖는 것으로 표현된다. 다만 좀 더 자세히 살펴보면, 버블 정렬의 경우 모든 원소에 대해 비교 후 교환이 일어날 수 있는 반면 선택 정렬은 비교만 한 뒤 교환을 하지 않고 index를 저장해두었다가 매 사이클마다 1번씩의 교환만을 하기 때문에 연산량이 버블 정렬에 비해 절반 수준이다. 즉, 같은 O(N^2)의 시간 복잡도이지만 선택 정렬이 2배 더 빠르다.

 

여기서 기억해야 할 것은, 보다 효율적인 알고리즘을 짜는 데 있어 빅오표기법의 시간 복잡도를 따져보는 것은 필수적이지만, 빅오를 기준으로 같은 분류에 속하더라도 최적화를 하기 위해서는 보다 심도 있는 분석이 필요할 수 있다는 점이다. 그 분석에는 알고리즘의 내부 과정을 포함해, 데이터의 분포상 '최선의 경우 / 평균적인 경우 / 최악의 경우' 중 어떤 경우에 중점을 두어야 하는지, 자주 사용하는 연산이 어떤 것인지 등등이 모두 포함되어야 할 것이다.