버블 / 선택 / 삽입 정렬

오늘 살펴볼 알고리즘은 정렬 알고리즘의 가장 대표적인 예시들인 버블 / 선택 / 삽입 정렬 알고리즘이다.

알고리즘 자체는 크게 어렵지 않지만 정보처리기사 시험에서도 가끔 출제되고 비슷하게 동작하여 개념들이 약간 헷갈리기 때문에 잘 기억해두면 좋을 듯하다. 글에서 설명하는 정렬은 모두 오름차순을 기준으로 정렬하는 것을 말한다.

---

버블정렬

우선 버블 정렬이다. 거품이 터지는 모양이 생각난다하여 이름 지어졌다 한다. 간단하게 말해서 큰 수를 먼저 뒤로 보내는 방식으로 정렬하는 것을 말한다. 이를 위해 앞뒤로 값을 비교하여 자리를 바꿔주는 작업을 수행해야 한다. 실제 과정을 살펴보자.

1. [1, 5, 3, 4, 2]
    ^  ^
    
2. [1, 5, 3, 4, 2]
       ^  ^       swap
       
3. [1, 3, 5, 4, 2]
          ^  ^    swap
          
4. [1, 3, 4, 5, 2]
             ^  ^ swap
             
5. [1, 3, 4, 2, 5]

정렬되지 않은 리스트 [1, 5, 3, 4, 2]를 정렬하는 과정이다. 첫 번째 원소를 시작으로 바로 다음 원소와 비교하여 만약 뒤에오는 원소가 더 작을 경우 swap 한다. 해당 과정이 완료되면 리스트에서 가장 큰 원소가 리스트의 끝에 위치한 것을 확인할 수 있다. 나머지를 과정을 모두 진행하면 이러한 순서로 결과를 확인할 수 있을 것이다.

 

unordered => [1, 5, 3, 4, 2]

1. [1, 3, 4, 2, 5]
                *

2. [1, 3, 2, 4, 5]
             *  *

3. [1, 2, 3, 4, 5]
          *  *  *
          
4. [1, 2, 3, 4, 5]
       *  *  *  *  

result => [1, 2, 3, 4, 5]

버블정렬의 경우 공간 복잡도는 O(N)을 가진다. 시간 복잡도의 경우 한 번의 루프를 위해 O(N)이 소요되고 이를 전체 요소에 반복하므로 O(N)을 또 소모하여 총 O(N^2)의 시간 복잡도를 가지게 된다. 다만, swap이 일어나는 횟수를 체크하여 전체 반복 전 정렬이 다 끝난 경우 일찍 종료시킬 수도 있다.

 

이를 코드로 구현하면 이러하다.

def bubble_sort(array):
    length = len(array)
    
    for i in range(length - 1, 0, -1):
        for j in range(i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

array = [1, 5, 3, 4, 2]

bubble_sort(array)
print(array)

이상으로 버블정렬을 살펴보았다.

---

선택정렬

다음으로 선택정렬을 살펴보겠다. 선택 정렬은 주어진 리스트를 순회하며 최솟값을 찾아 맨 앞에 위치한 값과 swap 하는 것을 통해 정렬하는 방식이다. 첫 순회 이후, 맨 앞 위치를 뺀 나머지 리스트를 순회하는 방식으로 반복하여 정렬한다. 실제 과정을 간단하게 살펴보면 이러하다.

1. [1, 5, 4, 3, 2]
    ^
    
2. [1, 5, 4, 3, 2]
    *  ^        ^ swap
       
3. [1, 2, 4, 3, 5]
    *  *  ^  ^    swap     
          
4. [1, 2, 3, 4, 5]
    *  *  *  ^  
             
5. [1, 2, 3, 4, 5]
    *  *  *  *  ^

리스트의 첫 번째 요소를 제외한 나머지 전체를 순회하여 가장 작은 값을 찾는다. 찾은 값을 리스트의 첫 번째 요소와 비교하여 더 작은 값을 갖는 경우 swap 한다. 이제 가리키고 있는 지점을 한 칸 뒤로 옮겨 두 번째 요소를 기준으로 한 뒤 같은 과정을 반복한다. 즉, 리스트에서 가장 작은 값을 찾아가며 하나 씩 순서대로 정렬하는 것이다.

 

선택정렬의 공간 복잡도는 O(N)이다. 시간 복잡도의 경우 전체 리스트를 반복 순회하며 진행하기 때문에 O(N^2)이 된다.

 

코드로 구현하면 이러하다.

array = [1, 5, 4, 3, 2]

for i in range(len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)

이상으로 선택정렬을 살펴보았다.

---

삽입정렬

마지막으로 삽입정렬을 확인해보자. 삽입정렬은 리스트의 요소를 이미 정렬된 부분과 비교하여 위치를 찾아 삽입하는 정렬이다. 간단한 예시를 보자.

1. [1, 5, 4, 2, 3]
       ^
    
2. [1, 5, 4, 2, 3]
       *  ^      
       
3. [1, 4, 5, 2, 3]
       *     ^
       
4. [1, 2, 4, 5, 3]
          *     ^  
             
5. [1, 2, 3, 4, 5]

첫 번째 요소 하나로는 비교할 대상이 없기 때문에 두 번째 요소부터 비교를 시작한다. '^'은 현재 선택된 요소, '*'은 해당 요소가 들어갈 위치를 의미한다. 직관적인 이해가 다소 어려우므로 상황을 하나씩 설명하겠다.

1번 상황의 경우, '5'는 바로 앞 요소인 '1'보다 크기 때문에 제자리에 위치한다.

2번 상황의 경우, '4'는 바로 앞 요소인 '5'보다 작기 때문에 swap 한다. 이동한 후 앞에 위치한 '1'보단 크기 때문에 swap 하지 않는다.

3번 상황의 경우, '2'는 바로 앞 요소인 '5'보다 작기 때문에 swap 한다. 이동한 후 앞에 위치한 '4'보다 작기 때문에 한 번 더 swap 한다. 그다음 '1'보단 크기 때문에 swap 하지 않는다.

4번 상황의 경우, '3'은 바로 앞 요소인 '5'보다 작기 때문에 swap 한다. 이동한 후 앞에 위치한 '4'보다 작기 때문에 한 번 더 swap 한다. 그 다음 '2'보단 크기 때문에 swap 하지 않는다.

결과적으로 5번 상황 처럼 정렬되게 된다.

 

해당 과정을 살펴보면 현재 선택된 요소 이전까지의 값들은 정렬된 형태임을 확인할 수 있다. 즉, 정렬된 배열 안의 요소들과 비교하여 해당 요소가 들어갈 자리를 찾는 것이다.

 

삽입정렬의 공간 복잡도는 O(N)이며, 시간 복잡도의 경우 O(N^2)이지만 이미 정렬된 경우엔 O(N)의 시간 복잡도를 갖게 된다.

 

코드로 구현하면 이러하다.

array = [1, 5, 4, 2, 3]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break

print(array)

이상으로 삽입정렬을 살펴보았다.

---

사실 아직까지 코딩테스트에 앞서 말한 세 가지 정렬이 출제되는 것은 보지 못했다. 시간 복잡도가 좋지 않기 때문이다. 하지만 정보처리기사 시험에 자주 출제되며 정렬 알고리즘의 기본적인 내용들이므로, 어떤 개념인지는 알고 있는 게 좋을듯하다. 다음 글로는 합병정렬과 퀵정렬을 작성해볼까 생각한다. 이상 글을 마치겠다.