삽입정렬

삽입 정렬

• 삽입정렬이란?
  • 배열을 정렬할 때 현재 원소를 적절한 위치에 삽입하는 방식으로 동작
  • 시간 복잡도는 최악의 경우$O(N^2)$, 평균 $O(N)$
• 동작

  

  • 배열의 두 번째 원소부터 시작해 현재 원소를 앞의 정렬된 부분과 비교
  • 현재 원소보다 큰 값들은 한칸씩 뒤로 밀어줌
  • 적절한 위치에 현재 원소 삽입
  • 마지막 원소까지 반복
• 시간 복잡도
  • 최선의 경우(이미 정렬된 경우) : O(N)
  • 평균의 경우 : $O(N^2)$
  • 최악의 경우(역순으로 정렬된 경우) : $O(N^2)$
• 특징
  • 추가적인 메모리 사용이 거의없음
  • 같은 값의 원소들이 원래 순서 유지
  • 거의 정렬된 데이터에 강함
  • 큰 데이터에는 비효율적임
• 구현

#include <iostream>
using namespace std;

void insertionSort(int arr[5], 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;
    }
}

int main() {
    int arr[5] = {5, 3, 4, 1, 2};
    int n = 5;

    insertionSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}