snippetcppMinor
Insertion sort C++14 implementation
Viewed 0 times
insertionimplementationsort
Problem
I have implemented insertion sort using C++. Is there any way to improve my code and is it CppCoreGuideline compliant? As I passed the vector as
const in print method, do I need to specify const in range for loop?/*
* Insertion Sort
*/
#include
#include
void insertionSort(std::vector &v);
void print(const std::vector &v);
int main()
{
std::ios_base::sync_with_stdio(false);
std::vector v {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
// Print the vector before sorting.
print(v);
// Sort
insertionSort(v);
// Print the vector after sorting.
print(v);
return 0;
}
void insertionSort(std::vector &v) {
for (auto i = v.begin() + 1; i != v.end(); ++i) {
int key = *i;
auto j = i - 1;
while (j >= v.begin() && *j > key) {
*(j+1) = *j;
--j;
}
*(j+1) = key;
}
return;
}
void print(const std::vector &v) {
for (const auto &i : v) {
std::cout << i << " ";
}
std::cout << "\n";
}Solution
Advice 1
In your
Advice 2
Making your insertion sort generic is easy:
Advice 3
Making your
Hope that helps.
In your
insertionSort you can remove the last statement (return). Advice 2
Making your insertion sort generic is easy:
template
void insertion_sort(RandIt begin, RandIt end)
{
for (auto i = begin + 1; i != end; ++i)
{
auto key = *i;
auto j = i - 1;
while (j >= begin and *j > key)
{
*(j + 1) = *j;
--j;
}
*(j + 1) = key;
}
}
template
void insertion_sort(Container& cont)
{
insertion_sort(std::begin(cont), std::end(cont));
}Advice 3
Making your
print function generic is not hard either:template
void print(RandIt begin, RandIt end)
{
using value_type = typename std::iterator_traits::value_type;
std::copy(begin, end, std::ostream_iterator(std::cout, ", "));
std::cout
void print(const Container& container)
{
print(std::begin(container), std::end(container));
}Hope that helps.
Code Snippets
template<typename RandIt>
void insertion_sort(RandIt begin, RandIt end)
{
for (auto i = begin + 1; i != end; ++i)
{
auto key = *i;
auto j = i - 1;
while (j >= begin and *j > key)
{
*(j + 1) = *j;
--j;
}
*(j + 1) = key;
}
}
template<typename Container>
void insertion_sort(Container& cont)
{
insertion_sort(std::begin(cont), std::end(cont));
}template<typename RandIt>
void print(RandIt begin, RandIt end)
{
using value_type = typename std::iterator_traits<RandIt>::value_type;
std::copy(begin, end, std::ostream_iterator<value_type>(std::cout, ", "));
std::cout << std::endl;
}
template<typename Container>
void print(const Container& container)
{
print(std::begin(container), std::end(container));
}Context
StackExchange Code Review Q#152687, answer score: 6
Revisions (0)
No revisions yet.