[ 자료구조 ] 정렬 - 03 . 삽입 정렬

[삽입 정렬]

[ 삽입 정렬이란 ]

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 적당한 곳에 삽입하여 정렬해 나가는 알고리즘 .

 

[ 정렬과정 ]

오름차순 정렬임을 가정했을때 삽입 정렬은 다음의 순서로 이루어 진다 .

1. 데이터 집합에서 정렬 대상이 되는 요소를 선택한다 . 정렬 대상은 왼쪽 부터 선택, 범위는 2개에서 시작하여 알고리즘 반복 횟수가 늘어날때마다 1개씩 커진다 . ( 정렬 대상의 최대 범위는 데이터 집합의 크기 -1 )
2. 정렬 대상 가장 오른쪽의 값이 가장 큰 값을 가지고 있는지 확인한다 . 아니라면 해당 요소를 뽑아 적절한 위치         (가장 왼쪽을 기준으로 했을때 더 작은 요소가 없는 위치)를 찾는다 .
3. 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동 ,빈자리에 삽입
4. 정렬의 완료까지 1 ~3 을 반복한다 .

예제) 5 ,1 ,6 , 4, 2 , 3 을 정렬해보자

[삽입 정렬의 속도]

[ 삽입 정렬 속도 ]

앞의 예제는 크기가 6인데 정렬을 위한 반복은 5회 수행한다 .

데이터 집합 내 요소들간의 비교는 2개일때 1번 , 3개일때 한번이다 . 이를 공식으로 유도하자면

 

1+2+ .. (n-1) => n(n-1)/2 로 간소화 할 수 있다 . 버블정렬과 같음을 볼 수 있다

 

다만 , 버블정렬과 다르게 삽입 정렬은 데이터 집합이 정렬되어 있다면 한번도 비교를 거치지 않을 수 있다 . 

최선의 경우는 (n-1) 최악의 경우(역으로 정렬)는 n(n-1)/2 이다 . 둘의 평균을 구했을때 나오는 값인 ((n*n)+n-2)/2 회를 생각해보면 버블 정렬과 삽입 정렬은 같은 성능을 가진것 같지만 평균적으로는 삽입 정렬이 더 나은 성능을 보인다 .

 

따라서 비교적 크기가 작은 데이터 집합을 정렬한다면 버블 보다는 삽입을 권하는 편이다 .

 

[삽입 정렬의 구현]

[ 구현 ]

#include<stdio.h>
#include<string.h>

void InsertSort(int Data[], int Length)
{
	for (int i = 1; i < Length ; i++)
	{
		int value = 0;
		//올바른 정렬이라면 넘긴다
		if (Data[i - 1] < Data[i])
			continue;

		value = Data[i];

		//올바른 위치를 찾을때까지
		for (int j = 0; j < i; j++)
		{
			//올바른 위치를 찾았다면
			if (Data[j] > value)
			{
				//배열을 한칸씩 밀어준다 이때 size는 미는 배열만큼
				memmove(&Data[j + 1], &Data[j], sizeof(Data[0]) * (i - j));
				Data[j] = value;
				break;
			}
		}
	}
}

int main(void)
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof DataSet / sizeof(DataSet[0]);
	int i = 0;

	InsertSort(DataSet, Length);

	for (int i = 0; i < Length; i++)
	{
		printf("%d\t", DataSet[i]);
	}
	return 0;
}