언제부턴가 삽입정렬과 선택정렬을 헷갈리기 시작하는 것을 시작으로

소팅 알고리즘은 물론 여러 자료구조들을 잊어버리기 시작했다.

 

그래서 다시 공부할 겸 블로그에 다시 정리해두어야겠다 싶다.

 

---

Basic Concept of Sorting

오늘 얘기할 두 정렬에 대해 이야기 하기 전에, 우선 정렬이 무엇인가에 대해 정의해보자.

 

1.  어떤 임의의 원소 e는 집합 S 에 속한다.

2.  집합 S에 속하는 두 요소 e1, e2 에 대하여 <, >, = 연산이 정의된다.

 

집합 S에 대해 소팅하였을 때, 다음 조건을 만족한다.

 

1. 오름차순으로 소팅한 후 집합 S의 원소들을 순회하였을 때, 이전에 순회한 원소는 반드시 이번에 순회한 원소보다 작아야 한다.

2. 내림차순으로 소팅한 후 칩합 S의 원소들을 순회하였을 때, 이전에 순회한 원소는 반드시 이번에 순회한 원소보다 커야 한다. 

 

Insertion Sort

Concept

사실 삽입정렬(Insertion sort)은 인간이 주로 생각하는 소팅 방식으로, 카드게임에서 많이 찾아볼 수 있다.

세븐포커를 치는데, 카드 깔 때쯤 되니 이렇게 되었다 치자. (모양은 신경쓰지 말고)

 

8 A 3 Q J 10 K

 

갑자기 이게 신경쓰여 숫자 순서대로(오름차순으로) 정리하고 싶은데, 앞에서부터 하나하나 살펴가보자.

맨 앞에 있는건 제대로 있다 치고, 두번째 꺼부터 살펴보자.

 

8 A 3 Q J 10 K

A는 첫번째에 있어야 하는데 왜인지 두번째에 있다. 불편하다.

바로 전부터 처음까지 훓어보면, 8이 꿰차고 있다. 바꾸어주자.

 

8 A 3 Q J 10 K

 

A 8 3 Q J 10 K

 

이제 좀 편안해졌다.

세번째를 보니 3이 있는데, 이것보다 큰게 있는지 또 바로 전부터 처음까지 훓어보자.

 

A 8 3 Q J 10 K

 

두번째에 8이 꿰차고 있다. 불편하다. 바꿔주자.

 

A 8 3 Q J 10 K

 

A 3 8 Q J 10 K

 

편안하다.

4번째를 보니 Q가 있다. 바로 전부터 처음까지 훑어보니 Q보다 큰 게 없다. 편안하다.

 

A 3 8 Q J 10 K

 

5번째를 보니 J가 있다. 바로 전부터 처음까지 훑어보니 4번째에 J보다 큰 Q가 있다. 불편하다.

바꿔주자.

 

A 3 8 Q J 10 K

 

A 3 8 J Q 10 K

 

편안하다.

6번째를 보니 10이 있다. 바로 전부터 처음까지 훑어보니 4번째에 10보다 큰 J가 있다. 불편하다.

바꿔주자.

 

A 3 8 J10 K

 

A 3 8 10 Q J K

 

여기서 문제가 생겼다.

다음 K 를 보면 끝나는데, 막상 결과를 보면 소팅이 제대로 안됐다.

 

첫번째부터 5번째까지는 바로 옆에 있는 것끼리 바꾼 것처럼 보인다.

그러나 사실은 그 옆에 "삽입" 한 것이다.

 

다시 6번째로 돌아가서, 제대로 해본다. 10을 J 옆에 "삽입" 한다.

 

A 3 8 10 J Q K

 

마지막 K를 본다.  가장 큰 수니까 제 위치에 잘 있다.

 

A 3 8 10 J Q K

Abstraction

결국, 처음부터 끝까지 순회하면서, 바로 전 부분부터 처음까지 한번 더 순회하며 지금 순회중인 원소보다 큰 것을 (내림차순이라면 작은 것을) 발견하면, 그 이전에 삽입하는 것이 삽입정렬이다.

Implementation

삽입정렬을 C에서 배열을 이용하여 구현해 보면 이렇게 해볼 수 있다.

(Introduction to Algorithms, 3/E, 18p의 pseudocode를 기반으로 작성)

