안녕하세요 고급 정렬 알고리즘 두 번째이자 마지막 시간입니다!


힙 정렬이 하나 더 있기는 하지만 별도의 자료구조가 필요하기 때문에 추후에 다루도록 하겠습니다.


그럼 빠르게 본론으로 들어가보겠습니다!


합병 정렬(Merge sort) - 안정 정렬(Stable sort)


합병 정렬은 데이터를 이분할 하는 작업을 반복하여 크기가 1인 데이터까지 분할하고, 


이 데이터들을 정렬해 나가며 최종적으로 완전 정렬하는 알고리즘입니다.


즉, 분할 정복 기법을 이용한 정렬 방법입니다.


따라서 합병 정렬은 분할, 정복(정렬) 이 두 단계로 이루어져 있습니다.


그림과 함께 조금 더 자세하게 설명해 드리도록 하겠습니다.


- 분할 단계



맨 처음 정렬해야 하는 데이터(7-3-2-1-5-4-6) 가 있습니다.


우선, 주어진 데이터의 인덱스를 0(start)~6(end)번이라고 생각해 보겠습니다.


이를 이분할 하기 위해서 중간점(mid)를 계산해야 하며 mid 는 다음과 같이 계산됩니다.


mid = (start + end) / 2


그렇게 되면 전반부 구간은 start~mid, 후반부 구간은 mid+1~end로 정할 수 있습니다.


이러한 구간 정보를 아래와 같이 분할 함수의 인자로 넘겨주는 작업을 반복(재귀)적으로 수행합니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid);

분할(data, mid+1, end);

}


그렇게 되면 주어진 데이터는 최종적으로 크기가 1인 데이터 까지 분할됩니다.



- 정복(정렬) 단계



정복 단계에서는 분할된 구간을 정렬해 나가면서 부분 문제를 해결합니다.


즉, 분할 이후에 정복 과정을 거치게 되는 것이죠. 간략하게 표현하자면 다음과 같습니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid); //부분 문제 해결로 전반부 정렬 완료

분할(data, mid+1, end); //부분 문제 해결로 후반부 정렬 완료

정복(data, start, mid, end); //전반부와 후반부를 비교하며 정렬

}


이제 정복함수의 간략적인 구성에 대해서 알아보도록 하겠습니다.


정복 함수는 크게 두 단계로 이루어져 있는데, 바로 임시 배열을 채우는 과정과 원래 배열에 임시 배열 값을 복사하는 과정입니다.


1) 전반부와 후반부 데이터를 비교하며 임시 배열 채우기


오름차순으로 정렬한다면, 전반부와 후반부의 데이터 중 작은 값을 비교해가며 임시 배열을 채웁니다.


이 과정을 전반부 혹은 후반부의 데이터가 빌 때 까지 진행하고, 이후 남은 데이터를 일괄적으로 채워주면 됩니다.


2) 임시 배열 값을 원래 배열에 복사하기


임시 배열에 정렬된 데이터를 저장했기 때문에 원래 배열에 복사해줍니다!



소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
int temp[7]; //정렬을 위한 임시 배열
//병합 함수 정의
void merge(int* a, int start,int mid, int end) {
    int firstPart = start;
    int lastPart = mid + 1;
    int savePoint = start;
 
    //전반부와 후반부를 비교하며 임시배열에 복사
    while ((firstPart <= mid) && (lastPart <=end)) {
        if (a[firstPart] <= a[lastPart])
            temp[savePoint++] = a[firstPart++];
        else
            temp[savePoint++] = a[lastPart++];
    }
 
    //전반부의 값이 남아 있다면
    while (firstPart <= mid)
        temp[savePoint++] = a[firstPart++];
 
    //후반부의 값이 남아 있다면
    while (lastPart <= end) 
        temp[savePoint++] = a[lastPart++];
 
    //임시 배열의 값을 원래 배열에 복사
    for (int i = start; i <= end; i++)
        a[i] = temp[i];
}
//분할 함수 정의
void partion(int * a, int start, int end) {
    int mid;
    if (start < end) {
        mid = (start + end) / 2;
        partion(a, start, mid); //전반부 - 분할 과정
        partion(a, mid + 1, end); //후반부 - 분할 과정
        merge(a, start, mid, end); //병합 - 정복 과정
    }
}
int main() {
    int a[7] = { 7,3,2,1,5,4,6 };
    partion(a,0, 6);
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
    return 0;
}
cs


* 소스코드 라인별 설명은 주석으로 대체하겠습니다! *

시간 복잡도




합병 정렬의 경우에는 퀵 정렬과 달리, 항상  을 보장합니다.


그 이유는 매번 이분할을 하기 때문에 분할된 구간의 크기가 항상 일정하게 형성됩니다.


따라서 위 그림처럼 크기가 N인 데이터를 이분할 했을 경우에는 의 분할이 존재하게 되고,


이 각 분할에 대해서 N번의 비교가 이루어지기 때문에 항상  을 보장합니다.


이러한 특성 때문에 합병 정렬은 안정적인 성능을 보장하는 정렬 방법으로 알려져 있습니다.


다만 합병 정렬의 경우에는 소스 코드에서 볼 수 있듯이, 정렬하기 위한 추가적인 공간이 필요하다는 특징을 가지고 있습니다.




이번 포스팅에서 준비한 내용은 여기까지 입니다!


