Insertion Sort

#include <iostream>
using namespace std;
 
void insertion_sort(int *arr, int n){
  int i,j;
  for(i = 1; i < n; i++){ // 배열의 두번째 원소부터 시작함
    int tmp = arr[i];
    for(j = i; j > 0 && arr[j - 1] > tmp; j--) {// j가 0보다 크고, arr[j - 1] 값이 tmp보다 클 때 반복함
      arr[j] = arr[j-1];
    }
    arr[j] = tmp;
  }
}
 
int main() {
    int arr[5] = {3,2,5,9,1};
    for(auto i : arr){
        cout << i << ' ';
    }
    cout << '\n';
    insertion_sort(arr,5);
    for(auto i : arr){
        cout << i << ' ';
    }
    return 0;
}