[삽입 정렬]
[ 삽입 정렬이란 ]
데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 적당한 곳에 삽입하여 정렬해 나가는 알고리즘 .
[ 정렬과정 ]
오름차순 정렬임을 가정했을때 삽입 정렬은 다음의 순서로 이루어 진다 .
- 데이터 집합에서 정렬 대상이 되는 요소를 선택한다 . 정렬 대상은 왼쪽 부터 선택, 범위는 2개에서 시작하여 알고리즘 반복 횟수가 늘어날때마다 1개씩 커진다 . ( 정렬 대상의 최대 범위는 데이터 집합의 크기 -1 )
- 정렬 대상 가장 오른쪽의 값이 가장 큰 값을 가지고 있는지 확인한다 . 아니라면 해당 요소를 뽑아 적절한 위치 (가장 왼쪽을 기준으로 했을때 더 작은 요소가 없는 위치)를 찾는다 .
- 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동 ,빈자리에 삽입
- 정렬의 완료까지 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;
}
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 정렬 - 05 . qsort (0) | 2023.02.18 |
---|---|
[ 자료구조 ] 정렬 - 04 . 퀵 정렬 (0) | 2023.02.17 |
[ 자료구조 ] 정렬 - 02 . 버블 정렬 (0) | 2023.02.13 |
[ 자료구조 ] 정렬 - 01 . 정렬 알고리즘 (0) | 2023.02.13 |
[ 자료구조 ] 트리 - 04 . 분리 집합 (0) | 2023.02.11 |