Published on

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

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

Question

Wiggle sort: Given an unsorted array A, reorder it such that A[0]<A[1]>A[2]<A[3]...A[0] < A[1] > A[2] < A[3] ... . For example, one possible answer for input [3,1,4,2,6,5][3, 1, 4, 2, 6, 5] is [1,3,2,5,4,6][1, 3, 2, 5, 4, 6]. Can you do it in O(n)O(n) time using only O(1)O(1) space?

Solution

Precondition

input array must not have duplicate value, otherwise occasionally wiggleness cannot be accomplished.

Solution 1: Find Median and Swap Even and Odd

Oueline

First we find median value of the array.
Median in this context = floor((n−1)/2)floor((n-1)/2)-th value of the array on zero based indexing.

Traverse the array to find the element x whose index is even and whose value >> median, and find the element y whose index is odd and whose value ≤\le median. If both are found, swap x and y.

Time complexity: O(n)O(n).

Code
/*
Precondition: input array must not have duplicate value,
otherwise occasionally wiggleness cannot be accomplished.

First we find median value of the array.
Median in this context = floor((n-1)/2)-th value of the array
on zero based indexing

Traverse the array to find the element x whose index is even and
whose value > median, and find the element y whose index is odd and
whose value <= median.
If both are found, swap x and y.

Time complexity: O(n)
*/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

int quickselect_helper(std::vector<int>& v, const size_t i_l, const size_t i_r,
                       const size_t k) {
    // if the array contains only single element, return it
    if (i_l == i_r) return v[i_l];

    // take the last element as a pivot and partition
    auto firsthigh{i_l};
    for (auto i{i_l}; i < i_r; ++i) {
        if (v[i] < v[i_r]) {
            std::swap(v[i], v[firsthigh]);
            ++firsthigh;
        }
    }
    std::swap(v[i_r], v[firsthigh]);

    if (k < firsthigh)
        return quickselect_helper(v, i_l, firsthigh - 1, k);
    else if (k > firsthigh)
        return quickselect_helper(v, firsthigh + 1, i_r, k);
    else
        return v[k];
}

int find_median(std::vector<int>& v) {
    std::random_shuffle(v.begin(), v.end());
    return quickselect_helper(v, 0, v.size() - 1, (v.size() - 1) / 2);
}

void wiggle_sort(std::vector<int>& v) {
    if (v.size() < 2) return;

    auto median{find_median(v)};

    size_t i_ev{0};
    size_t i_od{1};
    while (true) {
        while (i_ev < v.size() && v[i_ev] <= median) i_ev += 2;
        while (i_od < v.size() && median < v[i_od]) i_od += 2;
        if (i_ev >= v.size() && i_od >= v.size()) break;
        std::swap(v[i_ev], v[i_od]);
    }
}

bool check_wiggled(const std::vector<int>& v) {
    for (auto i{0}; i < v.size(); ++i) {
        if (i & 1) {
            if (v[i] <= v[i - 1]) return false;
            if (i != v.size() - 1 && v[i] <= v[i + 1]) return false;
        } else {
            if (i != 0 && v[i - 1] < v[i]) return false;
            if (i != v.size() - 1 && v[i + 1] < v[i]) return false;
        }
    }
    return true;
}

void println(auto rem, auto const& v) {
    for (std::cout << rem; auto e : v) std::cout << e << ' ';
    std::cout << '\n';
}

int main(int argc, char const* argv[]) {
    std::vector v{1};
    wiggle_sort(v);
    println("Sort 1: v = ", v);
    assert(check_wiggled(v));

    v = {2, 1};
    wiggle_sort(v);
    println("Sort 2: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 3: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1, 4, 5, 6, 7, 8, 9};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 4-1: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1, 4, 5, 6, 7, 8, 9, 10};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 4-2: v = ", v);
    assert(check_wiggled(v));

    return 0;
}

Solution 2: Partition Using Special Indexing

Oueline

We partition the array using median value of the array as pivot.
Median in this context = floor((n−1)/2)floor((n-1)/2)-th value of the array on zero based indexing.

Here, we use special indexing system so that all element of odd index (original) come after all elements of even index (original). Example: the order [e0,e1,e2,e3,e4][e_0, e_1, e_2, e_3, e_4] gets converted to [e0,e2,e4,e1,e3][e_0, e_2, e_4, e_1, e_3].

After partitioning, the last element of even index (original) is median and all elements of even index is less than or equal to median, while all elements of odd index is greater than median.

Time complexity: O(n)O(n).

Code
/*
Precondition: input array must not have duplicate value,
otherwise occasionally wiggleness cannot be accomplished.

We partition the array using median value of the array as pivot.
Median in this context = floor((n-1)/2)-th value of the array
on zero based indexing

Here, we use special indexing system so that
all element of odd index (original) come after all elements of
even index (original).
Example: the order [e0, e1, e2, e3, e4] gets converted
to [e0, e2, e4, e1, e3].

After partitioning, the last element of even index (original) is
median and all elements of even index is less than or equal to
median, while all elements of odd index is greater than median.

Time complexity: O(n)
*/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

constexpr size_t sp_idx(const size_t i, const size_t len) {
    if (i < ((len + 1) >> 1)) return i * 2;
    return 2 * (i - ((len + 1) >> 1)) + 1;
}

void partition_by_kth_elem(std::vector<int>& v, const size_t i_l,
                           const size_t i_r, const size_t k) {
    // if the array contains only single element, exit
    if (i_l == i_r) return;

    // take the last element as a pivot and partition
    const auto len{v.size()};
    auto firsthigh{i_l};
    for (auto i{i_l}; i < i_r; ++i) {
        if (v[sp_idx(i, len)] < v[sp_idx(i_r, len)]) {
            std::swap(v[sp_idx(i, len)], v[sp_idx(firsthigh, len)]);
            ++firsthigh;
        }
    }
    std::swap(v[sp_idx(i_r, len)], v[sp_idx(firsthigh, len)]);

    if (k < firsthigh)
        partition_by_kth_elem(v, i_l, firsthigh - 1, k);
    else if (k > firsthigh)
        partition_by_kth_elem(v, firsthigh + 1, i_r, k);
}

void wiggle_sort(std::vector<int>& v) {
    std::random_shuffle(v.begin(), v.end());
    partition_by_kth_elem(v, 0, v.size() - 1, (v.size() - 1) / 2);
}

bool check_wiggled(const std::vector<int>& v) {
    for (auto i{0}; i < v.size(); ++i) {
        if (i & 1) {
            if (v[i] <= v[i - 1]) return false;
            if (i != v.size() - 1 && v[i] <= v[i + 1]) return false;
        } else {
            if (i != 0 && v[i - 1] < v[i]) return false;
            if (i != v.size() - 1 && v[i + 1] < v[i]) return false;
        }
    }
    return true;
}

void println(auto rem, auto const& v) {
    for (std::cout << rem; auto e : v) std::cout << e << ' ';
    std::cout << '\n';
}

int main(int argc, char const* argv[]) {
    std::vector v{1};
    wiggle_sort(v);
    println("Sort 1: v = ", v);
    assert(check_wiggled(v));

    v = {2, 1};
    wiggle_sort(v);
    println("Sort 2: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 3: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1, 4, 5, 6, 7, 8, 9};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 4-1: v = ", v);
    assert(check_wiggled(v));

    v = {3, 2, 1, 4, 5, 6, 7, 8, 9, 10};
    assert(!check_wiggled(v));
    wiggle_sort(v);
    println("Sort 4-2: v = ", v);
    assert(check_wiggled(v));

    return 0;
}