삽입 정렬(Insertion Sort)

삽입 정렬

삽입 정렬(Insertion Sort)은 모든 요소를 이미 정렬된 부분과 비교하여 적절한 위치를 찾아 삽입하는 알고리즘입니다.

두 번째 원소부터 시작해서 앞에 있는 원소와 비교하고 앞에 있는 원소가 값이 더 크다면 뒤로 옮기고 적절한 위치에 원소를 삽입합니다.

두 번째 원소는 첫 번째 원소와 비교되고 세 번째 요소는 두 번째 요소와 첫 번째 요소, 네 번째 요소는 세 번째 요소와 두 번째 요소, 첫 번째 요소 이런 식으로 마지막 요소는 나머지 모든 원소와 비교되고 적절한 위치에 삽입된 뒤 정렬이 완료됩니다.

 

삽입 정렬 예시

 

삽입 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

	for (int i = 0; i < number; i++)
	{
		scanf("%d", &numbers[i]);
	}

	for (int i = 1; i < number; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (numbers[j] > numbers[j + 1])
			{
				Swap(&numbers[j], &numbers[j + 1]);
			}
		}
	}

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

정렬하려는 배열이 이미 정렬되어 있는 경우 반복문을 빠져나오도록 해서 알고리즘을 최적화시킬 수 있습니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

	for (int i = 0; i < number; i++)
	{
		scanf("%d", &numbers[i]);
	}

	int i, j, key;

	for (i = 1; i < number; i++)
	{
		key = numbers[i];

		for (j = i - 1; j >= 0 && numbers[j] > key; j--)
		{
			numbers[j + 1] = numbers[j];
		}

		numbers[j + 1] = key;
	}

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

버블 정렬 시간복잡도

최선	평균	최악
n	n2	n2