[알고리즘] 선택 정렬 (Selection Sort)

예를 들어

*1 10 5 8 7 6 4 3 2 9 *

라는 숫자들을 오름차순으로 정렬하려고 한다고 가정해보자

 

 

사람이라면 직관적으로 보고 작은 수 를 찾아 순서대로 정렬하겠지만,

컴퓨터는 배열을 하나하나 읽기전 까지는 어떤 값이 들어있는지 알지 못한다.

따라서 정렬을 위해서는 알고리즘이 필요하다.

 

 

그 중에서도 선택정렬은 모든 배열을 탐색 후, 가장 작은 수를 앞으로 보내는 방식으로 동작한다.

---

ex)

arr[10]

 

*1 10 5 8 7 6 4 3 2 9 *

 

모든 배열을 탐색 후 , 1이 가장 작은 숫자로 알맞은 위치에 있으므로,

이제는 1을 제외한 10 부터 9까지를 탐색해준다.

 

*1 2 5 8 7 6 4 3 10 9 *

 

나머지 배열중에 가장 작은 수는 2이므로 arr[1] 인덱스의 값으로 넣어주고 원래 2라는 값이 있던

인덱스 arr[8]에는 10을 넣어 자리를 바꿔준다.

이런식으로 오름차순이 완성될때 까지 반복 해주면 된다.

---

예제와 같은 식으로 반복 한다면

처음 1 부터 10 까지 10 번을 연산

그 다음엔 이미 정렬된 1을 제외한 9번을 연산

정렬된 1과 2 를 제외한 8번......... 반복하다보면

 

등차수열의 합

n: 항의 갯수

a: 등차 수열의 첫째 항

l : 끝항

 

$$S_{n} = n(a+l) / 2$$

 

등차수열의 합 공식에 따라서 10 * (10 + 1) /2 => 55 가 되고 

수식으로 작성하면 n*(n+1) /2 여서

Big O 표기법으로 시간 복잡도는  O(n^2) 이 된다.

 

이차 함수의 그래프를 생각 해보았을때 

 

x 축을 데이터 y 축을 시간 이라고 한다면 ,

데이터 양이 증가할수록↑ 시간 역시 늘어나기 때문에 ↑

데이터 양이 많을땐 효율적인 알고리즘이라고 하기 힘들다.

#include <stdio.h>

int main(void)
{
    int i,j,min,index,temp;
    int arr[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i = 0; i < 10; i++) //비교할 기준 인덱스
    {
        min = 9999;
        for(j = i; j < 10; j++) //나머지 인덱스와 비교 
        {
            if(min > arr[j])
            {
                min = arr[j];
                index = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;

    }

    for(i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}