삽입정렬 (insertion sort) 알아보기

반응형

이번 포스팅에서는 삽입정렬, insertion sort 에 관해 간단히 정리해보려고 합니다. 지난 포스팅에서는 버블정렬에 관해 정리했었습니다. 삽입정렬도 버블정렬만큼이나 간단하고 쉬운 정렬 방법입니다. 간단하지만 비교해서 설명하라고 하면 헷갈려 하는 경우가 생기기도 합니다. 그래서 이번에는 개념 위주로 삽입정렬에 관해 알아보고 버블정렬과는 어떤 점이 다른지 비교해보려고 합니다.

 

삽입정렬이란...

삽입정렬도 굉장히 무식한 방법 중에 하나입니다. 이름에서 알 수 있듯이 이 방법은 수를 정렬할 때 각각의 수를 배열에 삽입하여 정렬합니다. 추후에 다루게 될 선택정렬 (selection sort)와 유사하면서 다른 점은 삽입정렬은 내가 정렬할 어떤 수를 적절한 과정을 거쳐 적합한 위치에 넣는 방식이고, 선택정렬은 배열 내 해당 위치에 들어갈 수를 일일이 찾는 방식이라고 보면 됩니다.

 

위에서 삽입정렬은 "정렬할 어떤 수를 적절한 과정을 거쳐 적합한 위치에 넣는다"고 하였습니다. 여기서 중요한 점은 어떤 것이 적절한 과정이고, 어디가 적합한 위치인지 알 수 있는지 입니다. 삽입정렬에 관해 예시를 들기 전에 길거리 농구나 공용 체육시설을 사용하는 스포츠를 즐겨 하시는 분들이라면 '밀어내기'라는 용어를 익히 알고 계실 것 같습니다. 공용 체육시설은 대게 코트가 한정되어 있다보니 예약제가 아닌 경우라면 많은 사람들이 몰려 있습니다. 여러 사람들이 공정하게 사용하기 위해 보통 게임을 해서 이긴 팀은 계속 코트에 남고, 진 팀은 다음 팀과 교체되는 방식입니다.

 

스포츠에 익숙하지 않으신 분들이 있을 수 있으니 다른 예시를 들자면 무한도전에 '관상'편에 나온 왕게임을 본 적 있으신가요? 거기서 멤버들은 왕부터 천민까지 다양한 직업군으로 역할을 부여받고 천민부터 기회가 주어져 게임을 통해 승리하면 두 멤버의 계급이 바뀝니다. 도전자는 질 때까지 계속 다음 단계의 멤버와 계급을 놓고 게임을 벌이게 되죠.

 

이게 다 무슨 소리냐구요? 말씀드린 두 예시는 삽입정렬의 진행방식과 유사한 점이 있습니다. 머릿속에 과정이 들어온다면 이를 바탕으로 향후 코드를 짤 때 도움이 되기 때문에 현상을 이미지화 해두는 것이 중요합니다. 아래의 예시를 보겠습니다.

 

삽입정렬 예시

예시: [7, 2, 4, 8, 3]

 

오름차순으로 위 배열을 정렬한다고 하겠습니다. 삽입정렬 방식을 쓸 것입니다. 첫번째 인덱스에 있는 [7]은 비교할 대상이 없기 때문에 넘어가고 두번째 인덱스에 있는 [2]부터 왼쪽으로 이동해가며 본인과 크기를 비교합니다. 오름차순 정렬이기 때문에 자신보다 큰 숫자라면 이긴 것이고, 자신보다 작은 숫자라면 정렬이 되어 있는 것이기 때문에 졌다고 판단합니다. 이겼다면 기존 숫자는 자신의 자리를 넘겨주고 옆으로 이동하게 됩니다. 위 예시에서 [2]는 [7]보다 작은 숫자이기 때문에 게임에서 승리했습니다. 이에 [7]은 오른쪽으로 자리를 이동하여 [2]에게 본래 자리를 넘겨줍니다.

 

결과: [2, 7, 4, 8, 3]

 

다음으로 [4]의 차례입니다. [4]와 [7]과 비교하면 이번에도 [7]이 더 큰 숫자이기 때문에 오른쪽으로 이동합니다. 하지만 [4]는 [2]보다는 큰 숫자이기 때문에 더 왼쪽으로 이동하지 못하고 멈추게 됩니다.

 

결과: [2, 4, 7, 8, 3]

 

이런 식으로 [8]과 [3]이 동일하게 이동을 하게 되면 아래와 같이 오름차순으로 정렬이 완료됩니다.

 

최종결과: [2, 3, 4, 7, 8]

 

삽입정렬 특징

삽입정렬은 처음에는 낯설 수는 있지만 원리를 이해하고 예시를 보면 쉽게 정리할 수 있는 방법입니다. 예시로 부터 삽입정렬이 갖는 특징을 정리해보겠습니다.

 

- 이미 정렬되어 있는 경우 효율적이다. (최선의 경우 O(n)의 시간이 걸린다.)

- 보통은 많은 이동 연산이 필요하다.

- 평균적으로 O(n^2)의 시간복잡도가 발생한다.

 

 

이상 삽입정렬에 관해 알아보았습니다. 다음에는 이와 유사한 선택정렬에 관해 알아보고 코드도 작성해보는 포스팅을 올리도록 하겠습니다.