이제 드디어 정렬이 끝났습니다. 


다음 포스팅 부터는 본격적으로 그래프 관련 알고리즘에 대해서 알아보도록 하겠습니다.


그래프 관련 알고리즘들은 코딩테스트에서도 많이 출제되는 부분이니 더 힘내서 공부해주시기 바라겠습니다!


'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] - 깊이 우선 탐색(DFS) #9  (0) 2020.01.19
[알고리즘] - 그래프의 표현 방법 #8  (0) 2019.03.13
[알고리즘] - 퀵 정렬(Quick sort) #6  (0) 2019.01.31
[알고리즘] - 선택 정렬(Selection sort) #5  (0) 2019.01.16
[알고리즘] - 삽입 정렬(Insertion sort) #4  (3) 2019.01.15

이번 시간에는 저번 시간에 이어 기본 정렬 중 하나인 삽입 정렬(Insertion sort)에 대해서 알아보도록 하겠습니다.



삽입 정렬(Insertion sort) - 안정 정렬(Stable sort)


삽입 정렬이란 정렬된 구간과 그렇지 않은 구간 둘로 나누고, 


정렬되지 않은 구간의 맨 앞 원소를 가져와 정렬된 구간에 삽입하는 알고리즘입니다.


알고리즘의 수행 단계는 다음과 같습니다.


1) 주어진 데이터 중 맨 앞의 원소를 정렬된 구간으로 설정하고, 나머지를 그렇지 않은 구간으로 정합니다.


2) 삽입 데이터 정하기 : 정렬되지 않은 구간의 맨 앞 데이터를 삽입 데이터(key 값)로 정한다.


3) 삽입 위치 파악하며 데이터 밀어내기 : 정렬 구간을 역순으로 탐색하며 Key 값이 삽입될 위치를 파악합니다.


4) 모든 데이터가 정렬될 때까지 2-3 과정을 반복합니다.


좀 더 자세하게 그림으로 보여드리겠습니다.





이 그림을 위에서 언급한 순서와 함께 설명하자면 다음과 같습니다.


1) 주어진 데이터(7-3-2-1-5) 에서 7을 정렬된 구간으로 설정하고 나미저 3-2-1-5를 정렬되지 않은 구간으로 설정하여 시작합니다.


1 회전 : 

2) 3을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 정렬된 구간을 7부터 역순으로 탐색하며 삽입 위치를 합니다. 이때, (Key 값 > 비교 데이터) && (더 이상 비교할 데이터가 없는가?)를 만족해야 합니다. 따라서, 조건을 비교해가며 결국 첫 번째 자리에 삽입되게 됩니다.


2 회전 :

2) 2를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


3 회전 :

2) 1을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


4 회전 :

2) 5를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2, 3회전과 달리 두 번째 비교작업때 Key 값이 비교데이터(3) 보다 크므로 조건에 위배됩니다. 따라서, 그때 빈 공간에 삽입되게 됩니다.



소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
using namespace std;
 
int main()
{
    int a[5] = {7,3,2,5,1};
    int key,j;
 
    //삽입 정렬
    for(int i = 1 ; i< 5; i++){
        key = a[i];
        j = i;
        while(key < a[j-1] && j>0){
            a[j] = a[j-1];
            j--;
        }
        a[j] = key;
    }
 
    //출력
    for(int i = 0 ; i< 5; i++)
        cout << a[i] << " ";
 
    return 0;
}
 
cs



배열 a : 정렬하고자 하는 데이터


key : 정렬되지 않은 구간에서 정렬 구간으로 옮기며 정렬할 값


j : key 값의 삽입 위치


Line 11: 

i 는 정렬되지 않은 구간에서 삽입할 데이터의 위치를 의미합니다. 

따라서 첫 번째 값을 정렬 구간으로 설정하기 때문에 1부터 시작합니다.


Line 12 :

정렬할 데이터를 Key 변수에 저장합니다.


Line 14 :

Key < a[j-1] -> Key 값 보다 큰 값이 이전에 있으면 계속 진행하는 조건 입니다.

j>0 -> key 값이 제일 작아 처음에 삽입되어야 하는 조건입니다.


Line 15-16 :

데이터의 삽입을 위해 정렬된 구간의 데이터들을 뒤로 한칸씩 미룹니다. 또한 다음 탐색을 위해 j값을 감소시킵니다.


Line 18 :

한 회전을 통해서 삽입할 위치를 찾았으니 데이터를 삽입합니다.



시간 복잡도


삽입 정렬에서 최악의 경우는 버블 정렬과 마친 가지로 역순으로 정렬되어 있을 경우다.


즉, 매 회전마다 삽입되는 데이터가 정렬 구간의 처음에 삽입된다면,


1회전에 1번, 2회전 2번 ... n-1 회전에 n-1번 동작하기 때문에


1부터 n-1 까지 등차 수열의 합이므로 n에 대한 2차식이다. 따라서 시간복잡도는 이 됩니다.



 

'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] - 퀵 정렬(Quick sort) #6  (0) 2019.01.31
[알고리즘] - 선택 정렬(Selection sort) #5  (0) 2019.01.16
[알고리즘] - 버블 정렬(Bubble Sort) #3  (1) 2019.01.10
[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2  (5) 2019.01.09
[알고리즘] - 알고리즘과 성능 척도 #1  (1) 2019.01.07

+ Recent posts

티스토리툴바