이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다.
삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다.
알고리즘
삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)
반복(i:=1; i<n ; i:= i+1)
반복(j=i; j>0 ; j:=j-1)
조건(compare (base [j-1], base [j]) < 0)
temp: = base [j-1]
base[j-1] = base [j]
base[j] = temp
아니면
루프 탈출
점근식 계산
이번에는 삽입 정렬 알고리즘 성능을 분석합시다.
삽입 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i에서 0까지 점점 감소하므로 최악일 때 비교를 i번 수행하고 교환도 i번 수행함을 알 수 있어요. 따라서 S(i) = 2n 이죠.
외부 반복문은 i가 1에서 n까지 순차적으로 증가하면서 내부 반복문을 수행합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(1) + S(2)+ … +S(n) 이죠.
따라서 T(n) = S(1) + S(2)+ … +S(n) = 2(1 + 2 + … + n)
따라서 T(n)= n(n+1) 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 삽입 정렬도 순차 정렬과 거품 정렬, 선택 정렬처럼 O(n^2)이네요.
하지만 앞에서부터 특정 위치까지 정렬 상태에서 삽입 정렬을 사용하면 다른 정렬 방식에 비해 뛰어난 성능을 발휘할 수 있습니다.
소스 코드
//삽입 정렬(Insertion Sort)
#include <stdio.h>
#define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환
void InsertionSort(int *base, int n);
int main(void)
{
int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
InsertionSort(arr, 10);
return 0;
}
void ViewArr(int *arr, int n);
void InsertionSort(int *base, int n)
{
int i, j;
ViewArr(base, n);//현재 상태 출력
for (i = 1; i<n; i++)//정렬할 범위를 확대해 나갑니다.
{
for (j = i; j>0; j--)
{
if (base[j - 1]>base[j])//앞쪽 원소가 더 크면
{
SWAP(base[j - 1], base[j]);//교환
ViewArr(base, n);//상태 출력
}
else
{
break;
}
}
}
}
void ViewArr(int *arr, int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
//https://ehpub.co.kr
//[언제나 C언어] 삽입 정렬(Insertion Sort) [예제 Center]
#pragma warning(disable:4996)
#include
#include
#include
#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))
#define SWAP(i, j) {int t; t=i; i=j; j=t;}
#include
enum Color
{
LACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY,
LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE
};
void changecolor(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void View2(int *base, int n,int i,int j,int r)
{
int s = 0;
for (s = 0; s < n; s++)
{
if (s <= i)
{
if (r == 0)
{
changecolor(PURPLE);
}
else
{
if (s == j - 1)
{
changecolor(YELLOW);
}
else if (s == j)
{
changecolor(GREEN);
}
else
{
changecolor(PURPLE);
}
}
}
else
{
changecolor(WHITE);
}
printf("%2d ", base[s]);
}
changecolor(WHITE);
if (r)
{
printf("SWAP %d %d", base[j - 1], base[j]);
}
printf("\n");
}
void InsertionSort2(int *base, int n)//삽입 정렬(base:시작 주소, n:원소 개수)
{
for (int i = 1; i < n; i++) // 반복( i :=1--->n)
{
for (int j = i; j > 0; j--)//반복(j: = i->0)
{
if (base[j - 1] > base[j])//조건(base[j - 1] > base[j])
{
View2(base, n, i, j, 1);
Sleep(1000);
SWAP(base[j - 1], base[j]);//교환(base[j - 1], base[j])
}
else //아니면
{
break;//루프 탈출
}
}
View2(base, n, i, -1, 0);
Sleep(1000);
}
}
void View(int *base, int n,const char *msg)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%2d ", base[i]);
}
puts(msg);
}
void InsertionSort(int *base, int n)//삽입 정렬(base:시작 주소, n:원소 개수)
{
for (int i = 1; i < n; i++) // 반복( i :=1--->n)
{
for (int j = i; j > 0; j--)//반복(j: = i->0)
{
if (base[j - 1] > base[j])//조건(base[j - 1] > base[j])
{
SWAP(base[j - 1], base[j]);//교환(base[j - 1], base[j])
}
else //아니면
{
break;//루프 탈출
}
}
}
}
int main(void)
{
int arr[10] = { 9,4,3,0,5,8,7,6,2,1 };
View(arr, LENGTH(arr), "before");
getch();
InsertionSort2(arr, LENGTH(arr));
View(arr, LENGTH(arr), "after");
system("pause");
return 0;
}