[Algorithm] 정렬: 버블 정렬, 삽입 정렬

+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.

정렬 문제

=> n개의 서로 다른 수가 주어졌을 때, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순) 만드는 문제

ex) 9, 3, 5, 7 => 3, 5, 7, 9

 

- 한 문제를 풀기 위해서 여러가지 방법이 가능하다.

- 방법마다 특징이 다르다.

- 기본적인 문제이면서, 실생활에 자주 쓰인다.

- 시간 복잡도, 최적성에 대해서 증명이 쉽다.

 

정렬할 데이터가 담긴 배열의 각 원소를 O(1) 시간에 접근 가능하다고 가정한다.

(데이터가 메인 메모리에 저장되어 있다고 가정한다.)

---

버블 정렬

1. 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환한다.

2. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복한다.

 

ex) 5 3 1 4 2를 버블 정렬하라.

5 3 1 4 2

3 5 1 4 2

3 1 5 4 2

3 1 4 5 2

3 1 4 2 5

 

3 1 4 2 5

1 3 4 2 5

1 3 4 2 5

1 3 2 4 5

 

1 3 2 4 5

1 3 2 4 5

1 2 3 4 5

 

1 2 3 4 5

1 2 3 4 5

 

< 정확성 >

- 제일 큰 원소가 제일 뒤에 존재하고, 그 다음 큰 원소가 그 앞, 그 다음 큰 원소가 그앞, ...

 

< 시간 복잡도 >

처음 가장 큰 원소를 구할 때 n -1번 비교하고, 두 번째 큰 원소를 구할 때 n-2번, ...

=> (n-1) + (n-2) + ... + 1 = n(n-1) / 2 => Θ(n^2)

 

즉, 입력과 무관하게, n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행한다.

ex) 1 2 3 4 5와 5 4 3 2 1의 비교 횟수가 같다.

 

import random

def bubblesort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i + 1):
            if j + 1 < len(arr) and arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

List = list(range(20))
random.shuffle(List)
print(List)
print(bubblesort(List))

j + 1이 리스트 길이보다 큰 경우 에러가 발생하므로 주의!

---

삽입 정렬 (insertion sort)

1. 정렬 대상이 될 원소를 두 부분으로 나눈다.

- 앞은 이미 정렬이 된 부분 (오름차순이 만족하는 부분)

- 뒤는 정렬할 부분

2. 매번 정렬할 부분의 가장 첫번째 원소를 정렬이 된 부분에 삽입한다.

- 삽입은 정렬된 부분의 가장 큰 원소(= 가장 오른쪽 원소)부터 왼쪽으로 비교해나가면서 진행한다.

 

ex) 5 3 1 4 2를 삽입 정렬하라

5 3 1 4 2 (처음 원소 5는 그 자체로 정렬된 수)

 

5 3 1 4 2

3 5 1 4 2

 

3 5 1 4 2

3 1 5 4 2

1 3 5 4 2

 

1 3 5 4 2

1 3 4 5 2

1 3 4 5 2

 

1 3 4 5 2

1 3 4 2 5

1 3 2 4 5

1 2 3 4 5

1 2 3 4 5

 

import random

def insertsort(arr):
    result = [] # 정렬한 부분
    while len(arr) > 0:
        num = arr.pop(0)
        result.append(num)
        for i in range(len(result) - 1, 0, -1):
            if result[i] < result[i-1]:
                result[i], result[i-1] = result[i-1], result[i]
            else:
                break
    return result

List = list(range(20))
random.shuffle(List)
print(List)
print(insertsort(List))

 

< 정확성 >

1. 이미 정렬된 부분은 항상 정렬이 되어 있다.

2. 처음에는 정렬된 부분에 원소 1개 있다. (원소 1개는 그 자체가 정렬되어 있다.)

3. 매번 정렬할 부분의 원소 1개를 정렬된 부분으로 옮긴다.

- 정렬할 부분은 처음 n-1개 원소를 갖고 있다.

- 매번 1개씩 감소하므로, 최종적으로 정렬된 부분에 n개 정렬할 부분에 0개의 원소가 있다.

