wiggle_sort.cpp

Go to the documentation of this file.

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

namespace sorting {
namespace wiggle_sort {

template <typename T>  // this allows to have vectors of ints, double, float,
                       // etc
std::vector<T> wiggleSort(const std::vector<T> &arr) {
    uint32_t size = arr.size();
 
    std::vector<T> out(
        arr);  // create a copy of input vector. this way, the original input
               // vector does not get modified. a sorted array is is returned.
 
    for (int i = 0; i < size; i += 2) {
        if (i > 0 && out[i - 1] > out[i]) {
            std::swap(out[i], out[i - 1]);  // swapping the two values
        }
 
        if (i < size - 1 && out[i] < out[i + 1]) {
            std::swap(out[i], out[i + 1]);  // swapping the two values
        }
    }
 
    return out;  // returns the sorted vector
}
}  // namespace wiggle_sort
}  // namespace sorting

template <typename T>
static void displayElements(const std::vector<T> &arr) {
    uint32_t size = arr.size();
 
    std::cout << "Sorted elements are as follows: ";
 
    std::cout << "[";
 
    for (int i = 0; i < size; i++) {
        std::cout << arr[i];
        if (i != size - 1) {
            std::cout << ", ";
        }
    }
 
    std::cout << "]" << std::endl;
}

static void test() {
    std::srand(std::time(nullptr));  // initialize random number generator
 
    std::vector<float> data1(100);
    for (auto &d : data1) {  // generate random numbers between -5.0 and 4.99
        d = float(std::rand() % 1000 - 500) / 100.f;
    }
 
    std::vector<float> sorted = sorting::wiggle_sort::wiggleSort<float>(data1);
 
    displayElements(sorted);
 
    for (uint32_t j = 0; j < data1.size(); j += 2) {
        assert(data1[j] <= data1[j + 1] &&
               data1[j + 1] >= data1[j + 2]);  // check the validation condition
    }
 
    std::cout << "Test 1 passed\n";
}

int main() {
    test();
    return 0;
}