[자료구조/C++] 정렬(Sorting) : 삽입정렬(Insertion Sort)

전공 수업과 교안을 바탕으로 개인적으로 공부한 내용입니다. 공부 내용을 정리하는 과정에서 잘못된 정보가 있을 수 있으니, 참고용으로만 봐주시면 감사하겠습니다. 피드백은 언제든 환영입니다! 😊

---

✔️ 삽입정렬 (Insertion Sort)

예를 들어 {-∞, 30, 20, 40, 10, 5, 10,30, 15} 로 구성된 배열 A가 있다고 하자. (구현의 편리함을 위해 0번째 인덱스는 음의 무한대 값을 dummy값으로 설정했다)

삽입 정렬은 배열의 두번째 값부터 순서대로 비교할 값을 설정하여 비교할 값의 인덱스보다 이전에 있는 배열 값들을 하나씩 비교해 적절한  위치를 찾고, 찾은 위치를 기준으로 나머지 배열 값들은 뒤로 옮기고, 찾아둔 적절한 위치에 해당 비교한 값을 삽입하여 정렬하는 알고리즘이다.

 

이해를 위해 다음 그림을 참고하자.

 

 

먼저 인덱스 값이 2인 배열 값 20을 이전 인덱스 배열 값과 비교한다.

즉, step 1에서는 A[2]가 비교될 값이며 A[1]과 비교를 진행하고 A[2]가 A[1]보다 작으므로 A[2]값은 인덱스 1값에 들어가야 한다. 따라서 A[1]의 값을 뒤로 옮기고 A[2]의 값이였던 20을 인덱스 1의 위치로 삽입한다.

 

마찬가지로 step 2에서는 A[3]이 비교될 값이며 해당 인덱스의 이전 인덱스 배열 값인 A[2], A[1]과 비교를 진행한다. 이때 A[3]보다 작은 배열 값이 존재하지 않으므로 A[3]의 적절한 위치는 인덱스 3이 되고, 따로 위치를 변경할 필요가 없다.

 

step 3의 경우 A[4]가 비교될 값이며 해당 인덱스의 이전 인덱스 배열 값인 A[3], A[2], A[1]과 비교를 진행해 A[4]보다 작은 값이 있는 경우 해당 값을 뒤로 옮기면서 적절한 위치를 찾아 값을 삽입하는 방식으로 계속 반복해 주면 된다.

 

따라서 삽입정렬을 끝까지 수행하면 다음과 같이 배열이 정렬된다.

 

 

✔️ 구현 코드

#include <iostream>
#include <limits>
using namespace std;

void InsertionSort(int A[], int n) {
  int value, j;

  for (int i=2; i<=n; i++) {
    value = A[i];
    j = i;

    while (A[j-1] > value) {
      A[j] = A[j-1];
      j--;
    }

    A[j]=value;
  }
}

int main() {
  int dummy = numeric_limits<int>::min();
  int A[] = {dummy, 30, 20, 40, 10, 5, 10, 30, 15};
  int size = sizeof(A) / sizeof(A[0]) - 1;

  InsertionSort(A, size);

  for (int i=1; i<=size; i++) {
    cout << A[i] << " ";
  }
}