[Algorithm] 선택 정렬(Selection Sort)

선택 정렬이란?

가장 작은 것을 선택하여, 계속해서 앞으로 보내주는 방법(원래 앞에 있던 숫자와 자리를 바꿔줌)

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void){
    int i, j; // 배열의 요소들을 반복적으로 탐색하기 위함
    int min; // 최소 값
    int index; // 가장 작은 값이 존재하는 위치
    int temp; // 서로 다른 두 숫자를 바꿔주기 위해 사용 

    int array[10] = {1,6,9,8,2,4,10,3,7,5}; // 정렬할 배열

    for(int i=0;i<10;i++){
        min = 10000; // 모든 원소들 보다 큰 임의의 수 
        for(j=i;j<10;j++){ 
            // 정렬 되지 않은 나머지 부분에서 가장 작은 값 찾기 
            if(min > array[j]){
                min = array[j];
                index = j;
            }
        }
        // 가장 작은 값이랑 원래 앞에 있던 값이랑 자리 바꾸기 
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
    for(i=0;i<10;i++){
        cout << array[i] << endl;
    }
    return 0;
}

시간 복잡도

만약 10개의 요소가 담긴 배열을 선택 정렬을 사용하여 정렬할 땐, [처음 10번 + 9번 + 8번 + 7번 + 6번 + ... + 1번] 즉, 등차수열이다.

즉 N개의 요소를 선택정렬 할 때 필요한 수행시간은 [N * (N+1) / 2] 이다
만약, N이 엄청 큰 수일 경우, 더하기나 나누기 2 같은 경우 큰 의미가 없기 때문에 무시해 줄 수 있다.

즉, [N * N] 으로 나타낼 수 있다.

따라서 선택 정렬의 시간 복잡도는 O(N*N) 이다.

reference: https://www.youtube.com/watch?v=8ZiSzteFRYc&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=3&t=0s