<개인공부>/[Algorithm]

선택 정렬 (Selection Sort) 이론과 코드

BlockDMask 2017. 9. 24. 11:30
반응형

안녕하세요. BlockDMask 입니다. 

오늘은 간단한 정렬 알고리즘 중에 선택 정렬(Selection Sort)에 대해서 알아 보도록 하겠습니다. 

보시다가 이상하거나 궁금한 부분이 있으면 댓글 부탁드리겠습니다.


0. 원리

  • 오름 차순 기준일때 해당 하는 배열 안에서 가장 작은 값부터 찾아서 맨 앞부터 정렬 시키는 방법 입니다.

  • 그림으로 그려보겠습니다.


  • 주어진 배열(리스트) 중에 최소값을 찾습니다.
    -> 그 최소값과 맨 앞의 값을 바꾸어 줍니다(swap)
    -> 바꿔서 fixed 된 값을 제외하고 나머지 배열(리스트) 중에 최소값을 찾습니다.
    -> 그 최소값과 나머지 배열중에 맨 앞의 값을 바꾸어 줍니다(swap)
    -> -> -> 쭉쭉쭉.

1. 코드 및 결과


> 코드(C++)


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
46
47
48
49
50
51
//Selection Sort
 
#include<iostream>
using namespace std;
 
//swap 함수
void Swap(int &a, int &b){
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}
 
 
//selection sort.
//오름차순으로 구현하겠습니다.
void SelectionSort(int *arr, int len){
 
    int min_idx;
    for(int i=0; i<len-1; i++){
        min_idx = i;
 
        for(int j=i+1; j<len; j++){
            if(arr[min_idx] > arr[j]){
                min_idx = j;
            }
        }
        Swap(arr[min_idx], arr[i]);
    }
 
}
 
int main(void){
 
    int arr[5= {35124};
    int len = 5;
 
    for(int i=0; i<len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
 
 
    SelectionSort(arr, len); //선택정렬 호출
 
    for(int i=0; i<len; i++){
        cout << arr[i] << " ";
    }
 
    return 0;
}
cs


>결과


2. 시간 복잡도


다음 시간에는 퀵 정렬(Quick Sort)에 대해 포스팅 하겠습니다.

반응형