[알고리즘] Selection Sort - Proof & Time Complexity

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

Proof of Correctness of Sorting

---

'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가?

 

- 입력 값 : a[0], a[1], ... , a[n-1]

- sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1]

 

조건 1:

값이 없어지거나, 새로 생기면 안된다. (집합 조건)

{a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]}

 

조건 2:

값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다.

b[0] < b[1] < ... < b[n-1]

 

 

Selection Sort by For Loop

---

입력 배열 arr에는 같은 값이 없다고 가정하자.

void selectionSort(int arr[], int size) {
    for (int start = 0; start < size; ++start) {
        int min = start;
        for (int i = start; i < size; ++i) {
            if (arr[i] < arr[min]) {
                min = i;
            }
        }
        swap(arr[start], arr[min]);  // arr[start]과 arr[min]의 값을 서로 교환한다.
    }
}

 

Proof of the Invariant by Induction

Invariant:

k번째 loop가 끝난 후에는 아래 두 가지 조건을 만족한다.

1. arr[0] < arr[1] < ... < arr[k-1]

2. arr[k-1] < a[x] (x > k-1)

 

 

selectionSort() 함수가 종료되었을 때, 즉 n번째 loop가 끝난 후를 생각해보자. (k = n)

 

k = n을 Invariant 2번 식에 대입해보면, arr[n-1] < arr[x] (x > n-1)

이때 x > n-1인 x는 존재하지 않는다.

→ Vacuously True

 

k = n을 Invariant 1번 식에 대입해보면, arr[0] < arr[1] < ... < arr[n-1]

이는 Proof of Correctness of Sorting의 조건 2번과 같아진다.

 

위 코드에서는 집합 조건을 깨는 부분이 없으므로, Proof of Correctness of Sorting의 조건 1번은 항상 True이다.

 

따라서 Invariant가 항상 성립한다는 것을 증명하면, (Invariant를 끝까지 끌고 갈 수 있다면)

selectionSort() 함수를 통해서 모든 경우에 sorting이 된다는 것이 증명되는 것이다.

 

 

Base:

k = 0, 즉 0번째 loop가 끝난 경우?

 

1. arr[0] < ... < arr[-1]

'index 0부터 -1까지'라는 것은 '아무것도 없다'는 것과 같다.

→ Vacuously True

 

2. arr[-1] < arr[x] (x > -1)

arr[-1]은 존재하지 않기 때문에, 조건 x > -1만 남게 된다.

→ Vacuously True

 

 

Step:

k번째 loop이 끝났을 때 Invariant가 성립한다면, k+1번째 loop이 끝났을 때에도 Invariant가 성립한다.

 

k번째 loop가 끝났다면,

1. arr[0] < arr[1] < ... < arr[k-1]

2. arr[k-1] < arr[x] (x > k-1)

 

k+1번째 loop가 끝났다면,

1. arr[0] < arr[1] < ... < arr[k-1] < arr[k]

2. arr[k] < arr[x] (x > k)

 

arr[k]는 'arr[k-1] < arr[x] (x > k-1)' 중에 있던 놈이기 때문에 1번이 성립한다.

arr[k]는 'arr[k-1] < arr[x] (x > k-1)' 중에서 가장 작은 놈이기 때문에 2번이 성립한다.

 

따라서 Invariant는 성립한다.

 

 

Recursive Selection Sort

---

void selectionSort(int arr[], int size) {
    if (size <= 1) {
        return;
    }

    int min = 0;
    for (int i = 0; i < size; ++i) {
        if (arr[i] < arr[min]) {
            min = i;
        }
    }
    swap(arr[0], arr[min]);  // arr[0]과 arr[min]의 값을 서로 교환한다.

    selectionSort(arr + 1, size - 1);
}

 

Proof by Induction

주장:

selectionSort() 함수를 통해서 sorting이 된다.

 

 

Base:

n = 1

아무것도 진행하지 않아도 된다. → True

 

 

Step:

n-1일 때 selectionSort() 함수가 sorting에 성공한다면, n일 때에도 selectionSort() 함수가 sorting에 성공한다.

 

즉, 재귀호출이 끝난 후에 arr[1] < arr[2] < ... < arr[n-1]이 성립한다면,

함수가 끝났을 때 arr[0] < arr[1] < arr[2] < ... < arr[n-1]이 성립한다는 것을 보이면 된다.

 

중간의 for문에 의해서,

arr[0] < arr[1], arr[0] < arr[2], ... , arr[0] < arr[n-1]이 전부 성립한다. (arr[0]은 배열에서 가장 작은 값이기 때문)

 

따라서

재귀호출이 끝난 후에도 arr[0] < arr[1], arr[0] < arr[2], ... , arr[0] < arr[n-1]이 전부 성립하기 때문에

함수가 끝났을 때 arr[0] < arr[1] < arr[2] < ... < arr[n-1]가 성립한다.

 

Time Complexity

T(n)

= n + T(n-1)

= n + n-1 + T(n-2)

= ...

 

∴ O(N^2)