Anonymous user
Dutch national flag problem: Difference between revisions
Added C++ implementation
(Added C++ implementation) |
|||
Line 126:
Original Order: WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE
After Sorting: WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE</pre>
=={{header|C++}}==
<lang cpp>#include <algorithm>
#include <iostream>
// Dutch national flag problem
template <typename BidIt, typename T>
void dnf_partition(BidIt first, BidIt last, const T& low, const T& high)
{
for (BidIt next = first; next != last; ) {
if (*next < low) {
std::iter_swap(first++, next++);
} else if (!(*next < high)) {
std::iter_swap(next, --last);
} else {
++next;
}
}
}
enum Colors { RED, WHITE, BLUE };
void print(const Colors *balls, size_t size)
{
static const char *label[] = { "red", "white", "blue" };
std::cout << "Balls:";
for (size_t i = 0; i < size; ++i) {
std::cout << ' ' << label[balls[i]];
}
std::cout << "\nSorted: " << std::boolalpha << std::is_sorted(balls, balls + size) << '\n';
}
int main()
{
Colors balls[] = { RED, WHITE, BLUE, RED, WHITE, BLUE, RED, WHITE, BLUE };
std::random_shuffle(balls, balls + 9);
print(balls, 9);
dnf_partition(balls, balls + 9, WHITE, BLUE);
print(balls, 9);
}</lang>
{{out}}
<pre>
Balls: blue white red blue red blue white red white
Sorted: false
Balls: red red red white white white blue blue blue
Sorted: true
</pre>
=={{header|D}}==
| |||