[알고리즘] 삽입 정렬 (insertion sort)

삽입정렬

삽입정렬은 배열을 정렬된 부분(앞부분) 과 정렬이 안 된 부분(뒷부분) 으로 나누고, 정렬이 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복.

• 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어듬.

수도코드 및 시간복잡도

입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for i = 1 to n-1{
 currentElement = A[i] //정렬이 안 된 부분의 가장 왼쪽 원소
 j <- i - 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳 탐색
 while( j >= 0) and (A[j] > currentEelement){
  A[j+1] = A[j] //자리 하나씩 이동
  j <- j-1
  }
  //while문을 빠져나왓다는거 = A[j] < currentElement
A[j+1] <- currentElement
}
return A

• for루프가 n-1번 수행되는데, i=1일때 while루프는 1번 수행되고, i=2일때 while루프는 2번 수행되고, ... i=n-1때 while루프는 n-1번 수행되므로, while루프내 수행 횟수는 1+2+3+4+...+n-1 = n(n-1)/2 이다. while루프 내부 수행시간 O(1)이므로, 전체 시간복잡도는 n(n-1)/2 x O(1) = O(n^2)
• 이미 정렬된 배열이 주어진 경우, while문 조건식이 항상 거짓이 되므로 원소의 이동이 없어, for루프 가 n-1번만 수행된다. 이때 시간복잡도는 최선의 경우 O(n) 이다.

---

•  본교재 문제 13 ) 버블정렬, 선택정렬, 삽입정렬 중에서 입력이 [3,4,7,1,2] 일때 어떤 정렬 알고리즘이 가장 빨리 정렬할까?
  • 삽입정렬을 선택했을 경우, 기존 정렬된 부분은 while문을 넘어가므로, 위 입력에서 3,4,7은 while문을 넘어가, 1,2만 추가 정렬하면 된다. 나머지 정렬은 그런 부분이 없이 처음부터 정렬을 하므로 위 입력이 주어졌을 경우, 삽입정렬이 가장 빨리 정렬한다.
• 본교재 문제 37) 삽입정렬은 currentElement를 앞부분에 정렬되어 있는 숫자들 사이에 적절히 삽입하기 위해 1개의 원소씩 비교하며 원소들을 이동시킨다. 즉 순차탐색이 수행된다. currentEelement 를 앞부분에 보다 효율적으로 삽입할 수 있는 방법은?
  • currentElement 값보다 적은 값인 경계를 찾아  더 효율적으로 원소를 이동시킨다. 이 과정은 이진탐색으로 수행한다.

코드(c)

/*
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for i = 1 to n-1{
 currentElement = A[i] //정렬이 안 된 부분의 가장 왼쪽 원소
 j <- i - 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳 탐색
 while( j >= 0) and (A[j] > currentEelement){
  A[j+1] = A[j] //자리 하나씩 이동
  j <- j-1
  }
  //while문을 빠져나왓다는거 = A[j] < currentElement
A[j+1] <- currentElement
}
return A

*/

#include <stdio.h>
void insertionsort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int currentElem = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > currentElem)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = currentElem;
	}

	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
}
int main()
{
	int a[] = { 40,60,70,50,20,30,10 };
	int n = sizeof(a) / sizeof(int);
	insertionsort(a, n);
	return 0;
}

---

본교재 문제 37 에 해당하는 코드

#include <stdio.h>

int binary(int low, int high, int a[], int currentElem)
{
	while (low < high)
	{
		int mid = low + (high - low) / 2;
		if (a[mid] < currentElem)
			low = mid + 1;
		else
			high = mid -1;
	}
	return low;
}

void insertionsort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int currentElem = a[i];
		int pos;
		int j = i - 1;
		pos = binary(0, j, a, currentElem);

		while (j >= pos && a[j] > currentElem)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = currentElem;
	}

	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
}

int main()
{
	int a[] = { 40, 60, 70, 50, 20, 30, 10 };
	int n = sizeof(a) / sizeof(int);
	insertionsort(a, n);
	return 0;
}

BOJ

24051 (c++)

https://www.acmicpc.net/problem/24051

24051번: 알고리즘 수업 - 삽입 정렬 1

1차시도 )  처음에 아래와 같은 코드로 작성하였는데, 값은 제대로 나왔지만 "시간초과" 오류가 나왔다. 그래서 삽입 정렬을 이진탐색을 이용해 구현하려고 시도해보았다(다다음 코드).

#include <iostream>
#include <vector>
using namespace std;
void swap(int& a, int& b)
{
	int tmp = a;
	b = a;
	b = tmp;
}
bool isSame(vector<int> a, vector<int> b, int N)
{
	int sameCount = 0;
	for (int i = 0; i < N; i++)
	{
		if (a[i] == b[i])
			sameCount++;
	}
	if (sameCount == N)
		return true;//a와 b가 같다
	else
		return false;//a와 b가 다르다
}
int insertionsort(vector<int> a, vector<int>b , int N, int K)
{
	int count = 0;//저장 횟수
	for (int i = 1; i < N; i++)
	{
		int j = i - 1;
		int currentElem = a[i];
		while (j >= 0 && currentElem < a[j])
		{
			a[j + 1] = a[j];
			if(! isSame(a, b , N))//함수의 반환이 false 값인 경우 저장횟수 증가
				count++;//저장횟수 증가
			if (count == K)
				return a[j+1];
			j--;

		}
		a[j + 1] = currentElem;
		if (!isSame(a, b, N))//함수의 반환이 false 값인 경우 저장횟수 증가
			count++;//저장횟수 증가
		if (count == K)
			return a[j+1];
	}
	return -1;
}
int main()
{
	int N, K;

	cin >> N;
	cin >> K;
	vector<int> a(N);
	vector<int> b(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	int result = insertionsort(a,b,N,K);
	cout << result;
	return 0;
}

2차 시도 )   

currentElem 을 새로운 자리에 저장하는 수행이  i != j+1인 경우에만 수행될 수 있도록 조건을 넣어줬어야 했다.

#include <iostream>
#include <vector>
using namespace std;
void swap(int& a, int& b)
{
	int tmp = a;
	b = a;
	b = tmp;
}
bool isSame(vector<int> a, vector<int> b, int N)
{
	int sameCount = 0;
	for (int i = 0; i < N; i++)
	{
		if (a[i]  == b[i])
			sameCount++;
	}
	if (sameCount == N)
		return true;//a와 b가 같다
	else
		return false;//a와 b가 다르다
}
int insertionsort(vector<int> a, vector<int>b , int N, int K)
{
	int count = 0;//저장 횟수
	for (int i = 1; i < N; i++)
	{
		int j = i - 1;
		int currentElem = a[i];
		while (j >= 0 && currentElem < a[j])
		{
			a[j + 1] = a[j];
			//if(! isSame(a, b , N))//함수의 반환이 false 값인 경우 저장횟수 증가
				count++;//저장횟수 증가
			if (count == K)
				return a[j+1];
			j--;

		}
		if (i != j + 1) {//같은 값 저장 제외
			a[j + 1] = currentElem;
			count++;//저장횟수 증가
		}//if (!isSame(a, b, N))//함수의 반환이 false 값인 경우 저장횟수 증가
		if (count == K)
			return a[j+1];
	}
	return -1;
}
int main()
{
	int N, K;

	cin >> N;
	cin >> K;
	vector<int> a(N);
	vector<int> b(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	int result = insertionsort(a,b,N,K);
	cout << result;
	return 0;
}