Chap 6-3. 삽입 정렬(insertion sort)

삽입 정렬이란? 

배열을 정렬된 부분(앞부분)과 정렬 안 된 부분 (뒷부분)으로 나누고,

정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복

즉, 정렬 안 된 부분에서 하나씩 꺼내서 정렬된 부분에 있는 것들과 비교한다.

 

자신보다 작은 원소를 발견할 때까지 왼쪽 방향으로 이동한다.

자신보닥 작은 원소 바로 뒤에 삽입된다.

→ 정렬 안 된 부분의 원소가 정렬된 부분에 삽입되어 정렬된 부분의 그룹의 수가 1개 늘어나고, 정렬이 안 된 부분의 원소의 수는 1개 줄어든다.

 

결과= 이를 반복하여 수행하면, 마지막엔 정렬이 안 된 부분엔 아무 원소도 남지 않는다. + 모두가 정렬된 상태가 된다.

가정 = 정렬은 배열의 첫 번째 원소만이 정렬된 부분에 있는 상태에서 정렬을 시작한다(정렬된 부분에 있다고 할 수 있다)

 

[의사코드]

입력: 크기가 n인 배열 A
출력: 정렬된 배열 A

1. for i = 1 to n-1
2.    CurrentElement = A[i] // 정렬 안된 부분의 가장 왼쪽 원소
3.    j ← i – 1 //이미 정렬 완료된 원소 
4.    while (j >= 0) and (A[j] > CurrentElement) //현재 비교 대상보다 크다면 
5.       A[j+1] = A[j] // 오른쪽으로 자리 이동 
7.    A [j+1] ← CurrentElement //삽입 완료 
8. return A

 

[코드 구현]

#include <stdio.h>
#include <stdlib.h>

#define N 8
#define FALSE 0
#define TRUE 1
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void insertionSort(int A[])
{
	int currentElement;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\n");

	printf("\n <<<<<<<<<<<<<<<<< Insertion Sorting .... >>>>>>>>>>>>>>>>>>\n");
	for (int i = 1; i <= N; i++) //첫 번째 원소는 이미 정렬되었다고 가정하자 
	{
		int currentElement = A[i]; //비교 대상 
		int j = i - 1; //이미 정렬 완료된 원소 

		while (j >= 0 && A[j] > currentElement)
		{
			A[j + 1] = A[j];
			j--; //현재 고른 값보다 작은 값을 찾을 때까지 앞으로 이동한다. 

		}
		A[j + 1] = currentElement; //j--을 하고 while문을 빠져나와서 j+1로 해야 한다. 


		printf(" %d pass >> ", i + 1);

		for (int j = 0; j < N; j++) //배열 출력 
			printf("%d", A[j]);
		printf("\n");
	}



}

 

[ 삽입 정렬의 특징 ]

(1) 삽입 정렬은 거의 정렬된 입력에 대해서 다른 정렬 알고리즘보다 빠르다.

예를 들면, 입력이 앞부분은 정렬되어 있고 뒷부분(전체 입력 의 20% 이하)에 새 데이터가 있는 경우

 

(2) 입력의 크기가 작을 때 매우 좋은 성능을 보인다.

 

(3) 삽입 정렬의 경우 입력 데이터의 정렬 여부에 따라 민감하다.

-어느 정도 정렬이 되어있다면 비교 연산이 별로 없다.

-오름차순을 원하는데 내림차순으로 입력이 들어온다면 비교연산이 매우 많아진다.

 

(4) 퀵 정렬, 합병 정렬에서 입력 크기가 작아지면 순환 호출을 중단하고 삽입 정렬을 사용

*한편, Tim sort에서는 입력 크기가 64이하이면 삽입 정렬을 호출한다.(방법 변환)

 

시간 복잡도

• for-루프가 (n-1)회 수행 – i=1일 때 while-루프는 1회 수행 – i=2일 때 최대 2회 수행
• - i = 3일 때 최대 3회 수행

⋮ – 마지막으로 최대 (n-1)회 수행

• 루프 내부의 line 5~6이 수행되는 총 횟수:

1 + 2 + 3 +⋯+ (n-2) + (n-1) = n(n-1)/2

• 루프 내부는 O(1) 시간(단순 대입)

- n(n-1)/2 x O(1) = O(n^2)