삽입 정렬

1. 삽입 정렬 알고리즘
2. 삽입 정렬 예
3. 삽입 정렬 알고리즘 구현
4. 삽입 정렬 알고리즘 복잡성

삽입 정렬은 간단한 비교 기반 정렬 알고리즘입니다. 이 알고리즘에서 우리는 정렬 된 하위 배열과 정렬되지 않은 하위 배열의 두 가지 하위 배열을 유지합니다. 정렬되지 않은 하위 배열의 한 요소가 정렬 된 하위 배열에서 올바른 위치를 찾아 여기에 삽입됩니다. 누군가가 손에있는 카드 한 벌을 분류하는 방식과 유사합니다. 올바른 위치에 요소를 삽입 할 때 작동하므로 삽입 정렬이라고합니다. 이 알고리즘은 작은 데이터 세트에는 효율적이지만 큰 데이터 세트에는 적합하지 않습니다.

삽입 정렬 알고리즘

n 개의 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 첫 번째 요소A[0]은 이미 정렬되어 있으며 정렬 된 하위 배열에 있습니다.

삽입 정렬 예

배열이(5,3,4,2,1)이라고 가정합니다. 삽입 정렬 알고리즘을 사용하여 정렬합니다.

• 첫 번째 반복

키 :A[1]= 3

• 두 번째 반복

키 :A[2]= 4

• 세 번째 반복

키 :A[3]= 2

• 네 번째 반복

키 :A[4]= 1

삽입 정렬 알고리즘 구현

#include <iostream>
using namespace std;

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

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

삽입 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

평균적으로 i는 삽입 정렬의 i번째 패스에서 비교된다. 따라서 n 개의 반복이있는 경우 평균 시간 복잡도는 아래와 같습니다.

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

따라서 시간 복잡도는 [Big Theta] : O(n²) 정도입니다.

• 최악의 경우

최악의 경우는 배열이 역으로 정렬되고 최대 비교 및 ​​스와핑 횟수를 수행해야하는 경우에 발생합니다.

최악의 경우 시간 복잡도는 [Big O] : O(n²)입니다.

• 베스트 케이스

최상의 경우는 배열이 이미 정렬 된 다음 외부 루프 만 n 번 실행될 때 발생합니다.

최적의 시간 복잡도는 [Big Omega] :O(n)입니다.

공간 복잡성

삽입 정렬 알고리즘의 공간 복잡성은 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(n)입니다.