[C++] 삽입 정렬(Insertion sort) 알고리즘

오늘은 삽입 정렬 알고리즘을 C++ 을 이용하여 구현해보았다.

 

삽입 정렬 알고리즘은 두 번째 원소부터 검사를 하는데 현재 값과 이전 값을 이중 포문을 이용하여 검사 후 이전 값이 현재 값보다 더 크다면 오른쪽으로 이동하여  정렬을 진행한다.

 

#include <iostream>
#include <stdio.h>

void inser_sort(int ans[], int n) {
 int i, j, temp;

 for (i = 1; i < n; i++) // 두 번째 원소부터 검사
 {
	temp = ans[i]; // 현재값
	for (j = i - 1; j >= 0 && ans[j] > temp; j--) // 현재 값과 이전 값 비교 후 이전값이 더 크다면 오른쪽으로 이동
	{
		ans[j + 1] = ans[j];
	}
	ans[j + 1] = temp; // 반복문을 빠져나온뒤 현재 값을 저장
 }

}

int main() {
int n = 10;
int *arr = new int[n];
for (int i = 0; i < n; i++) {
	scanf("%d", &arr[i]);
}

inser_sort(arr, n); // 삽입 정렬 진행

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

delete[] arr;
return 0;
}

 

이중 for문을 이용하기때문에 시간복잡도가 O(N^2) 이 나온다.

 

음.. 요소 수가 많아진다면 시간복잡도가 커져서 효율적이진 못할 것같다. 모든 요소를 요소의 갯수만큼 검사해야하기 때문이다.