[알고리즘] 버블정렬과 삽입정렬

버블 정렬은 맨 왼쪽 원소부터 바로 이웃한 원소와 비교하면서 정렬하는 것이고, 삽입 정렬은 이미 정렬된 부분과 정렬할 부분을 나눠 정렬하는 것입니다. 알고리즘의 핵심인 정렬 중 버블 정렬과 삽입 정렬에 대해 알아보겠습니다.

 

1. 버블 정렬

개념

맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환하는 정렬입니다. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해 반복합니다.

 

 

예시) 5 3 1 4 2를 오름차순으로 정렬

 

버블 정렬 예시

 

 

특징

정확성을 보이기 제일 쉽습니다.

 

 

시간복잡도

처음 가장 큰 원소를 구할 때 n-1 번을 비교하고, 두번째 큰 원소를 비교할 때 n-2를 비교합니다. 이런식으로 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

 

 

코드

def bubblesort(L):
    result = list(L)
    for x in range(len(result) - 1):
        for y in range(len(result) -x - 1):
            if(result[y] > result[y+1]):
                result[y], result[y+1] = result[y+1], result[y]
    return result

A = list(range(5))
import random
random.shuffle(A)
print(A)
print(bubblesort(A))

 

 

 

2. 삽입 정렬

개념

정렬 대상이 될 원소를 두 부분으로 나눠 정렬합니다. 앞은 '이미 정렬된 부분', 뒤는 '정렬할 부분'으로 구분합니다. 매번 정렬할 부분의 가장 첫번째원소를 정렬이 된 부분에서 비교하고 알맞은 위치에 삽입합니다. 삽입은 정렬된 부분의 가장 큰 원소(가장 오른쪽 원소)부터 오른쪽으로 비교해나가면서 진행합니다.

 

 

예시) 5 3 1 4 2를 오름차순으로 정렬

 

삽입 정렬 예시

 

 

특징

삽입된 떄에 따라 시간 복잡도가 다릅니다. 이미 오름차순으로 정렬되어 있는 경우, 각 원소마다 한번씩만 비교하면 되므로 시간복잡도는 O(N)이지만, 역순으로 정렬된 최악의 경우엔 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(N^2)의 시간복잡도를 보입니다.

 

 

i+1번째 원소 추가 시 평균 시간복잡도

평균 시간복잡도

 

* 1등 확률과 2등 확률은 비교회수가 i번으로 같습니다. 1번까지 체크를 해야 2등인지 알 수 있고, 1등인지 알 수 있기 때문입니다.

 

따라서 i+1번째 원소를 추가할 때 평균적인 비교회수를 급수로 표현하면 아래와 같은 수식이 됩니다.

 

n개의 원소라면 위 수식에 1 ~ n-1을 넣고 더할 수 있습니다 . 급수를 계산하면

n(n-1)/4 + (n-1) - {1/2 + 1/3 + ... + 1/n} 이 됩니다.

여기서 1/2 + 1/3 + ... + 1/n 는 1/n + 1/n + ... + 1/n(1)보다 크거나 같고, 1 + 1 + .. + 1(n)보다 작거나 같습니다.

따라서 전체 시간복잡도는  n^2/4 <= n(n-1)/4 + (n-1) - {1/2 + 1/3 + ... + 1/n} <= 5n^2/4로 포현해볼 수 있습니다. 

 

 

코드

def insertionsort(L):
    temp = list(L)
    result = []

    while (len(temp) > 0):
        m = temp.pop(0)
        result.append(m)
        for i in range(1, len(result))[::-1]:
            if(result[i] < result[i-1]):
                result[i], result[i-1] = result[i-1], result[i]
            else: 
                break
    
    return result
A = list(range(20))
random.shuffle(A)
print(insertionsort(A))

 

 

3. 결론

버블 정렬과 삽입 정렬 모두 시간복잡도는 O(N^2)이라고 볼 수 있습니다. 하지만 정렬을 더 빠르게 할 수 있는 방법은 없을까요? 버블 정렬과 삽입 정렬은 모두 "인접한" 원소를 정렬한다는 특징이 있습니다. 인접하지 않은 원소를 정렬할 때에는 O(N^2)보다 더 빠르게 정렬할 수 있는 방법이 있습니다.