sort/insertion-sort.hpp

• View this file on GitHub
• Last update: 2022-11-17 17:07:52+09:00
• Include: #include "sort/insertion-sort.hpp"

Verified with

• verify/AOJ-ALDS1_1_A.test.cpp

Code

#pragma once
template <class T>
void insertionSort(vector<T> &target, bool print){
  int n = target.size();
  for(int i = 1; i < n; ++i){
    T v = target[i];
    int j = i-1;
    while(j >= 0 && target[j] > v){
      target[j+1] = target[j];
      --j;
    }
    target[j+1] = v;
    if(print){
      for(int i = 0; i < n; ++i){
        cout << (i ? " ": "") << target[i];
      }
      cout << endl;
    }
  }
}

#line 2 "sort/insertion-sort.hpp"
template <class T>
void insertionSort(vector<T> &target, bool print){
  int n = target.size();
  for(int i = 1; i < n; ++i){
    T v = target[i];
    int j = i-1;
    while(j >= 0 && target[j] > v){
      target[j+1] = target[j];
      --j;
    }
    target[j+1] = v;
    if(print){
      for(int i = 0; i < n; ++i){
        cout << (i ? " ": "") << target[i];
      }
      cout << endl;
    }
  }
}

Back to top page