// arr : int형 포인터지만 배열이 들어간다.
// size: 포인터를 인자로 받으므로 배열 크기를 명시해줄 필요가 있다.
void insert_sort(int* arr, unsigned int size) {
    unsigned int i, j;
    int cur;
    
    // 두번째 원소부터 순회한다.
    for (i = 1; i < size; ++i) {
        cur = arr[i];
        
        // 바로 전부터 처음까지 훓고 내려간다.
        // cur보다 큰 수가 나올때까지
        j = i - 1;
        while (j > 0 && arr[j] > cur) {
            arr[j + i] = arr[j];
            --j;
        }
 
        // 비운 자리에 현재 값을 넣는다.
        // 만일 비운 자리가 없다면 제자리를 유지한다.
        arr[j + 1] = cur;
    }
}

Complexity

최선의 경우 (즉 정렬된 경우)에는 자리 교환이 일어나지 않는다. -> O(n)

 

최악의 경우 (자료가 역순으로 정렬된 경우)에는 모든 경우에 대하여 i번씩 비교 및 이동이 수행된다.

즉, (1 + 2 + 3 + ... + n-1) = n(n-1)/2 이므로 O(n^2) 이다.

Selection Sort

Concept

아까 친 포커가 끝난 뒤 한번 더 치기로 했다. 또 똑같은 카드가 튀어나왔다.

 

8 A 3 Q J 10 K

 

선택정렬 방식으로 카드를 정리해보자.

첫번째에 가장 작은 카드가 와야 하니까, 한번 훑어본다. A가 가장 작다. 처음으로 옮겨준다.

 

8 A 3 Q J 10 K


 A 8 3 Q J 10 K

 

두번째에 그 다음으로 작은 것이 와야 하니 또 한번 훑어본다. 남은 것 중 3이 가장 작으니 두번째와 바꿔준다.

 

 A 8 3 Q J 10 K

 

 A 3 8 Q J 10 K

 

세번째에 그 다음으로 작은 것이 와야 하니 또 한번 훑어본다. 남은 것 중 8이 가장 작지만 제 자리에 있다.

 

 A Q J 10 K

 

네번째에 그 다음으로 작은 것이 와야 하니 또 한번 훑어본다. 남은 것 중 10이 가장 작으니 네번째로 옮겨준다.

 

 A 3 8 Q J 10 K

 

 A 3 8 10 J Q K

 

다섯번째 이후를 보니 J, Q, K가 모두 제 자리에 잘 있다.

Abstract

선택정렬은 배열을 순회하면서 해당 위치에 적합한 최솟값을 찾는다. 만일 해당 위치에 최솟값이 위치한다면 그 다음으로 넘어가며, 그렇지 않은 경우 서로 위치를 뒤바꾼다.

Implementation

삽입정렬을 C에서 배열을 이용하여 구현해 보면 이렇게 해볼 수 있다.

// 스왑 함수
// 서로 변수의 값을 바꿔준다.
void swap(int* a, int* b) {
    int temp = *a; // 임시로 a의 값을 보관한다.
    *a = *b;       // a에 b의 값을 넣는다.
    *b = temp;     // b에 임시로 저장한 a 값을 넣는다.
}

// arr : int형 포인터지만 배열이 들어간다.
// size: 포인터를 인자로 받으므로 배열 크기를 명시해줄 필요가 있다.
void selection_sort(int* arr, unsigned int size) {
    unsigned int i, j;
    int least_pos; // 최솟값의 위치
    
    // 전체 배열을 순회한다.
    for (i = 0; i < size; ++i) {
        least = arr[i]; // 현재 위치가 최솟값이라고 가정한다.
        
        // 그 뒤쪽으로 최솟값이 있는지 탐색한다.
        for (j = i + 1; j < size; ++j) {
            if (arr[least_pos] > arr[j]) {  // 현재 최솟값보다 작은 수가 있다면 
                least = j; // 그 수를 최솟값이라고 한다.
            }
        }
        
        // 현재 값의 위치와 최솟값의 위치가 다르다면
        if (i != least_pos) {
            swap(&arr[i], &arr[least_pos]); // 서로 위치를 바꾸어준다
        }
    }
}

Complexity

최선의 경우나 최악의 경우나 요소의 갯수 * (요소의 갯수 - 현재 위치) 만큼의 순회가 발생한다.

따라서 (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 O(n^2) 이다.

Comparison

삽입정렬은 현재 위치의 값보다 큰(작은) 요소를 찾아 그 전 위치에 "삽입" 하는 것이라면,

선택정렬은 현재 위치에 알맞는 최솟값(최댓값)을 "선택"하여 자리를 맞바꾸는 것인 셈이다. 

Reference

Thomas H. Cormen, et al., Introduction to Algorithms 3/E, 18p

 

[알고리즘] 선택 정렬(selection sort)이란

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html