선택정렬

의미>

1부터 10까지의 배열이 무작위로 있을 때 10개를 대상으로 가장 작은 것을 골라 맨 앞과 위치 스위칭. 그리고 맨 앞에 간 가장 작은 것은 제쳐두고 나머지 9개를 대상으로 전체 검색을 하여 그 중 가장 작은 것을 맨 앞으로 스위칭.

이런 식으로 "비교-> 특정-> 위치 스위칭 -> 제껴두고 나머지들을 대상으로 다시 비교-> 특정-> 스위칭" 하는 것을 선택정렬이라고 함. '선택'인 이유는 대상을 특정해서 이를 선택하여 위치를 바꾸는데에서 '선택'이라는 명칭이 발생.

 

코드예시>

#include <stdio.h>



int main(void){

    

    int array[10] = {9, 5, 6, 8, 3, 7, 10, 2, 4, 1};

    int i, j, index, min, temp;

    

    for(i = 0; i < 10; i++){

        

        min = 100;

    

     //for(j = i; j < (10-i); j++){

     for(j = i; j < 10; j++){

            if(array[j] < min){

                min = array[j];

                index = j;              

            }

            

     }

        

        temp = array[i];

        array[i] = array[index];

        array[index] = temp;            

        

    }



    for(i = 0; i < 10; i++){

        printf("%d ", array[i]);

    }

    

    return 0;

}

​​

시간복잡도>

N(N+1)/2

-> N^2/2 + N/2

-> N^2/2

-> N^2

= O(N^2)