**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