Dutch national flag problem: Difference between revisions
Content added Content deleted
(Added C++ implementation) |
|||
Line 126: | Line 126: | ||
Original Order: WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE |
Original Order: WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE |
||
After Sorting: WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE</pre> |
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}}== |
=={{header|D}}== |