[알고리즘] 삽입 정렬 알고리즘

동현·2020년 10월 10일

정렬은 자료 탐색에서 매우 중요한 알고리즘이다. 국어사전을 예로 들어보자 만약 국어사전이 가나다 순으로 오름차순이나 내림차순 정렬이 되어 있지 않다면 단어를 빨리 찾는 것은 매우 어려울 것이다. 정렬 알고리즘은 여러 가지가 있지만 이번에 다룰 알고리즘은 삽입 정렬 알고리즘이다.

1. 삽입 정렬 알고리즘이란?

삽입 정렬 알고리즘은 값 하나하나를 올바른 위치에 삽입하는 형식의 알고리즘이다. 예를 들어 정렬이 된 부분과 정렬이 안 된 부분이 있다면 정렬이 되지 않은 부분의 첫번째 값을 정렬된 부분의 올바른 자리에 삽입하는 알고리즘이다. 마치 우리가 카드 게임을 할 때 새로운 카드를 받을 때마다 올바른 위치에 끼어넣는 것과 비슷하다.

검정색으로 표시한 부분은 정렬이 완료된 부분, 남색 부분은 정렬이 안된 부분이다. 매 스캔마다 정렬이 안된 부분(남색)의 첫번째 값(하늘색)을 정렬이 된 부분(검정색)의 올바른 위치에 삽입하는 것을 볼 수 있다.

2. 소스 코드 구현

구현하는 데 사용한 언어는 C++이다.

void insertion_sort(int* arr, int n) {
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}	// 새로 삽입할 숫자가 앞 숫자보다 작을 경우 한 칸씩 밀어서 삽입
		arr[j + 1] = key;
	}
}

key의 경우 매 스캔마다 정렬할 값이 되고 j의 경우 정렬이 완료된 부분의 맨 마지막 인덱스를 가리킨다. 정렬이 완료된 부분의 마지막부터 시작해서 key값이 더 작을 경우 한 칸씩 뒤로 민다음, 올바른 위치에 key값을 삽입하는 방식이다.

#include <iostream>
using namespace std;

void print_array(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

void insertion_sort(int* arr, int n) {
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}	// 새로 삽입할 숫자가 앞 숫자보다 작을 경우 한칸씩 밀어서 삽입
		arr[j + 1] = key;
	}
}

int main() {
	int arr[6] = { 3, 4, 1, 5, 9, 7 };
	cout << "정렬 전 -> ";
	print_array(arr, 6);

	cout << "정렬 후 -> ";
	insertion_sort(arr, 6);
	print_array(arr, 6);

	return 0;
}