삽입 정렬(Insertion sort)
새로운 레코드를 i개의 정렬된 레코드 리스트에 끼워넣어 크기가 i+1로 정렬된 결과 레코드 리스트를 만드는 것이다.
즉, a[0]을 사용하면 리스트 끝 검사(즉, i<1)를 생략할 수 있게 해 while 루프를 간단하게 한다.
즉, a[0]을 사용하면 리스트 끝 검사(즉, i<1)를 생략할 수 있게 해 while 루프를 간단하게 한다.
삽입 정렬은 순서 순차 a[1]에서부터 시작하여 a[2], a[3], .... , a[n]을 연속적으로 삽입한다.
매번 삽입의 결과가 정렬된 리스트가 되기 때무에 n개의 레코드를 가진 리스트는 n-1번 삽입함으로써 정렬할 수있다.
정렬된 리스트로 삽입
void insert(element e, element a[], int i)
{/*배열의 최소 크기는 i+2*/
a[0] = e;
while (e.key < a[i].key)
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = e;
}삽입 정렬
void insertionSort(element a[], int n)
{/* a[1:n]을 비감소 키 순서대로 정렬*/
for (int j = 2; j <= n; j++) {
element temp = a[j];
insert(temp, a, j - 1);
}
}
예시 문제
1. 주어진 데이터를 읽어 Insertion Sort 수행하라.
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
N R 1,1 R 1,2
R 2,1 R 2,2
…
R N,1 R N,2
N: Record의 갯수이며, N≤1000라 가정한다.. Ri, j 는 정수이며, i번째 Record의 j번 field를 나타낸다.
2) Insertion Sort를 이용하여 두개의 Key(K 1 , K 2 )에 대해 각각 오름 차순으로 정렬한다.
입력값
input.txt
8
-1 5
31 4
95 -9
82 3
1984 124
-78 -42
0 -154
525 195
코드
/*
Description : Insertion Sort 구현
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct array
{
int key1;
int key2;
}array;
void open();
void InsertSort_key1(array arr[], int n);
void InsertSort_key2(array arr[], int n);
void Printarr(array [],array []);
void Init(array[], array[]);
array *matric;
int N;
int main(void)
{
open();
array *temp1,*temp2;
temp1 = (array*)malloc(sizeof(array) * N);
temp2 = (array*)malloc(sizeof(array) * N);
Init(temp1, temp2); //초기화
printf("Insertion Sort\n");
InsertSort_key1(temp1, N);
InsertSort_key2(temp2, N);
Printarr(temp1,temp2);
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d", &N);
matric = (array*)malloc(sizeof(array) * N);
int i = 0, j = 0;
while (fscanf(fp, "%d %d", &matric[i].key1,&matric[i].key2) != EOF)
i++;
fclose(fp);
}
void Init(array *temp1,array *temp2) //초기화
{
for (int i = 0; i < N; i++)
{
temp1[i] = matric[i];
temp2[i] = matric[i];
}
}
void InsertSort_key1(array arr[], int n) //key1 값을 기준으로
{
int i, j;
array key;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j].key1 > key.key1) //자리바꿈
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void InsertSort_key2(array arr[], int n) //key2 값을 기준으로
{
int i, j;
array key;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j].key2 > key.key2)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void Printarr(array arr[],array arr2[])
{
printf("Key : K1\n");
for (int i = 0; i < N; i++)
printf("%d %d\n", arr[i].key1,arr[i].key2);
printf("\nKey : K2\n");
for (int i = 0; i < N; i++)
printf("%d %d\n", arr2[i].key1, arr2[i].key2);
}출력 값
정렬 관련 알고리즘