[c++] 삽입 정렬

12 Dec 2023

삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 하나씩 값을 비교하여 정렬하는 방식으로 동작합니다.

알고리즘 개요

배열의 두 번째 원소부터 시작하여 현재 위치의 값을 key 변수에 복사합니다.
key 값을 이전 위치의 값과 비교하여 큰 값이 나올 때까지 이전 위치의 값을 현재 위치로 복사합니다.
이전 위치의 값이 key보다 작은 경우, key 값을 현재 위치에 복사합니다.
배열의 모든 원소에 대해 위 과정을 반복합니다.

C++ 코드 예시

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
  int i, key, j;
  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;
  }
}

int main() {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);

  insertionSort(arr, n);

  cout << "정렬된 배열: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

위 코드는 삽입 정렬을 구현한 예시입니다. insertionSort 함수는 삽입 정렬을 수행하고, main 함수에서 해당 함수를 호출하여 배열을 정렬합니다.

마치며

이렇게 C++을 사용하여 삽입 정렬을 구현할 수 있습니다. 이 알고리즘은 작은 크기의 배열에 대해 효율적이며, 코드 또한 간단하기 때문에 이해하기 쉽습니다. 유사한 정렬 알고리즘을 학습할 때 이해하기 쉽고 직관적인 예제로 활용할 수 있을 것입니다.

또한, 이러한 기본적인 정렬 알고리즘을 통해 정렬 알고리즘의 기본 동작 원리를 파악하고, 성능 향상을 위해 다양한 알고리즘을 학습할 수 있습니다.

참고문헌: GeeksforGeeks - Insertion Sort