[C++][구현] 삽입정렬 (Insertion Sort)

⭐ 삽입 정렬

 

오름 차순으로 정렬을 한다고 할 시에, (1 -> lenght 순서로 가는 k) k번째 까지는 이미 정렬이 되어 있다고 생각을 하고, 

 

k+1 번째 값을 정렬된 곳에 삽입해주려는 정렬 방식입니다.

 

k번째 까지는 이미 정렬이 되어 있기에 큰 값부터 비교해가며 딱 알맞은 곳에 삽입해줘야 합니다.

 

#include <iostream>
using namespace std;

void insertSort(int nums[], int length) {

	for (int i = 1; i < length; i++) {

		int tmp = nums[i];
		int Idx = i - 1;

		while (Idx >= 0 && tmp < nums[Idx]) {
			nums[Idx + 1] = nums[Idx];
			Idx--;
		}
		nums[Idx + 1] = tmp;
	}
}

 

시간 복잡도는 O(N^2) 이고, Stable한 정렬기법 입니다.