[C언어 소스] 삽입 정렬(Insertion Sort) 알고리즘
삽입 정렬 (Insertion Sort)
이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다.
삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다.
삽입 정렬(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
아니면
루프 탈출
삽입정렬
삽입 정렬(Insertion Sort) 알고리즘.c//삽입 정렬(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");
}
자세히 보기