삽입 정렬(insertion sort)

삽입 정렬이란?

삽입 정렬은 리스트를 순차적으로 탐색하면서, 현재 값이 들어갈 적절한 위치를 찾아 앞쪽 정렬된 부분에 삽입하는 방식으로 정렬을 수행하는 알고리즘입니다.

 

정렬 순서

1. 두 번째 원소부터 시작하여, 해당 원소를 앞쪽의 정렬된 부분과 비교한다.
2. 자신의 위치보다 앞에 있으면서 자신보다 큰 원소들은 한 칸씩 뒤로 이동시킨다.
3. 빈자리에 현재 원소를 삽입한다.
4. 리스트 끝까지 같은 방법을 반복한다.

이 과정을 통해 리스트는 점진적으로 정렬됩니다.

의사 코드 (Pseudocode)

for i = 1 to n - 1:
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]
        j = j - 1
    a[j + 1] = key

시간 복잡도

삽입 정렬은 데이터의 상태에 따라 성능 차이가 크게 발생합니다.

구분	복잡도
최선의 경우 (이미 정렬된 경우)	O(n)
평균적인 경우	O(n²)
최악의 경우 (역순 정렬)	O(n²)
공간 복잡도	O(1) (추가 메모리 사용 없음)

• 이미 정렬되어 있는 경우, 비교만 수행되고 이동이 거의 발생하지 않기 때문에 효율적입니다.

예제

초기 리스트: `[9, 1, 6, 8, 4, 3, 2, 0]`

패스 번호	리스트 상태	삽입 위치
0	[9, 1, 6, 8, 4, 3, 2, 0]	시작
1	[1, 9, 6, 8, 4, 3, 2, 0]	1이 9 앞에 삽입
2	[1, 6, 9, 8, 4, 3, 2, 0]	6이 9 앞에 삽입
3	[1, 6, 8, 9, 4, 3, 2, 0]	8이 9 앞에 삽입
4	[1, 4, 6, 8, 9, 3, 2, 0]	4가 정렬된 부분에 삽입
5	[1, 3, 4, 6, 8, 9, 2, 0]	3이 정렬된 부분에 삽입
6	[1, 2, 3, 4, 6, 8, 9, 0]	2가 정렬된 부분에 삽입
7	[0, 1, 2, 3, 4, 6, 8, 9]	0이 정렬된 부분에 삽입

최종적으로 리스트가 오름차순으로 정렬됩니다.

장단점

장점

• 구현이 매우 간단하다
  → 알고리즘 구조가 직관적이며 코드가 짧고 이해하기 쉽다.
• 이미 정렬된 데이터에 매우 효율적이다
  → 최선의 경우 O(n)으로 빠르게 정렬 가능하다.
• 추가 메모리가 거의 필요 없다
  → 공간 복잡도: O(1)
  → 별도의 배열이나 자료구조 없이 주어진 배열 내에서만 정렬을 수행한다.
• 부분적으로 정렬된 데이터에 적합
  → 실시간으로 데이터가 삽입되는 경우에 유리하다.

단점

• 최악의 경우 시간 복잡도가 O(n²)
  → 역순으로 정렬된 경우 매우 비효율적이다.
• 대규모 데이터 정렬에는 부적합
  → 효율성이 낮기 때문에, 대량의 데이터를 정렬할 경우 다른 고급 알고리즘(퀵 정렬, 병합 정렬 등)을 사용하는 것이 좋다.

코드 예시

C

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ){
        data[j+1] = data[j];
    }
    data[j+1] = remember;
  }
}

Java

void insertionSort(int[] arr)
{

   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux + 1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

Python

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

정렬 알고리즘 시간복잡도 비교

알고리즘 이름	Best	Avg	Worst	공간복잡도
삽입 정렬	𝑂(𝑛)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
선택 정렬	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
버블 정렬	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
셸 정렬	𝑂(𝑛)	𝑂(𝑛¹⋅⁵)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
퀵 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛²)	𝑂(log 𝑛) (재귀 호출 스택)
힙 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(1) (제자리 정렬)
병합 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛) (추가 배열 필요)

• 제자리 정렬(in-place sort): 추가 메모리를 거의 사용하지 않는 정렬, 주로 𝑂(1) 을 보장