[sorting] 삽입 정렬 | Insertion Sort

Insertion Sort

 

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 해당 위치에 삽입한다.
• 삽입정렬은 두 번째 자료부터 시작하여 해당 위치 기준 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한다. 
• 이는 기준점의 왼쪽의 자료들은 모두 sorted상태임을 알 수 있다.
• 처음 key 값은 두번째 자료부터 시작한다.

 

 

#include <stdio.h>
#include <iostream>
using namespace std;

int main(void) {
	int arr[10] = { 4,5,6,2,3,10,8,1,9,7 };
	int j;
	for (int i = 1; i < 10; i++) {
		int key = arr[i];
		int temp;
		for (j = i - 1; j >= 0 && arr[j] > key; j--) {
			arr[j + 1] = arr[j];
			temp = j;
		}
		arr[j + 1] = key;
		
		for ( auto x : arr) {
			cout << x << ' ';
		}
		cout << "\n";
	}
}

 

< 실행 결과

 

 

 

 

 

 

 

장단점

장점

• 안전한 정렬 방법
• 데이터 수가 적을 경우 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 대부분의 데이터가 이미 정렬되어있는 경우에 매우 효율적.

 

단점 

• 비교적 많은 데이터의 이동을 포함한다.
• 데이터 수가 많고 크기가 클 경우에 적합하지 않다.

 

 

시간 복잡도

1. 최선의 경우
   1. 비교횟수 :
      • 이동없이 1번의 비교
      • 외부루프 :(n-1)번
        •  Best : O(n)
2. 최악의 경우 == 입력 자료가 역순일 경우
   1. 비교횟수 : 외부 루프 안의 각 반복마다 i번의 비교 수행
      • 외부루프 : (n-1)번 -> (n-2)번 -> ... ->2번 ->1번 == n(n-1)/2 == O(n**2)
      • 교환 횟수
        • 외부루프의 각 단계마다 (i+2)번의 이동 발생
        • n(n-1)/2 + 2(n-1) = (n**2 + 3n-4)/2 = O(n**2)
        • Worst : O(n^2)

 

최선: N   평균: N**2  최악: N**2