In preparing this answer this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:
Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$
I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:
#include <algorithm>
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
This is the code in context with a short test program.
testweave.cpp
#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>
std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
if (v.begin() == v.end()) {
return out << "{}";
}
out << "{" << *v.begin();
for (auto it = v.begin()+1; it != v.end(); ++it) {
out << ", " << *it;
}
return out << "}";
}
#define SHOW(x) std::cout << # x " = " << x << '\n'
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
int main()
{
std::vector<int> v;
for (int i=0; i < 10; ++i) {
std::cout << '\n';
SHOW(v.size());
SHOW(v);
weave(v.begin(), v.end());
SHOW(v);
v.push_back(i);
std::sort(v.begin(), v.end());
}
}
I'm particularly interested in whether there is a more efficient algorithm for this.
In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:
Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$
I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:
#include <algorithm>
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
This is the code in context with a short test program.
testweave.cpp
#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>
std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
if (v.begin() == v.end()) {
return out << "{}";
}
out << "{" << *v.begin();
for (auto it = v.begin()+1; it != v.end(); ++it) {
out << ", " << *it;
}
return out << "}";
}
#define SHOW(x) std::cout << # x " = " << x << '\n'
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
int main()
{
std::vector<int> v;
for (int i=0; i < 10; ++i) {
std::cout << '\n';
SHOW(v.size());
SHOW(v);
weave(v.begin(), v.end());
SHOW(v);
v.push_back(i);
std::sort(v.begin(), v.end());
}
}
I'm particularly interested in whether there is a more efficient algorithm for this.
In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:
Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$
I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:
#include <algorithm>
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
This is the code in context with a short test program.
testweave.cpp
#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>
std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
if (v.begin() == v.end()) {
return out << "{}";
}
out << "{" << *v.begin();
for (auto it = v.begin()+1; it != v.end(); ++it) {
out << ", " << *it;
}
return out << "}";
}
#define SHOW(x) std::cout << # x " = " << x << '\n'
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
int main()
{
std::vector<int> v;
for (int i=0; i < 10; ++i) {
std::cout << '\n';
SHOW(v.size());
SHOW(v);
weave(v.begin(), v.end());
SHOW(v);
v.push_back(i);
std::sort(v.begin(), v.end());
}
}
I'm particularly interested in whether there is a more efficient algorithm for this.
Weaving an array
In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:
Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$
I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:
#include <algorithm>
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
This is the code in context with a short test program.
testweave.cpp
#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>
std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
if (v.begin() == v.end()) {
return out << "{}";
}
out << "{" << *v.begin();
for (auto it = v.begin()+1; it != v.end(); ++it) {
out << ", " << *it;
}
return out << "}";
}
#define SHOW(x) std::cout << # x " = " << x << '\n'
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
for (++first; first != last; ++first) {
std::reverse(first, last);
}
}
int main()
{
std::vector<int> v;
for (int i=0; i < 10; ++i) {
std::cout << '\n';
SHOW(v.size());
SHOW(v);
weave(v.begin(), v.end());
SHOW(v);
v.push_back(i);
std::sort(v.begin(), v.end());
}
}
I'm particularly interested in whether there is a more efficient algorithm for this.