[알고리즘] 삽입 정렬

삽입 정렬

: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

 

C언어 구현

ver1.

void insertionSort(int A[], int n) {
	int key, index;
	for (int i = 1; i < n; i++) {
		key = A[i];
		for (int j = i - 1; j >= 0; j--) {
			if (A[j] > key) {
				A[j + 1] = A[j];
			}
			else {
				index = j + 1;
				break;
			}
		}
		A[index] = key;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", A[i]);
	}
}

 

ver2.

void insertionSort2(int A[], int n) {
	for (int i = 1; i < n; i++) {
		int key = A[i];
		int index = i;
		for (int j = i - 1; j >= 0; j--) {
			if (A[j] > key) {
				A[j + 1] = A[j];
				index = j;
			}
		}
		A[index] = key;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", A[i]);
	}
}

 

ver1은 키값이 배열 요소값보다 클때에만 인덱스값만 확인해서 바로 for문을 빠져나오고, 확인한 인덱스 다음 자리에 삽입한다.

ver2은 키값이 배열 요소보다 작을 때, 즉 계속 자리를 탐색해야 하는 경우 그때그때마다 index값을 업데이트해주어야함.

 

ver1, ver2 모두 key값 이전 인덱스부터 탐색

 

void insertionSort3(int A[], int n) {
	int key, index, j;
	for (int i = 1; i < n; i++) {
		key = A[i];
		j = i;
		while ((j > 0) && (A[j - 1]) > key) {
			A[j] = A[j - 1];
			j--;
		}
		A[j] = key;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", A[i]);
	}
}

ver3는 맨 앞부터 탐색