- 정렬된 부분은 정렬이 되어 있으므로 최종적인 정답은 정렬된 상태이다.

 

< 시간 복잡도 >

최선의 경우: 이미 오름차순으로 정렬되어 있을 때

- 정렬된 부분에 원소를 넣을 때마다 비교를 한 번만 하면 된다.

=> 총 n-1번 비교 => Θ(n)

 

최악의 경우: 역순으로 정렬된 수들을 정렬할 때

- i번째 위치의 원소를 정렬된 부분에 추가할 때 i-1개의 원소와 모두 비교해야한다.

(이미 정렬된 부분에 i-1개의 원소가 있을 때)

=> i = 2, 3, 4, ..., n 이므로 1 + 2 + ... + n-1 = n(n-1) / 2 => Θ(n^2)

 

 평균 시간 복잡도: i개의 정렬된 부분에 i+1번째 원소를 삽입할 때

- 삽입을 마치면 정렬된 부분에는 i+1개의 원소가 있고 1등부터 i+1등이 가능하다.

- i+1등할 확률은 1 / (i+1)이고 비교는 1번

- i등할 확률은 1 / (i+1)이고 비교는 2번

- ...

- 2등할 확률은 1 / (i+1)이고 비교는 i번 (마지막 원소와 비교하여 크면 2등)

- 1등할 확률은 1 / (i+1)이고 비교는 i번 (마지막 원소와 비교하여 작으면 1등)

 

기대값의 선형성: E[x+y] = E[x] + E[y]

 

i+1번째 원소를 추가할 때 평균적인 비교횟수

=> 2등일 때부터 i+1등일때까지 확률의 합 + 1등일 때의 합

=> i가 1~n-1까지 합은 n(n-1) / 4 + (n-1) - {(1 / 2) + (1 / 3) + ... + (1 / n)}

n(n-1) / 4 + (n-1)

=> Θ(n^2)

{(1 / 2) + (1 / 3) + ... + (1 / n)}

=> {(1 / n) + (1 / n) + ... (1 / n)} ≤ {(1 / 2) + (1 / 3) + ... + (1 / n)} ≤ {1 + 1 + ... + 1}

=> 1 ≤ {(1 / 2) + (1 / 3) + ... + (1 / n)} ≤ n-1

 

따라서,  n^2 / 4 ≤ n(n-1) / 4 + (n-1) - {(1 / 2) + (1 / 3) + ... + (1 / n)} ≤ 5n^2 / 4

 

=> 평균적인 시간 복잡도는 Θ(n^2)이다.

 

+ 수열의 합의 크기를 추정할 때, 반복되는 횟수만큼 가장 큰 값을 더한 것보다는 작고, 가장 작은 값을 더한 것보다는 크다는 성질을 이용하여 범위를 구할 수 있다.

---

O(n^2)보다 빠르게 정렬할 수 있는가?

인접한 두 원소를 교환하는 방식의 정렬 알고리즘은 O(n^2)보다 빨리 정렬할 수 없다.

 

< 증명 >

- n개의 서로 다른 값을 가지는 원소를 나열하는 방법은 n! 가지가 있지만, 오름차순/내림차순으로 정렬된 결과는 한 가지이다.

- n개의 원소 중 둘을 뽑는 방법은 (n, 2)가지가 있다.

- 정렬되지 않았다면 순서가 틀린 쌍(= 둘을 뽑았을 때 앞의 원소가 뒤의 원소보다 큰 쌍)이 있다.

- 정렬되었다면, 순서가 틀린 쌍이 없다.

- 인접한 두 원소를 교환하면 이 중 오로지 한 쌍이 제거된다. 

ex) 1 2 5 4 3 => 1 2 5 3 4 (단 한 쌍만 수정)

ex) 1 2 5 4 3 => 1 2 3 4 5 (멀리 떨어진 쌍을 바꾸면 한 번에 모두 수정)

- 최악의 경우에는 모든 쌍의 순서가 잘못되어있다. (역순 정렬)

- 따라서, (n, 2) = O(n^2)번 교환이 필요하다.