정렬 알고리즘(삽입 정렬)

삽입 정렬(Insertion Sort)

개yo

---

앞선 포스팅에서는 선택정렬 , 버블정렬 에 대해 알아보았고, 이번 포스팅에서는 삽입정렬을 구현하고 시간 복잡도를 알아 보도록 하겠다.

문제

---

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

1 10 5 8 7 6 4 3 2 9

SOL

문제를 해결하기 위해 “각 숫자를 적절한 위치에 삽입”을 이용할 수 있다.

위와 같은 방법을 삽입정렬 이라고 부른다.

특징

1. 다른 정렬 알고리즘보다 비교적 느린 알고리즘에 속한다.
2. 조금 복잡한 구조를 가지고 있다.
3. 특정한 경우에 굉장히 빠른 속도를 갖는다.

구현

---

#include <iostream>

using namespace std; 

int main(void) {
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i = 0; i < 9; i++) 
	{
		j = i;
		while(j >= 0 && array[j] > array[j + 1]) 
	{
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for(i = 0; i < 10; i++) 
	{
		printf("%d ", array[i]);
	}
	return 0;
}

출력 값

1 2 3 4 5 6 7 8 9 10

해설

---

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

2 3 4 5 6 7 8 9 10 1

1. 데이터가 위와 같이 거의 정렬된 상태일 때는 필요한 경우에만 삽입이 이루어지는 삽입정렬 은 데이터가 거의 정렬된 경우에는 시간복잡도가 O(N)와 유사함으로 어떤 알고리즘보다도 빠른 특징을 가지고 있다.
2. 하지만 정렬이 거의 되어있지 않은 상태에서의 시간 복잡도는 선택정렬 , 버블정렬 과 동일하게 O(N^2) 로 표현할 수 있다.
3. 삽입정렬 : 멈출 타이밍(위치, index)을 스스로 판단하는 정렬 알고리즘

#### 추가설명

---

/* < 예시 입력 >

10
26 5 37 1 61 11 59 15 48 19

< 예시 출력 >

26 
5 26 
5 26 37 
1 5 26 37 
1 5 26 37 61 
1 5 11 26 37 61 
1 5 11 26 37 59 61 
1 5 11 15 26 37 59 61 
1 5 11 15 26 37 48 59 61 
1 5 11 15 19 26 37 48 59 61

< 출력 > */

위와 같은 삽입정렬의 과정을 출력하는 코드를 살펴 본다면

#include <stdio.h>

int n;
int array[101];

int main(void) {
	int i, j, temp, n;
	scanf("%d", &n);
	for(i = 0; i < n; i++) {
		scanf("%d", &array[i]);
	}
	for(i = 0; i < n; i++) {
		j = i;
		while(j > 0 && array[j - 1] > array[j]) {
			temp = array[j - 1];
			array[j - 1] = array[j];
			array[j] = temp;
			j--;
		}
		for(j = 0; j <= i; j++) {
			printf("%d ", array[j]);
		}
		printf("\n");
	}
	return 0;
}

위 코드는 시작부터 특정 위치에서 시작하여 왼쪽으로 이동하여 자신보다 작은 것을 만날 때 그 위치에 원소를 삽입하는 과정을 따른다.

본 포스팅은 동빈나님의 블로그를 참고하여 작성하였습니다.