Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E4-4'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-4

Question

Assume that we are given n pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Solution

Outline

FIrst, traverse input array, and classify each color and save them.
Next, sort the array using saved data, in order that is all reds before all blues before all yellows.

Code

// FIrst, traverse input array, and classify each color and save them.
// Next, sort the array using saved data, in order that is all reds before all
//  blues before all yellows.

//  Complexity: n(first traversal)+n(each stored color array traversal) = Θ(n)

#include <algorithm>
#include <array>
#include <cassert>
#include <utility>
#include <vector>
enum class Color { red, blue, yellow };
constexpr auto operator+(Color a) noexcept {
    return static_cast<std::underlying_type_t<Color>>(a);
}

using colored_ints = std::vector<std::pair<int, Color>>;

void sort_colored_int_array(colored_ints& ci_s) {
    std::array<std::vector<int>, +Color::yellow + 1> store_each_clr{};
    for (const auto& ci : ci_s) {
        store_each_clr[+ci.second].push_back(ci.first);
    }
    size_t idx{0};
    for (size_t j = 0; j < store_each_clr.size(); j++) {
        for (auto&& v_ci : store_each_clr[j]) {
            ci_s[idx++] = {v_ci, static_cast<Color>(j)};
        }
    }
}

int main(int argc, char const* argv[]) {
    colored_ints ci_s{{1, Color::blue}};
    sort_colored_int_array(ci_s);
    assert(ci_s == (colored_ints{{1, Color::blue}}));
    ci_s = {{2, Color::red}};
    sort_colored_int_array(ci_s);
    assert(ci_s == (colored_ints{{2, Color::red}}));
    ci_s = {{4, Color::yellow}};
    sort_colored_int_array(ci_s);
    assert(ci_s == (colored_ints{{4, Color::yellow}}));

    ci_s = {{1, Color::yellow}, {2, Color::yellow}};
    sort_colored_int_array(ci_s);
    assert(ci_s == (colored_ints{{1, Color::yellow}, {2, Color::yellow}}));

    ci_s = {{1, Color::blue},
            {3, Color::red},
            {4, Color::blue},
            {6, Color::yellow},
            {9, Color::red}};
    sort_colored_int_array(ci_s);
    assert(ci_s == (colored_ints{
                       {3, Color::red},
                       {9, Color::red},
                       {1, Color::blue},
                       {4, Color::blue},
                       {6, Color::yellow},
                   }));
    return 0;
}