삽입 정렬 (Insertion Sort)

삽입 정렬 : 삽입 정렬은 리스트를 순회하면서 각 원소를 적절한 위치에 삽입하여 정렬된 부분 리스트를 점진적으로 확장하는 방식으로 작동합니다.

 - 시간 복잡도

        Best   : O(n)

        Worst : O(n^2) 

 - 삽입 정렬은 추가적인 메모리를 거의 사용하지 않기 때문에 제자리 정렬(In Place Sort, O(1)의 공간 복잡도)입니다.

 - 삽입 정렬은 입력 순서를 보장하는 안정 정렬(Stable Sort)입니다.

 

오름차순 예시

 

struct Num
{
	int idx;
	int num;

	Num(int idx, int num)
		: idx(idx), num(num) {};
};

void AscendingInsertionSort(vector<Num>& arr)
{
	for (int i = 1; i < arr.size(); ++i)
	{
		Num key = arr[i];

		int j;
		for (j = i - 1; j >= 0; --j)
		{
			if (arr[j].num > key.num)
			{
				arr[j + 1] = arr[j];
			}
			else
				break;
		}

		arr[j + 1] = key;
	}
}

void DscendingInsertionSort(vector<Num>& arr)
{
	for (int i = 1; i < arr.size(); ++i)
	{
		Num key = arr[i];

		int j;
		for (j = i - 1; j >= 0; --j)
		{
			if (arr[j].num < key.num)
			{
				arr[j + 1] = arr[j];
			}
			else
				break;
		}

		arr[j + 1] = key;
	}
}

int main(void)
{
	srand(static_cast<unsigned int>(time(NULL)));
	vector<Num> v1;
	vector<Num> v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(Num(i, rand() % 6));
		v2.push_back(Num(i, rand() % 6));
	}

	cout << "오름차순 정렬 전 : ";
	PrintVector(v1);
	AscendingInsertionSort(v1);
	cout << "오름차순 정렬 후 : ";
	PrintVector(v1);
	cout << "정렬 후 idx \t : ";
	printVectorIdx(v1);
	
	cout << endl;

	cout << "내림차순 정렬 전 : ";
	PrintVector(v2);
	DscendingInsertionSort(v2);
	cout << "내림차순 정렬 후 : ";
	PrintVector(v2);
	cout << "정렬 후 idx \t : ";
	printVectorIdx(v2);

	return 0;
}

 

결과