The Wiggle Sort Algorithm on Array of Integers

The Wiggle Sorting may produce more than one possible outcome as long as the final sorted array satisfies: nums[0] <= nums[1] >= nums[2] <= nums[3] Given an unsorted array nums.

For example, if input numbers = [3, 5, 2, 1, 6, 4] and one possible Wiggle Sorted answer is [3, 5, 1, 6, 2, 4]

Sorting with O(nlogn)

If we sort the original array of numbers, we need runtime complexity of O(nlogn). The next step is to swap two elements if necessary to make it conform to the wiggle sorting characteristics.

1
2
3
4
5
6
7
8
9

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(begin(nums), end(nums)); // sorting takes O(nlogn)
        for (int i = 1; i + 1 < nums.size(); i += 2) {
            swap(nums[i], nums[i + 1]); 
        }
    }
};

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(begin(nums), end(nums)); // sorting takes O(nlogn)
        for (int i = 1; i + 1 < nums.size(); i += 2) {
            swap(nums[i], nums[i + 1]); 
        }
    }
};

O(n) one pass Wiggle Sort Algorithm

Can we do better in O(n)? Boolean of value false is essentially converted implicitly to zero while true is converted to one. Thus, at first position, we check if the element[i] is smaller or equal to element[i+1], and swap if it is not. At next iteration, we check if it is bigger or equal and so on.

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    void wiggleSort(vector<int>& nums) {        
        for (int i = 0; i + 1 < nums.size(); ++ i) {
            if ((i % 2) == (nums[i] < nums[i + 1])) {
                swap(nums[i], nums[i + 1]);
            }
        }
    }
};

class Solution {
public:
    void wiggleSort(vector<int>& nums) {        
        for (int i = 0; i + 1 < nums.size(); ++ i) {
            if ((i % 2) == (nums[i] < nums[i + 1])) {
                swap(nums[i], nums[i + 1]);
            }
        }
    }
};

–EOF (The Ultimate Computing & Technology Blog) —