졸지말고..

이번 시간에는 저번 시간에 이어 기본 정렬 중 하나인 삽입 정렬(Insertion sort)에 대해서 알아보도록 하겠습니다.

삽입 정렬(Insertion sort) - 안정 정렬(Stable sort)

삽입 정렬이란 정렬된 구간과 그렇지 않은 구간 둘로 나누고, 

정렬되지 않은 구간의 맨 앞 원소를 가져와 정렬된 구간에 삽입하는 알고리즘입니다.

알고리즘의 수행 단계는 다음과 같습니다.

1) 주어진 데이터 중 맨 앞의 원소를 정렬된 구간으로 설정하고, 나머지를 그렇지 않은 구간으로 정합니다.

2) 삽입 데이터 정하기 : 정렬되지 않은 구간의 맨 앞 데이터를 삽입 데이터(key 값)로 정한다.

3) 삽입 위치 파악하며 데이터 밀어내기 : 정렬 구간을 역순으로 탐색하며 Key 값이 삽입될 위치를 파악합니다.

4) 모든 데이터가 정렬될 때까지 2-3 과정을 반복합니다.

좀 더 자세하게 그림으로 보여드리겠습니다.

이 그림을 위에서 언급한 순서와 함께 설명하자면 다음과 같습니다.

1) 주어진 데이터(7-3-2-1-5) 에서 7을 정렬된 구간으로 설정하고 나미저 3-2-1-5를 정렬되지 않은 구간으로 설정하여 시작합니다.

1 회전 : 

2) 3을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 정렬된 구간을 7부터 역순으로 탐색하며 삽입 위치를 합니다. 이때, (Key 값 > 비교 데이터) && (더 이상 비교할 데이터가 없는가?)를 만족해야 합니다. 따라서, 조건을 비교해가며 결국 첫 번째 자리에 삽입되게 됩니다.

2 회전 :

2) 2를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.

3 회전 :

2) 1을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.

4 회전 :

2) 5를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2, 3회전과 달리 두 번째 비교작업때 Key 값이 비교데이터(3) 보다 크므로 조건에 위배됩니다. 따라서, 그때 빈 공간에 삽입되게 됩니다.

소스 코드

배열 a : 정렬하고자 하는 데이터

key : 정렬되지 않은 구간에서 정렬 구간으로 옮기며 정렬할 값

j : key 값의 삽입 위치

Line 11: 

i 는 정렬되지 않은 구간에서 삽입할 데이터의 위치를 의미합니다. 

따라서 첫 번째 값을 정렬 구간으로 설정하기 때문에 1부터 시작합니다.

Line 12 :

정렬할 데이터를 Key 변수에 저장합니다.

Line 14 :

Key < a[j-1] -> Key 값 보다 큰 값이 이전에 있으면 계속 진행하는 조건 입니다.

j>0 -> key 값이 제일 작아 처음에 삽입되어야 하는 조건입니다.

Line 15-16 :

데이터의 삽입을 위해 정렬된 구간의 데이터들을 뒤로 한칸씩 미룹니다. 또한 다음 탐색을 위해 j값을 감소시킵니다.

Line 18 :

한 회전을 통해서 삽입할 위치를 찾았으니 데이터를 삽입합니다.

시간 복잡도

삽입 정렬에서 최악의 경우는 버블 정렬과 마친 가지로 역순으로 정렬되어 있을 경우다.

즉, 매 회전마다 삽입되는 데이터가 정렬 구간의 처음에 삽입된다면,

1회전에 1번, 2회전 2번 ... n-1 회전에 n-1번 동작하기 때문에

1부터 n-1 까지 등차 수열의 합이므로 n에 대한 2차식이다. 따라서 시간복잡도는 이 됩니다.

저번 포스팅에서 언급했듯이 정렬에 대해서 알아보도록 하겠습니다.

우선 정렬 알고리즘을 배우기 전에 정렬의 안정적 특성에 대해서 알아야 할 필요가 있습니다.

이 특성을 모르고 정렬 알고리즘을 선택한다면, 우리가 원하는 결과를 얻지 못할 수 있기 때문입니다.

정렬의 안정적 특성이란?

정렬의 안정적 특성이란 "정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐" 입니다.

이러한 정렬의 안정적 특성에 따라서 정렬 알고리즘은 안정 정렬과 불안정 정렬로 구분 할 수 있습니다.

예를 들어, 아래와 같은 포커 카드에 대해서 번호를 키값으로 하여 오름차순으로 정렬하고자 합니다

이때, 우리는 약간 이상한 성향으로 인해(?) 같은 숫자카드의 무늬 순서를 유지시키고자 합니다.

즉, 아래 그림의 경우 정렬 후에도 하트4 뒤쪽에 스페이스4가 위치하게 하고 싶다는 의미입니다.

"당연히 유지되는게 정상 아니야?" 라고 생각 하실 수 있지만, 정렬 알고리즘에 따라서 정렬 후에 이 순서가 바뀔 수도 있습니다.

안정 정렬(Stable Sort) 

안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지되며, 결과는 다음과 같습니다.

정렬된 결과에서 하트4와 스페이스4의 순서가 그대로 유지되고 있음을 확인 할 수 있습니다.

불안정 정렬(Unstable Sort)

불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없으며, 결과는 다음과 같을 수 있습니다.

안정 정렬의 결과와는 달리 스페이스4와 하트4의 순서가 바뀐 모습을 확인 할 수 있습니다.

앞으로 배울 정렬 알고리즘에는 안정 정렬 알고리즘도 있고, 불안정 정렬 알고리즘도 있습니다.

따라서 이를 구분해서 학습을 해야 합니다. 너무 걱정하지는 마세요! 정렬 알고리즘을 설명할 때 같이 하도록 하겠습니다.

이번 포스팅은 여기까지며 다음 글부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다!