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

🔨 삽입 정렬

삽입하여 정렬하는 알고리즘으로, 자신보다 앞의 원소가 큰지 작은지 비교를 하면서 자신의 위치를 찾아서 '삽입'하는 정렬방법

👉 개념 요약

• 제자리 정렬(in-place sortring) 알고리즘의 하나
• 자신의 위치를 찾아 삽입
• 손안의 카드 정렬 방법과 유사
  (새로운 카드를 기존에 정렬된 카드 사이에서 올바른 자리를 찾아 삽입)

👉 실행

{5, 10, 2, 1, 17, 6 } 이란 배열이 주어졌을 때

1. 배열의 두번째 자리(10)에서 시작
2. 첫번째 자리(5)와 비교 (5보다 크므로 비교 끝)
3. 그대로 {5, 10, 2, 1, 17, 6 }
4. 배열의 세번째 자리에서 시작
5. 두번째 자리와 비교 10은 뒤로 옮겨짐.
첫번째 자리와 비교 5는 뒤로 옮겨짐.
6. 비교 끝 {2, 5, 10, 1, 17, 6}

여섯번재 자리(배열의 끝)까지 반복

👉 코드 구현

void InsertionSort(int* arr,int n) {
	int key;
	for (int i = 1; i < n; i++) {
		key = arr[i];
		int j = i - 1;
        // = for(j = i-1 ; j >=0; j--)
		while (j >= 0 && key < arr[j]) { //key보다 작은 값이 나오면 멈춤
			arr[j + 1] = arr[j]; // 앞자리의 값이 key보다 크다면 하나씩 이동
			j--;
		}
		arr[j + 1] = key; // 그 자리에 삽입
	}
}

👉 선택정렬 알고리즘 시간 복잡도

< 시간 복잡도 계산 >

• 비교 횟수
  - 두개의 for루프
  - 외부 루프 : n-1 번
  - 내부 루프 : 1, 2,...n-2, n-1 (최악의경우)
  1, 1,...1 ,1(최선의 경우)
  
• 교환 횟수
  O(1)

• 최악 시간복잡도 O(n^2) 비교 및 교환
• 최선 시간복잡도 O(n) 비교, O(1) 교환

다음 표를 보면 (삽입정렬,선택정렬, 버블정렬)은
다른 정렬에 비해 비효율적이다는 것을 알수있다.
하지만 코드 구현이 간단하다는 장점이 있다.

👉 삽입정렬 알고리즘 특징

• 장점
  - 대부분의 자료가 이미 정렬되어 있는 경우 매우 효율적이다
• 단점
  - 삽입시, 데이터가 하나씩 밀려야 하기때문에 배열이 길수록 효율이 떨어진다.

👉 관련된 post

• 선택 정렬(selection sort) : Selection Sort