3강 - 삽입 정렬 (Insertion Sort)

1. 삽입 정렬

(오름차순을 기준)

1) 정의

뒤의 숫자가 정렬되어있다고 가정하고 한 칸씩 이동하며

해당 index의 element을 뒤의 정렬된 숫자 사이 중 올바른 자리에 넣어준다.

2) 특징

1> 시행은 1번째 element부터 시작한다. (0번째는 정렬 되어있다고 가정)

 

2. 구체적인 과정

1> 0번째 element는 정렬 되어있다고 가정하고 1번째 element를 적절한 위치에 넣는다.

2> 적절한 위치는 처음으로 자신보다 작은 수가 나오는 부분이다. (없다면 맨 앞에 들어가게 한다.)

3> 1>~2>를 맨 마지막 N-1번째 element까지 진행한다.

 

 

3. 구현

(오름차순을 기준)

0) 주요 point

1> 어떻게 중간에 삽입하는가?

- 현재 위치를 찾는 element를 계속해서 swap을 통해 이동해간다고 생각한다.

 

1) 내 풀이

#include <iostream>
using namespace std;
const int MAX = 1000

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

int main()
{
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	// i: 이동해야 하는, 자리를 찾고 있는 element의 index
	for (int i = 1; i < N; i++)
	{
		// j: i와 크기를 비교하고 자리를 내어주거나 자리를 지키는 index
		for (int j = i - 1; j >= 0 ; j--)
		{
			if (arr[j] > arr[i])
			{
				swap(arr[i], arr[j]);
				i = j;
			}
			else break;
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}

2) 다른 풀이

 

#include <iostream>
using namespace std;
const int MAX = 1000;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

int main()
{
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int j;
	// i: 이동해야 하는, 자리를 찾고 있는 element의 index
	for (int i = 0; i < N-1; i++)
	{
		// j: 한 원소가 이동 중일 때에는 i대신 j로 표현
		j = i; // i가 0부터 시작이어서 그냥 j에 i를 할당하고 바로 시작해도 된다.
		while (j >= 0 && arr[j] > arr[j + 1])
		{
			swap(arr[j], arr[j + 1]);
			j--;
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}