이번 시간에는 기본 정렬의 마지막 선택 정렬입니다.


선택 정렬은 버블, 삽입 정렬과 다르게 불안정 정렬입니다.


이 부분에 대해서 글 마지막 부분에 추가적으로 설명해 드리니 집중해서 봐주세요!




선택 정렬(Selection sort) - 불안정 정렬(Unstable sort)


선택 정렬은 매 회전마다 가장 적합하다고 판단되는 값을 선택해 나가는 방법이다.


만약 오름차순으로 정렬한다면, 매 회전마다 가장 작은 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.

(맨 앞 자리는 i번째 회전 때 배열의 i번째 요소입니다.)


반대로 내림차순으로 정렬한다면, 매 회전마다 가장 큰 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.


여기서 선택을 한다는 의미는 해당 인덱스를 기억해 맨 앞자리 원소와 교환한다는 의미입니다.


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



1회전 : 

배열의 처음부터 끝까지 탐색하여 최적 값(1)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(7)과 최적 값(1)을 교환합니다.


2회전 :

배열의 두 번째 부터 끝까지 탐색하여 최적 값(2)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(3)과 최적 값(2)을 교환합니다.


3회전 :

배열의 세 번째 부터 끝까지 탐색하여 최적 값(3)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(3)과 최적 값(3)을 교환합니다.


4회전 :

배열의 네 번째 부터 끝까지 탐색하여 최적 값(5)의 Index를 찾습니다.

그리고 선택 위치 Index의 값(5)과 최적 값(5)을 교환합니다.


데이터가 하나 남았으므로 더 이상 비교할 데이터가 없으니 끝냅니다.




소스 코드


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
#include <iostream>
 
using namespace std;
 
//교환
void swap(int * num1, int * num2){
    int temp;
    temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}
int main()
{
    int a[5] = {7,3,2,1,5};
    int min;
    
    //선택 정렬
    for(int i = 0; i<4; i++){
        min = i;
        for(int j = i+1; j<5; j++){
            if(a[j] < a[min])
                min = j;
        }
        swap(&a[min],&a[i]);
    }
 
    //출력
    for(int i = 0; i<5 ; i++)
        cout << a[i] << " ";
    return 0;
}
 
cs

배열 a : 정렬하고자 하는 데이터 입니다.

min : 가장 적합한 값의 index 입니다.

Line 6-11 : Swap 함수의 정의입니다.

Line 19 : 선택 위치의 값을 제일 최적 값이라고 생각하고 시작합니다.

Line 20-23 : 선택 위치+1 부터 배열의 끝까지 탐색해 나가며 최적 값의 index를 갱신합니다. 

Line 24 : 최적 값의 위치와 선택 위치의 값을 교환합니다.




시간 복잡도


선택 정렬은 기존 데이터의 구성에 따라 비교 횟수가 변하지 않고, 


모든 비교를 진행하기 때문에 n-1 부터 1 까지 등차수열의 합입니다.


따라서 시간복잡도는 이 됩니다.




왜 불안정정렬인가?


가장 간단하게 선택 정렬시에 불안정 정렬이 되는 예를 보여드리겠습니다.


다음과 같은 카드들이 있습니다.




이 카드들에서 숫자5를 가진 카드들만 본다면 다이아몬드5 - 스페이스5의 순서를 확인 할 수 있습니다.


만약 이 상황에서 카드의 숫자를 기준으로 오름차순으로 정렬하면 1회전때 다음과 같은 교환이 일어납니다.





그리고 나서 결과를 살펴보면 아래와 같이 변합니다.



결국 1회전 이후 완전히 정렬되었으므로 2, 3, 4 회전때는 교환이 일어나지 않습니다.


최종 정렬 결과를 살펴보면 기존의 다이아몬드5 - 스페이스5 순서가 뒤바뀐 모습을 볼 수 있습니다.


이는 앞서 설명했던 불안정 정렬의 기존 순서를 보존하지 않는 특성입니다.


따라서 선택 정렬은 불안정 정렬입니다.


만약 어떤 데이터를 정렬할 때, 위와 같은 결과를 원하시지 않으면 안정 정렬 알고리즘을 선택하는 게 옳습니다.



지금까지 버블, 삽입 정렬에 이어 선택 정렬을 살펴봤습니다. 


