삽입 정렬(Insertion Sort)

이재원·2024년 12월 16일

알고리즘

목록 보기

10/15

삽입 정렬

삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 주로 데이터 양이 적거나 거의 정렬된 경우에 적합하다. 삽입 정렬은 배열의 요소를 하나씩 순회하며, 현재 요소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작한다.

작동 원리

초기 설정: 첫 번째 요소는 이미 정렬된 상태로 간주한다.
반복 과정

두 번째 요소부터 시작해서 배열의 끝까지 각 요소를 순회
현재 요소를 그보다 앞쪽에 있는 정렬된 부분과 비교하여 올바른 위치에 삽입

완료: 모든 요소를 정렬된 위치에 삽입하면 작업이 종료된다.

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

void insertion_sort(int list[], int n) {
	int i, j, key;
	for (i = 1; i < n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j] > key; j--)
			list[j + 1] = list[j]; // 레코드의 오른쪽 이동
		list[j + 1] = key;
	}
}

int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) 
		list[i] = rand() % 100;

	insertion_sort(list, n);
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}