[알고리즘] 삽입정렬 쉽게 생각하기

 

선택정렬은 왼쪽을 기준으로 가장 작은 값을 찾아가는 방식으로 정렬을 진행합니다..

버블정렬은 오른쪽을 기준(i점)으로 두고 반대편 왼쪽(j점)에서 0으로 두고 i를 하나하나씩 늘려가는 방법으로 정렬을 진행하는 것이었습니다.

이제 왼쪽을 기준(i점)을 시작점으로 두고 하나하나씩 정렬을 진행하는 방법을 알아보겠습니다. 왼쪽 기준은 두 가지로 나뉘는데요, 왼쪽을 기준으로 안쪽을 정렬하느냐, 왼쪽 기준으로 오른쪽으로 정렬하느냐로 나뉩니다. 여기서 왼쪽(정렬된 쪽)은 이미 정렬 된 곳에 삽입한다고 해서 삽입정렬이라고 부릅니다.

 

이번에는 삽입정렬을 알아보겠습니다.

 

삽입정렬의 기본 아이디어는 새로 나온 지점 n에 대해서 안쪽에 있는 값을 하나하나씩 다 순차적으로 검사한다는 점입니다. 그런데 이미 정렬이 되어있으므로, 하나하나 정렬하는 값(j)는 i값안으로만 검사하여 그 사이를 에 삽입을 하면 되는 것입니다.

 

i지점 왼쪽 기준으로 하나하나씩 정렬하게 되면
i기준점 {i=1; i<n; i++} (i=0일 때는 할 이미 제일 왼쪽이므로 할 필요가 없습니다)
j시작점 {j=0; j<i; j++}
이런식으로 사이클이 기본적으로 생성됩니다.
그런데 문제는 왼쪽은 이미 정렬이 되어있다는 점이고, i지점은 정렬이 되어있지 않다는 점입니다. 그렇기 때문에 정렬이 되지 않은 i지점에서 정렬이 된 왼쪽 부분을 하나하나씩 검사하면 됩니다. 그런데 값을 찾았을 때 나머지 값이 전부다 오른쪽으로 밀려나야 하게 됩니다.

목표지점을 찾으면 전부 오른쪽으로 옮기게 된다.

 

이 문제를 해결하기 위해서 j를 i-1부터 시작하면서, 값이 작지 않다면 미리 한칸씩 옮겨가게 되는 방법을 만들면 됩니다.

for(i=1; i<n; i++){
key=arr[i];
int j;
// j는 거꾸로 하나하나씩 세어가게 된다.
for (j=i-1; arr[j]>key && j>=0 ; j--){
// j값이 key값보다 크다면 미리 한칸씩 밀려나게 된다.
arr[j+1] = arr[j];
}
// arr[j+1]와 arr[j+2]은 위의 루프 때문에 같은 값이다.
// 그러므로 arr[j]>key인 지점 바로 앞에 arr[j]에 key값을 삽입한다.
arr[j+1] = key;

해당 식은 기본적으로 위와 같이 세울 수 있습니다. 위와 같이 세우면 j = i-1지점부터 시작해서 arr[j] <= key인 지점이면 조건에서 벗어나서 루프를 멈추게 됩니다. 만약 j가 0이 되면 arr[j]가 가장 큰 숫자가 되므로 해당되는 부분을 조건식으로 추가해줍니다.

 

여기서 arr[j] = key가 아니라 arr[j+1] = key인 이유는 arr[j]<key인 지점에서 j값이 끝났으므로 해당 값 바로 앞인 arr[j+1]에 key값을 배치해야 됩니다.

 

 

위의 구문을 똑같이 while로도 쓸 수 있습니다.

void insertionSort(int arr[], int n){
int i, j, key;
for(i=1; i<n; i++){
key=arr[i];
j = i-1;
while(j>=0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}

 

삽입정렬은 n이 갑자기 추가 됬을 때 내부적인 값을 이용해 n의 값을 구하는 아이디어로 확장될 수 있습니다. 나중에 공부하실 dynamic programming도 이와 비슷한 아이디어인데요, dp[n] = dp[n-1] + dp[n-2];라는 점화식(dp)는 n이 추가됬을 때 내부의 값을 통해 새로운 값을 알아낸다는 점에서 유사합니다.