[알고리즘] 삽입정렬(Insertion Sort)

오늘은 삽입정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다.

 

오름차순으로 정렬하기 위해서는 정렬할 값과 정렬된 배열의 끝(가장 큰 수)부터 차례대로 비교해가면서 알맞은 자리에 삽입하면 됩니다.

정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다.

처음에는 인덱스가 0인 부분만 정렬된 상태이고 그 뒤의 숫자는 정렬되지 않은 즉, 정렬할 값이라고 생각하면 됩니다.

 

배열 위의 화살표는 현재 삽입정렬을 할 숫자이고, 배열 밑의 화살표는 삽입정렬 수행 시 비교하는 숫자들과 연결한 것입니다. 

현재 삽입정렬를 할 숫자를 key라고 부르겠습니다.

반복문을 돌면서 정렬된 부분(보라색 부분)의 숫자가 key값보다 크면 뒤로 한칸씩 밀어주고,

만약 정렬된 부분(보라색 부분)의 숫자가 key값보다 작거나, 배열의 맨 앞부분(인덱스가 0)까지 왔다면 반복문을 탈출합니다. 탈출하는 시점이 key의 알맞은 자리입니다.

그 후, 알맞은 자리에 key를 삽입하면 됩니다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void insertionSort(int* arr) {
	int temp;
	for (int i = 1; i < 5; i++) {
		temp = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > temp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
}

void main() {
	int num[5] = { 4,2,1,5,3 };
	insertionSort(num);
	for (int i = 0; i < 5; i++) {
		printf("%d\n", num[i]);
	}
}