1. 선택 정렬

< 선택 정렬 >

: 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 (효율↓)

 

#include <stdio.h>
int main(void) {
	int i , j, min, index, temp; 
    //index = 가장작은 원소가 존재하는 위치
    //temp = 특정한 두 숫자를 서로 바꾸기 위해서
    
    int array[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 > array[j]) {
            		min = array[j];
                	index = j;
            }
        }
        
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
        //스와핑
    }
    
    
    for(i = 0; i < 10; i++) {
    	printf("%d\n", array[i]);
     }
    
    return 0;
}

 

temp = array[i];

array[i] = array[index];

array[index] = temp;

// 스와핑 // 가장 앞에 있는 것과 최솟값을 바꿔주겠다.

---

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

→ 10 * ( 10 + 1 ) / 2 = 55번의 비교 연선

→ N * ( N + 1 ) / 2

→ N * N

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