Insertion Sort in C++
最良時間計算量: O(N)
平均/最悪時間計算量: O(N^2)
code:cpp
void print_int_vec(const std::vector<int> &a)
{
for (auto elem : a)
{
std::cout << elem << " ";
}
std::cout << std::endl;
}
void insertion_sort(std::vector<int> &a)
{
size_t vec_length = a.size();
bool changed = false;
// expand sorted sub-list one by one
for (size_t target_i = 1; target_i < vec_length; target_i++)
{
continue;
size_t insert_idx = target_i;
do
{
insert_idx--;
// we can assume a..i is sorted already at this point }
}
int main()
{
int N;
std::cin >> N;
std::vector<int> A(N);
for (size_t i = 0; i < N; i++)
insertion_sort(A);
print_int_vec(A);
return 0;
}