Insertion Sort in C++
最良時間計算量: O(N)
平均/最悪時間計算量: O(N^2)
code:cpp
#include <iostream>
#include <vector>
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++)
{
if (atarget_i - 1 <= atarget_i)
continue;
int target = atarget_i;
// sort sub-list(a0:i)
size_t insert_idx = target_i;
do
{
ainsert_idx = ainsert_idx - 1;
insert_idx--;
} while (insert_idx > 0 && ainsert_idx - 1 > target);
ainsert_idx = target;
// 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++)
std::cin >> Ai;
insertion_sort(A);
print_int_vec(A);
return 0;
}