삽입 정렬 알고리즘 구현 (C++)

삽입 정렬에 대해 정리해보자.

삽입 정렬은, 선택 정렬 그리고 버블 정렬과 함께 대표적인 시간 복잡도 O(n^2) 알고리즘이다.

하지만 삽입 정렬은, 필요할 때까지만 삽입(스왑)이 일어나기 때문에, 정렬할 배열이 거의 정렬되어 있는 상태라면 다른 선택 정렬, 버블 정렬보다 훨씬 빠른 속도를 보여준다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{   
 
    int a[10] = {-100, 10, 13, -5, 4, 12 , -5, 6, -1000, 2};
    
    int n = 10;
   
   //삽입 정렬 오름차순
   for(int i = 0 ; i < n - 1 ; i++){ //while문 내부 비교 구문에서, j와 j+1을 비교하기 때문에 n-2까지만 들어가도록
       int j = i;
       while(j >= 0 && a[j] > a[j + 1]){ //i의 앞쪽까지는 이미 정렬이 돼있다고 본다.
           swap(a[j], a[j + 1]); //따라서 swap이 일어나지 않으면 그 cycle의 정렬은 끝난 것
           j--;
       }
   }
    
    for(int i = 0 ; i < 10 ; i++)
        cout << a[i] << ' ';
 
    return 0;
}