본문 바로가기
<개인공부>/[Algorithm]

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

by 사용자 BlockDMask 2017. 9. 24.
반응형

안녕하세요. 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)에 대해 포스팅 하겠습니다.

반응형

댓글3