wiggle_sort.cpp File Reference

[Wiggle Sort Algorithm] (https://leetcode.com/problems/wiggle-sort-ii/) Implementation More...

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

Include dependency graph for wiggle_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors
namespace	wiggle_sort
	Functions for Wiggle Sort algorithm.

Functions
template<typename T >
std::vector< T >	sorting::wiggle_sort::wiggleSort (const std::vector< T > &arr)
	Function used for sorting the elements in wave form.
template<typename T >
static void	displayElements (const std::vector< T > &arr)
	Utility function used for printing the elements. Prints elements of the array after they're sorted using wiggle sort algorithm.
static void	test ()
int	main ()

Detailed Description

[Wiggle Sort Algorithm] (https://leetcode.com/problems/wiggle-sort-ii/) Implementation

Author

Roshan Kanwar

Wiggle Sort sorts the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form, if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

Function Documentation

wiggleSort()

template<typename T >

std::vector< T > sorting::wiggle_sort::wiggleSort

(

const std::vector< T > &

arr

)

Function used for sorting the elements in wave form.

Checking whether the even indexed elements are greater than their adjacent odd elements. Traversing all even indexed elements of the input arr. If current element is smaller than the previous odd element, swap them. If current element is smaller than the next odd element, swap them.

Parameters

arr	input array (unsorted elements)

Examples

/Users/runner/work/C-Plus-Plus/C-Plus-Plus/sorting/wiggle_sort.cpp.

                                                                        {
    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
}

Here is the call graph for this function: