Thursday, February 5, 2015

Wave sort an array.

Question: Given an unsorted array, sort it in wave form. Wave sorted array looks like as follows:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]...

Solution: Traverse all elements at even positions in the array and compare nth element with it's previous element(n-1th), if it is greater than previous, swap previous and current.
Now, again compare the nth element with its next element(n + 1th), if it is greater than next, swap next and current.

Implementation:

void sortWave(int* arr, int len)
{
        if(arr == NULL || len == 0 || len == 1)
                return;
        for(int i = 0; i < len; i+=2)
        {
                if(i>0 && arr[i-1] > arr[i])
                        std::swap(arr[i], arr[i-1]);
                if(i<len-1 && arr[i] < arr[i+1])
                        std::swap(arr[i], arr[i+1]);
        }

}

Complexity: O(n)

Alternative approach: Sort the array and swap adjacent elements. But the complexity of this approach will be O(nlogn)

No comments:

Post a Comment