Published on

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

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-24

Question

Give an efficient algorithm to rearrange an array of n keys so that all the negative keys precede all the non-negative keys. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. How fast is your algorithm?

Solution

Outline

Partition the array so that negative values can be moved to forward using the same algorithm used by partitioning part in Quicksort.

Code

/*
Partition the array so that negative values can be moved to forward.
*/
#include <algorithm>
#include <cassert>
#include <vector>
void neg_forward(std::vector<int>& v) {
    size_t firstpos{0};
    for (auto i{0}; i < v.size(); i++) {
        if (v[i] < 0) {
            std::swap(v[i], v[firstpos++]);
        }
    }
}

int main(int argc, char const* argv[]) {
    std::vector<int> v{-1};
    neg_forward(v);
    assert(v == (std::vector{-1}));
    v = {0};
    neg_forward(v);
    assert(v == (std::vector{0}));
    v = {1};
    neg_forward(v);
    assert(v == (std::vector{1}));

    v = {-1, 1};
    neg_forward(v);
    assert(v == (std::vector{-1, 1}));
    v = {1, -1};
    neg_forward(v);
    assert(v == (std::vector{-1, 1}));

    v = {1, -1, 2, -2, 3};
    neg_forward(v);
    assert(v == (std::vector{-1, -2, 2, 1, 3}));

    v = {18, -7,  -15, -18, 5,  11, -19, -2, 11,  2,
         -8, -13, -2,  8,   17, 2,  14,  0,  -11, 19};
    neg_forward(v);
    for (auto i{0}; i <= 8; ++i) assert(v[i] < 0);
    for (auto i{9}; i < v.size(); ++i) assert(v[i] >= 0);

    return 0;
}