(C/C++) 정렬 - 삽입 정렬(Insert Sort) - 안정성 O, O(N²)

안녕하세요.

오늘은 삽입 정렬과 간접 삽입 정렬에 대해서 알아보도록 하겠습니다.

 

1. 삽입 정렬(Insert Sort)이란?

이미 정렬된 부분에 키를 삽입하는 동작을 반복하는 정렬입니다.

배열이 있다고 했을때 루프문을 돌수록 왼쪽에 있는 값들은

1 2 7 8 이런식으로 정렬이 되고 5 라는 값이 나왔을때 1 2 5 7 8

이런식으로 정렬되어 있는 값 사이에 삽입 된다 하여 붙여진 이름입니다.  

 

2. 삽입 정렬의 특징

적은 비교, 많은 교환

안정성 O

O(N²) 의 시간복잡도

많은 교환을 하기 때문에 큰 자료형일수록 부담이 크다. (간접 정렬을 고려해볼만 하다.)

정렬되어 있을수록 빠르고 역순일 경우 상대적으로 느리다.

역순일 경우 느리다는 단점을 보완한 쉘 정렬 - 안정성 X, O(n^1.5)이 있디.

선택 정렬과 함께 많이 쓰이는 정렬 중에 하나

 

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 삽입 정렬의 구현

 

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

void InsertSort(int _arrays[], int _arraysLength);	//삽입 정렬 함수
void PrintArray(int _arrays[], int _arraysLength);	//배열 출력 함수

void InsertSort(int _arrays[], int _arraysLength)
{
	for (int i = 1; i < _arraysLength; i++)
	{
		int temp = _arrays[i];			//루프문을 많이 돌 거기 떄문에 따로 temp 에다가 값을 기록한다.
		int j = i;
		while (j > 0 && _arrays[j - 1] > temp)	//>= 를 사용하면 안정성이 깨진다. >= 를 사용하면 제일 뒤에 있던 같은값이 제일 앞으로 온다.
		{					
			_arrays[j] = _arrays[j - 1];
			j--;
		}
		_arrays[j] = temp;
	}
}

void PrintArray(int _arrays[], int _arraysLength)
{
	for (int i = 0; i < _arraysLength; i++)
	{
		printf("%d\t", _arrays[i]);
	}
	printf("\n");
}

int main()
{
	int SampleArray[] = { 5,2,3,4,8,7,9,6,1 };

	PrintArray(SampleArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
	printf("\n");

	InsertSort(SampleArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
	PrintArray(SampleArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
}

삽입 정렬 결과

Sample 배열이 정렬

 

4. 간접 삽입 정렬 구현

 

간접 삽입 정렬이란?

기본 배열은 전혀 건들지 않고 따로 만든 인덱스 배열의 값을 수정하는 방법 입니다.

위에서 자료형이 클수록 부담이 있다고 하였는데

그 부담을 줄이기 위해서 간접 정렬을 활용할 수 있습니다.

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

void IndirectInsertSort(int _arrays[], int _indexArrays[], int _arraysLength);		//간접 삽입 정렬 함수
void IndirectPrintArray(const int _arrays[], int _indexArrays[], int _arraysLength);	//간접 배열 출력 함수

void IndirectInsertSort(const int _arrays[], int _indexArrays[], int _arraysLength)	//기본 배열은 수정되면 안되기 떄문에 const
{	
	for (int i = 0; i < _arraysLength; i++)
	{
		_indexArrays[i] = i;							//먼저 index 값 초기화
	}

	for (int i = 1; i < _arraysLength; i++)
	{
		int temp = _indexArrays[i];
		int j = i;

		while (j > 0 && _arrays[_indexArrays[j - 1]] > _arrays[temp])		//j > 0 이 앞에 있는 이유는 j 가 0일때 array의 0 - 1 번째 배열에 접근 할수 없기 때문에
		{									//배열 인덱스는 그 값이 벗어 났는지 먼저 검사해주어야 한다.
			_indexArrays[j] = _indexArrays[j - 1];
			j--;
		}
		_indexArrays[j] = temp;
	}
}

void IndirectPrintArray(int _arrays[], int _indexArrays[], int _arraysLength)
{
	for (int i = 0; i < _arraysLength; i++)
	{
		printf("%d\t", _arrays[_indexArrays[i]]);
	}
	printf("\n");
}

int main()
{
	int SampleArray[] = { 5,2,3,4,8,7,9,6,1 };
	int IndexArray[sizeof(SampleArray) / sizeof(SampleArray[0])];		//sizeof 연산자는 컴파일 시에 상수로 바뀌기 때문에 사용할수 있다.

	PrintArray(SampleArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
	printf("\n");

	IndirectInsertSort(SampleArray, IndexArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
	IndirectPrintArray(SampleArray, IndexArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
	printf("\n");

	PrintArray(SampleArray, sizeof(SampleArray) / sizeof(SampleArray[0]));
}

간접 삽입 결과

Sample 배열은 그대로

Index 배열이 정렬됨

 

감사합니다.

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)