[알고리즘] 삽입 정렬 구현 (c언어)

---

🌿삽입정렬이란?

기본 정렬 알고리즘 중 하나이며, KEY를 선택후 배열의 값들과 비교해가며 삽입을 할지 안할지 결정한다.

 

최적의 경우 -> 이미 정렬된 배열에서는 O(n)의 시간복잡도를 가진다.

 

최악의 경우 -> O(n^2)의 시간 복잡도를 가진다.

---

🌿최적의 경우가 O(n)인 이유

다른 기본 정렬알고리즘들과는 다르게 삽입 정렬은 정렬된 배열에서 O(n)을 가지는데

void insertion_sort(int* arr, int size) {
	int i, j, key;
	for (i = 1; i < size; i++) {
		key = arr[i];  
		for (j = i - 1; j >= 0 && arr[j] > key; j--) { //***여기 부분때문에 최적의 경우 O(n)을 가짐!
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = key;
	}
}

 

 for문 조건에 arr[j] > key가 있기 때문에 이미 정렬된 배열에서는 for문을 탈출하는 것이다.

---

🌿코드 및 작동방식

arr[5]  = {5, 3, 4, 2, 1} 인 배열을 정렬 시킨다고 가정하자.

 

⭐코드는 다음과 같다!

#include <stdio.h>

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

int main()
{
	int arr[5] = { 5, 3, 4, 2, 1 };

	printf("정렬 전\n");
	for (int i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}

	insertion_sort(arr, 5);

	printf("\n정렬 후\n");
	for (int i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
}

 

 

⭐루프에 따라 작동하는 방식을 그림으로 알아보자

- 1번째 루프(key = 3일때)

- 2번째 루프(key = 4)일때

- ..... 이걸 배열의 크기만큼 반복하면 오름차순 정렬이 완성된다.

---

🌿실행