[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)이란?

앞(왼쪽)의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법으로

원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다.

삽입 정렬(Insertion Sort)의 특징

1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다.

  //주어진 배열만으로 정렬을 할 수 있다.

  //메모리가 제한적인 경우에 이점이 있다.

 

2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다.

 

3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다.

 

4. 손 안의 카드를 정렬하는 방법과 유사하다.

 

5. 시간 복잡도는 Best : O(N), Avg : O(N^2), Worst : O(N^2)이며, O(N^2)의 시간 복잡도를 가진 선택 정렬, 버블 정
   렬보다 효율적인 정렬 알고리즘이다.

 

6. 데이터가 이미 거의 정렬된 상태에 한해서는 어떠한 정렬 알고리즘보다 빠르다.

  //값의 이동이 필요할 때만 위치를 바꾸게 되기 때문

삽입 정렬(Insertion Sort) 결과

주어진 배열을 오름차순 혹은 내림차순으로 정렬

 

삽입 정렬(Insertion Sort) 구현 방법

주어진 리스트의 두 번째 원소부터, 그 앞(왼쪽)의 원소들과 비교하여 적절한 위치에 삽입한다.

 

{3, 1, 5, 2, 4}

 

1.

{1, 3, 5, 2, 4}

두 번째 원소인 1이 3보다 작기 때문에, 3앞에 1을 삽입한다.

 

2.

{1, 3, 5, 2, 4}

세 번째 원소인 5가 3보다 크기 때문에 5는 움직이지 않는다.

 

3.

{1, 2, 3, 5, 4}

네 번째 원소인 2가 5,3보다 작고, 1보다 크기 때문에 1과 3 사이에 2를 삽입한다.

 

4.

{1, 2, 3, 4, 5}

다섯 번째 원소인 4가 5보다 작고 3보다 크기 때문에 3과 5 사이에 4를 삽입한다.

마지막 원소까지 검사했으니 정렬을 종료한다.

 

코드(c++)

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 3, 4, 2, 5, 1 };
	int arrSize = 5;

	//배열의 시작점부터 끝까지 탐색한다.
	for (int i = 0; i < arrSize - 1; i++) {
		//배열의 두 번째 원소부터, 해당 원소의 왼쪽에 있는 값들을 비교하고, 원소보다 작은 값을
		//만나면 그 뒤에 해당 원소를 삽입한다.
		for (int j = i + 1; j > 0 && arr[j - 1] > arr[j]; j--) {
			int temp = arr[j - 1];
			arr[j - 1] = arr[j];
			arr[j] = temp;
		}
		for (int a = 0; a < arrSize; a++)
			cout << arr[a] << ' ';
		cout << '\n';
	}
	
}