단순 삽입 정렬은 선택한 요소를 그보다 더 앞쪽에 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘입니다.

단순 선택 정렬과 비슷해보이지만, 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점에서 차이가 발생합니다.

<aside> 💡

“알맞은 위치에 삽입”이란?

요소를 배열의 가장 앞, 또는 뒤로 보내는 것이 아닌, 정렬 중 인접한 요소의 대수관계 비교를 통해 특정 요소의 위치를 결정한다.

</aside>

// 단순 삽입 정렬
#include <stdio.h>
#include <stdlib.h>

// 단순 삽입 정렬 함수
void insertion_sort(int* arr, int n) {
  for (int i = 1; i < n; i++) {
    int key = arr[i]; // 현재 삽입할 값
    int j = i - 1; // 이전 인덱스

    // key보다 큰 값을 오른쪽으로 이동
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key; // key를 올바른 위치에 삽입
  }
}