다음 글 부터는 본격적으로 고급 알고리즘에 대해서 포스팅 해보도록 하겠습니다.


감사합니다!







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

[알고리즘] - 합병 정렬(Merge sort) #7  (2) 2019.02.06
[알고리즘] - 퀵 정렬(Quick sort) #6  (0) 2019.01.31
[알고리즘] - 삽입 정렬(Insertion sort) #4  (3) 2019.01.15
[알고리즘] - 버블 정렬(Bubble Sort) #3  (1) 2019.01.10
[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2  (5) 2019.01.09

이번 시간에는 저번 시간에 이어 기본 정렬 중 하나인 삽입 정렬(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

저번 글에서 언급했듯이 이제부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다.


이번 시간에는 기본적인 정렬 알고리즘 세 개 중 하나인 버블 정렬입니다.

(삽입과 선택은 다음 시간에 다루겠습니다!)


버블 정렬(Bubble Sort) - 안정 정렬


버블 정렬이란 인접한 두 원소를 계속 비교해 나가며 최종 정렬 값을 하나씩 완성해 나가는 방법입니다.


글로써는 이해하기가 어려울 수 있으니 그림으로 자세하게 설명드리도록 하겠습니다.







위 그림은 주어진 데이터를 오름 차순으로 버블 정렬하는 과정입니다.(데이터의 사이즈 n = 5)


정렬 과정은 데이터의 수 - 1 만큼 회전(반복)하며 큰 값을 결정해 나가는 것입니다.


다시 말해 1회전 - 첫 번째로 큰 값(7), 2회전 - 두 번째로 큰 값(5) ... 마지막으로  n-1 번째로 큰 값(2)을 결정하고 끝입니다.

(n번째 큰 값 1은 n-1번째로 큰 값이 정해지면 알아서 정해지므로 n-1번째 까지만 진행합니다.)


최종적으로 7 - 3 - 2 - 1 -5 의 데이터가 1 -2 - 3 - 5 - 7 로 정렬됨을 확인할 수 있습니다.



소스 코드


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
#include <iostream>
 
using namespace std;
 
void swap(int *a, int * b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
int main()
{
    int a[5] = {7,3,2,1,5};
    bool endFlag;
    
    //정렬
    for(int i = 0 ; i < 4;i++){
        endFlag = true;
        for(int j=0; j <4-i;j++){
            if(a[j]>a[j+1]){
                swap(&a[j],&a[j+1]);
                endFlag = false;
            }
        }
        if(endFlag) break;
    }
    
    //출력
    for(int i = 0; i <=4; i++)
        cout << a[i] <<" ";
    return 0;
}
 
cs



코드 설명


배열 a : 정렬하고자 하는 데이터 입니다.


endFlag : 정렬 과정 중에서 데이터의 교환(swap)이 일어나지 않으면, 정렬된 상태이므로 이 때 탈출하기 위한 신호(Flag) 변수입니다.


Line 5 - 10 : 데이터의 위치를 바꾸는 함수 정의입니다.


Line 19 : 매 회전마다 교환 여부를 파악하기 위해 true로 초기화


Line 21 -24 : 인접한 데이터의 순서가 맞지 않으면 교환하고 endFlag를 false로 변경하여 탈출하지 않습니다.


Line 26 : endFlag 값을 보고 정렬 완성 상태를 파악한 후 반복문을 끝낼지 결정하는 부분입니다.



시간 복잡도


버블 정렬을 사용했을 때 최악의 경우는 정렬하고자 하는 방향의 반대로 구성된 데이터들을 정렬할 때 입니다.


다시 말해서 오름차순으로 정렬하고자 할 경우 내림차순으로 정렬된 데이터들을 오름차순으로 정렬하는 경우입니다.


이 경우에는 endFlag 인해서 중간에 break가 되지 않고, 끝까지 돌아갑니다.


입력 데이터의 크기가 n 일때 시간복잡도를 계산해보면,


1회전 : n-1번비교, 2회전 : n-2번 비교  n-1회전 : 1번 비교


이를 계산하면 n-1 부터 1까지 등차 수열의 합이므로 최고 차항은 n에 대한 2차식이 됩니다.


따라서 시간복잡도는 이 됩니다.











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

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

+ Recent posts

티스토리툴바