wiggle_sort.cpp File Reference

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

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

Include dependency graph for wiggle_sort.cpp:

Go to the source code of this file.

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] >= …..

Definition in file wiggle_sort.cpp.

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.

Definition at line 54 of file 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
}