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

안녕하세요. BlockDMask 입니다. 

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

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

0. 원리

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

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

  

  
  

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

1. 코드 및 결과

> 코드(C++)

//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] = {3, 5, 1, 2, 4};
    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;
}

>결과

2. 시간 복잡도

= 

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