삽입 정렬 (Insertion Sort)

 삽입 정렬이란 자료 구조를 순차적으로 순회하면서 순서에 어긋나는 요소를 찾고, 그 요스를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘입니다.

삽입 정렬 구조 예시

 

 위는 구조에 대한 예시를 그림으로 설명하는 겁니다. 왼쪽부터 오른쪽 방향으로 데이터를 읽어나가다 수가 작은 값을 왼쪽으로 옮기고 큰 값을 오른쪽으로 옮기는 형태를 취하고 있습니다. 

#include <stdio.h>
#include <stdlib.h>		// srand, rand
#include <time.h>		// time(NULL)

#define MAX_LEN 10


// _startIdx 부터 _endIdx 까지를 한 칸씩 이동
void LeftMove(int* _pArr, int _startIdx, int _endIdx);
void InsertionSort(int* _pArr);


void main()
{
	// 삽입정렬(Insertion Sort)
	// 시간으로 랜덤시드 설정
	srand(time(NULL));

	// 정적배열 생성
	int arr[MAX_LEN] = { 0 };
	// 랜덤 값으로 배열 초기화
	for (int i = 0; i < MAX_LEN; ++i) {
		arr[i] = rand() % 100;
		printf("[%d] - ", arr[i]);
	}
	printf("(%d)\n", MAX_LEN);

	printf("\n");
	InsertionSort(arr);
	printf("\n");

	for (int i = 0; i < MAX_LEN; ++i)
		printf("[%d] - ", arr[i]);
	printf("(%d)\n", MAX_LEN);
}


void InsertionSort(int* _pArr)
{
	if (_pArr == NULL) return;


	// 배열 전체 갯수 보다 하나 모자르게 순회
	// 마지막 하나가 남은 상황에서는 이미 정렬이 끝났기 때문
	for (int k = 0; k < MAX_LEN - 1; ++k)
	{
		// 키로 선택 된 값이 저장된 인덱스
		int keyIdx = 0;
		// 자리를 마련하기 위해 값들을 왼쪽으로 이동시키면
		// 키값이 있던 자리도 덮어지기 때문에 키값 저장
		int keyValue = _pArr[keyIdx];

		// 키 다음 값 부터 비교 시작
		// 한 사이클이 끝나면 가장 끝 인덱스는 정렬이
		// 된 상황이기 때문에 사이클이 돌 때 마다 제외 가능
		for (int i = keyIdx + 1; i < MAX_LEN - k; ++i)
		{
			// 현재 키값 보다 큰 값을 발견 했다면,
			if (_pArr[i] > keyValue)
			{
				// 키값 보다 큰 자리 앞이 키값이 들어갈 자리이기 때문에
				// 키값이 있던 자리에서 부터
				// 키값 보다 큰 값이 있는 자리 전 까지를
				// 왼쪽으로 한 칸씩 이동
				LeftMove(_pArr, keyIdx, i);

				// 이동이 끝이 나면 해당 위치에 키값을 삽입
				_pArr[i - 1] = keyValue;

				// 삽입한 인덱스 다음 값을 키값으로 지정
				keyIdx = i;
				keyValue = _pArr[keyIdx];

				// 이후 끝에 도달할 때 까지 반복
			}
		}

		// 배열 끝에 도달한 키값은 마지막에 삽입을 해줘야 함
		LeftMove(_pArr, keyIdx, MAX_LEN - k);
		_pArr[MAX_LEN - k - 1] = keyValue;

		// 전체 출력
		for (int i = 0; i < MAX_LEN; ++i) {
			if (i >= MAX_LEN - k - 1)
				printf("[%d] - ", _pArr[i]);
			else
				printf(" %d  - ", _pArr[i]);
		}
		printf("(%d)\n", MAX_LEN);

		// 여기 까지가 한 사이클
	}
}

void LeftMove(int* _pArr, int _startIdx, int _endIdx)
{
	if (_startIdx < 0 ||
		_endIdx > MAX_LEN ||
		_startIdx > _endIdx) return;

	for (int i = _startIdx + 1; i < _endIdx; ++i)
		_pArr[i - 1] = _pArr[i];
}

 

끝