삽입 정렬

삽입 정렬

삽입 정렬은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 윧지되게 한다. 이와 같은 작업을 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.

삽입 정렬은 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 선택 정렬과 마찬가지로 입력 배열을 선택 정렬과 유사하게 입력배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 사용하면 된다.

void insertion_sort(int list[], int n){
	int i, j, key;
	for(i = 1; i < n; i++){
		key = list[i];
		for(j = i - 1; j >= 0 && list[j] > key; j--){
			list[j + 1] = list[j];
		list[j + 1] = key;
	}
}

삽입 정렬의 복잡도

삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 먼저 입력 자료가 이미 정렬되어 있는 경우는 가장 빠르다. 삽입 정렬의 외부 루프는 n - 1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교횟수는 n - 1번, 총 이동횟수는 2(n - 1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다.

버블 정렬

버블정렬은 인전합 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) 
void bubble_sort(int list[], int n) {
	int i, j, temp; 

	for(i=n-1; i>0; i--){
		for(j=0; j<i; j++) 
			if(list[j]>list[j+1]) // 앞뒤의 레코드를 비교한 후 교체
				SWAP(list[j], list[j+1], temp);
	}
}