[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

 

삽입 정렬이란?

• 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 위치를 찾아 삽입을 하는 알고리즘 이다.
• 시간복잡도는 평균 or 최악의 경우 O(n^2)를 가지게 된다.
• 정렬된 데이터 기준으로 시간복잡도는 O(1)을 가지게 된다.
• 데이터가 많아지면 효율이 떨어지고 구현이 간단하다.
• 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비해 빠르다

삽입 정렬 과정

오름차순 기준이다.

앞에서 부터 배열의 인덱스 0이 아닌 1로 기준을 잡고 기준에서 왼쪽과 비교하여 삽입을 해준다.

 

먼저 인덱스1의 키 값인 3을 가져온다.

---

3 과 4를 비교 후 3보다 4가 크니 4를 한칸 오른쪽으로 이동 시킨다.

---

배열의 -1의 인덱스가 존재 하지 않기 때문에 키 값은 0번째 배열에 삽입을 해준다.

---

이번엔 세 번째의 키 값을 가져 온다.

---

2와 4를 비교 후 4가 더 크니 오른쪽으로 한칸 이동 시킨다.

---

2와 3을 비교 후 3이 더 크니 오른쪽으로 한칸 이동 시킨다.

---

배열의 -1의 인덱스가 존재 하지 않기 때문에 키 값은 0번째 배열에 삽입을 해준다.

이런식으로 배열의 네 번째까지 똑같은 방식으로 비교하여 정렬을 시켜준다.

 

삽입 정렬 코드

#include <iostream>

int main()
{
    int Array[5] = { 4,3,2,1,5 };

    int Count = 5;

    for (int i = 1; i < Count; ++i)
    {
        int Key = Array[i];
        int j = i - 1;
        while (j >= 0 && Key < Array[j])
        {
            Array[j + 1] = Array[j];
            --j;
        }
        Array[j + 1] = Key;
    }


    for (int i = 0; i < Count; ++i)
    {
        std::cout << Array[i] << " ";
    }
}