[CH6 정렬] 기준에 따라 데이터를 정렬 (3)

삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다

따라서 이번에는 삽입 정렬(Insertion Sort)에 대해 알아보자!

 

• 삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 것이다
• 이는 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다
• 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다
• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다!
• 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다
• 더불어 삽입 정렬은 특정한 데이터가 적절한 위지에 들어가기 이전에, 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다
• 정렬되어 있는 앞쪽의 데이터 리스트에서 적절한 위치를 찾은 후, 그 위치에 삽입하는 것이다!

 

 

삽입 정렬의 단계별 진행 방법

이제 예시를 통해 단계별로 삽입 정렬 과정을 살펴보자

초기 데이터

위와 같이 초기 데이터가 구성되어 있다고 하자

이 때 삽입 정렬은 두번째 데이터부터 시작한다

왜냐면 첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다

 

 

STEP 1

STEP 1) 첫번째 데이터 7은 정렬되어 있다고 판단하고, 두번째 데이터 5부터 정렬한다. 5가 들어갈 수 있는 위치는 앞 쪽의 데이터인 7의 왼쪽이나 오른쪽, 총 2가지 경우만 존재한다. 우리는 카드를 오름차순으로 정렬할 것이기 때문에 7의 왼쪽에 삽입한다 (5<7)

 

 

STEP 2

STEP 2) 이어서 9가 어느 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 위의 그림처럼 3가지이며 9는 앞의 정렬된 데이터인 5와 7보다 크기 떄문에 맨 오른쪽에 위치하는데 이는 원래 자리이므로 그대로 둔다

 

 

STEP 3

STEP 3) 이어서 0이 어느 위치에 들어갈지 판단한다. 0이 삽입될 수 있는 위치는 4가지이며, 0은 앞의 정렬된 데이터들 중 가장 작기 때문에 맨 왼쪽에 삽입한다

 

 

STEP 4

STEP 4) 이어서 3이 어느 위치에 들어갈지 판단한다. 3이 삽입될 수 있는 위치는 5가지이며, 3은 0과 5사이에 삽입한다

 

---

STEP 8

STEP 9

STEP 10

STEP 10) 앞의 방법을 N-1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다

 

---

삽입 정렬은 재미있는(?) 특징이 있는데, 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다

위의 그림들 중에서 하늘색 카드들을 보면 어떤 STEP이든지 항상 정렬된 상태를 유지한다

이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때 삽입될 위치를 찾기 위해 왼쪽으로 한칸씩 이동하는데, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다

 

한 예시로 STEP 4를 살펴보자

STEP 4

STEP 4에서 3은 왼쪽으로 한칸씩 이동하다가 자기 자신(3)보다 작은 0을 만났을 때 그 위치에 삽입된다

다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬된 상태이기 때문에 자기보다 작은 데이터를 만나면 더 이상 앞의 데이터를 확인할 필요 없이 그 자리에 삽입하면 되는 것이다!

 

---

삽입 정렬의 소스코드

 

파이썬 코드)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

#두 번째 원소부터 정렬
for i in range(1, len(array)):
    for j in range(i, 0, -1): #i부터 1까지 1씩 감소하며 반복힌다
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

파이썬 for문은 다 아는 것 같다가도 헷갈린단 말이지🤔

먼저 삽입 정렬은 첫번째 원소는 이미 정렬이 되어있다고 판단하기 떄문에 2번쨰 원소부터 정렬한다

그래서 바깥 반복문에서 1부터 시작하도록 했다

그리고 이제 현재 정렬할 원소의 앞의 데이터들과 하나씩 비교해가며 앞의 데이터가 더 크면 한칸 앞으로 이동하고, 작으면 반복문을 멈춰서 정렬을 끝낸다

 

파이썬 삽입정렬 결과화면

[참고]

range의 매개 변수는 3개이다 -> (start, end, step)

step에 -1이 들어가면 start 인덱스부터 시작하여 end+1 인덱스까지 1씩 감소한다

그래서 위의 코드에서는 j 변수가 i부터 1까지 1씩 감소하게 되는 것이다!

 

 

C++ 코드)

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n = 10;
    int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

    for(int i=1; i<n; i++)
    {
        for(int j=i;j>0;j--)
        {
            if(arr[j]<arr[j-1])
            {
                swap(arr[j], arr[j-1]);
            }
            else
                break;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

알고리즘은 파이썬과 동일하다!

 

c++ 삽입정렬 결과화면

---

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다
• 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다
• 이때 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다!
• 즉, 최선의 경우 O(N)의 시간 복잡도를 갖는다
• 바로 다음에 배울 퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더욱 강력하다!
• 따라서 거의 정렬되어 있는 상태라면 삽입 정렬이 가장 적합하다