삽입 정렬 (C/C++ 구현, 시간 복잡도)

1. 삽입 정렬

 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

출처 - 위키피디아(https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC)

나의 해석 : 현재 인덱스를 시작으로 인덱스 -1 자리에서 부터 0번 인덱스까지 비교하여 key 값의 자리를 찾아주어 정렬한다.

 

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

제일 앞 인덱스부터 하나 하나 탐색한다.

1. 비교 인덱스가 큰거라면 앞으로 이동(오른쪽)

2. 비교 인덱스가 작다면 스톱(현재 인덱스의 위치 찾음)

3. 2의 자리와 현재 인덱스 위치 바꾸기

 

시간 복잡도

0번 인덱스[0]에서 0번 비교

1번 인덱스[1]에서 1번 비교

2번 인덱스[2]에서 2번 비교

3번 인덱스[3]에서 3번 비교

n-1번 인덱스에서[n] n-1번 비교

O(n^2)

 

소스 코드

#include <iostream>

using namespace std;
int a[5] = { 5,4,3,2,1 };
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void insertion_sort(int list[])
{
	int j;
	for (int i = 0; i < 5; i++)
	{
		// 키 값
		int key = list[i];
		j = i - 1;
		for (j = i - 1; j >= 0; j--)
		{
			//큰거라면 한칸 앞으로 (오른쪽으로 이동)
			if (list[j] > key)
				swap(list[j + 1], list[j]);
			//아니라면 스탑 자기 자신 위치 찾음
			else
				break;
		}
		//찾은 위치와 키값 교환
		swap(list[j+1], key);
	}
}
int main()
{
	insertion_sort(a);
	for (int i = 0; i < 5; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}