[c언어 알고리즘] 선택 정렬 과 삽입 정렬

오늘은 선택정렬과 삽입정렬에 대해서 공부하겠습니다. 선택정렬과 삽입정렬 모두 시간복잡도가 O(n^2)입니다. 쉽게 설명하자면 이중반복문을 통해 구현하기 때문입니다. 그렇다면 이제 각각의 차이가 무엇인지 알아보도록 하겠습니다.

 

---

선택 정렬의 기본적인 아이디어는 리스트를 순회하면서 가장 작은 것을 제일 앞으로 보내는 방식입니다. 

# include <stdio.h>

void main(){
	int i, j, min, index, tmp;
    int array[10] = = { 2, 1, 4, 3, 5, 7, 6, 8, 9, 10 };
    for(i = 0; i<9; i++){
    	min = array[i];
        for(j=i+1;j<10;i++){
        	if(min>array[j]){
            	min = array[j];
                index = j;
            }
        }
        temp = array[i];
        array[i] = min;
        array[index] = temp;
    }
    for(i=0;i<10;i++){
    	printf("%d", array[i]);   
    }
    
    return 0;
}

삽입정렬의 기본적인 아이디어는 정렬된 리스트에서 다음 원소는 어디에 위치하지 삽입하는 것입니다.

 

 1   2   3   5   6   4 

 

이러한 배열인 상태에서 원소 4는 어떻게 정렬을 해야할지 컴퓨터의 사고방식으로 생각하겠습니다. 

우선 4에서부터 뒤로 순회하면서 각 원소와 비교를 하겠습니다. 

 

...   6   5

 

4가 더 작으므로 위치를 바꾼다고 생각하겠습니다. 다음으로 

 

...   5   4

 

4가 더 작으므로 위치를 바꾼다고 생각하겠습니다. 다음으로 

 

...   3   4

 

이제 4거 더 커서 위치를 바꾸지 않고 끝냅니다. 그러면 리스트의 결과는

 

 1   2   3   4   5   6 

 

이렇게 삽입정렬은 말 그대로 각 원소를 적절한 위치에 삽입을 하는 것입니다.

 

# include <stdio.h>

void main(){
	int i, j, tmp;
    int array[10] = = { 2, 1, 4, 3, 5, 7, 6, 8, 9, 10 };
    for(i = 0; i<9; i++){
    	
        j = i+1;
       
        while(array[j-1] > array[i+1]){
        	j-- ;
        
        }
        
        
        tmp = array[i+1];
        array[i+1] = array[j];
        array[j] = tmp;
    }
    for(i=0;i<10;i++){
    	printf("%d", array[i]);   
    }
    
    return 0;
}

삽입 정렬은 거의 정렬된 데이터 속에서 선택정렬에 비해 월등히 빠르다고 말할 수 있습니다. 거의 정렬된 데이터에서는 비교할 연산 수 가 적기 때문입니다.