삽입 정렬 ( Insertion Sort )

삽입 정렬 ( Insertion Sort )

삽입 정렬은 배열을 앞에서부터 차례대로 보면서, 현재 원소를 알맞은 위치에 삽입하는 방식의 정렬 알고리즘이다.

이미 정렬된 부분 배열을 유지하면서, 새로운 원소를 하나씩 삽입하는 방식이라 삽입 정렬이라 부른다.

배열의 두 번째 요소부터 시작해
앞쪽 정렬된 부분과 비교하며 자신보다 큰 값을 밀어낸 뒤,
빈 자리에 현재 값을 삽입한다.

 

 

동작 과정

예를 들어 [ 5 , 3 , 8 , 4 , 2 ] 를 오름차순 정렬한다고 가정

1. 초기 상태

- 첫 번째 원소 ( 5 ) 는 이미 정렬된 상태로 간주

 

2. [ 3 ] 삽입

- 5 > 3 → [ 5 ] 에서 [ 3 ] 의 위치를 찾음 → [ 5 ] 앞에 삽입

- [ 3 , 5 , 8 , 4 , 2 ]

 

3. [ 8 ] 삽입

- [ 3 , 5 ] 에서 [ 8 ] 위치를 찾음 → 맨 뒤에 삽입

- [ 3 , 5 , 8 , 4 , 2 ]

 

4. [ 4 ] 삽입

- [ 3 , 5 , 8 ] 에서 [ 4 ] 위치를 찾음 → [ 3 ] 뒤, [ 5 ] 앞에 삽입

- [ 3 , 4 , 5 , 8 , 2 ]

 

5. [ 2 ] 삽입

- [ 3 , 4 , 5 , 8 ] 에서 [ 2 ] 위치 찾음 → 맨 앞에 삽입

- [ 2 , 3 , 4 , 5 , 8 ]

 

 

의사코드 ( PseudoCode ) 표현

for (i = 0, 배열 크기만큼 반복)

	for (j = i, j > 0까지 감소)

		if (arr[j - 1] > arr[j])
            arr[j - 1]과 arr[j]를 교환
        
        else
            반복 종료

 

 

C# 예제 코드

public static void InsertionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

 

 

정리

- 구현이 간단하고, 데이터가 거의 정렬되어 있으면 효율적이다.

- 데이터가 많을수록 비효율적이다

- 소규모 데이터 정렬에 적합하다.