02강 - 선택 정렬 (Selection sort)

알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 '정렬(Sort)' 문제이다.

=> 정렬만큼 알고리즘의 효율성 차이를 극명하게 보여주는 것이 없기 때문이다!!

---

먼저 선택 정렬 (Selection Sort) 알고리즘이다

 

 

[ 선택 정렬 ] 

가장 작은 것을 선택해서 제일 앞으로 보낸다

 

 

가장 원시적이고 기초적인 방법이다

수열의 앞부터 뒤까지 훑으면서 최소값을 앞으로 보낸다

그러면 한번 훑고 다음에 훑으면 배열이 앞에서부터 하나씩 줄어드는 것이다

이런식으로!

왜냐면 최소값이 맨 앞에 있으니까 맨 앞에 최소값을 제외하고 나머지 애들끼리 최소값 구해서 앞으로 보내면 되니까!

 

[ 코드 ]

 

아무튼 위 방법으로 코드를 구현하면 아래와 같다

#include <stdio.h>
#include <iostream>

using namespace std;

// 선택 정렬(selection sort)
int main()
{
    int array[10]={1,10,5,8,7,6,4,3,2,9};
    int index, temp;
    int min = 99999;
    for(int i=0;i<10;i++)
    {
        for(int 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(int i=0;i<10;i++)
    {
        printf("%d ", array[i]);
    }
    return 0;
}

위의 이중 반복문 중 안의 반복문에서는 최소값을 찾아서 min 변수에 저장하고, 최솟값을 찾은 후에는 배열 순서를 바꿔서 정렬해주는 것이다

 

 

[ 시간 복잡도 ]

이제 시간복잡도를 알아보자!

 

데이터의 갯수가 N개라고 해보자

선택 정렬은 비교 연산을 대략 N*(N+1)/2번 정도 수행하게 된다

그럼 O(N^2)이다!

 

선택 정렬의 시간 복잡도는 O(N^2)이다

 

 

---

 

총평 : 가장 기초적이고 구현하기는 쉽지만 그닥 효율적은 알고리즘은 아니다😅