© Parineeth M R

** Question 43. Re-arrange the elements in an array like a wave so that the values of the array alternately increase and decrease. The elements in the array are unique. For instance, if A = {50, 10, 20, 30, 40}, after re-arranging A can be {10, 30, 20, 50, 40} where in the value of consecutive elements alternately increases and decreases**

This problem can be solved in O(nlogn) without additional memory as follows:

1. First sort the entire array in ascending order. So {50, 10, 20, 30, 40} becomes {10, 20, 30, 40, 50}

2. Then starting from index 1 in the array, swap the neighboring elements. So {10, 20, 30, 40, 50} becomes {10, 30, 20, 50, 40}

## C/C++

/* a: array that has to be sorted so that the values in it alternatively increase and decrease. The elements should be unique length: number of elements in the array. should be >= 1 */ void wave_sort(int a[], int length) { int i, temp; /*Sort the elements in ascending order*/ qsort(a, length, sizeof(int), cmp_function); /*Swap the alternate elements*/ for (i = 1; i < length - 1; i += 2) { temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } }

## Java

/* a: non-empty array that has to be sorted so that the values in it alternatively increase and decrease. The elements should be unique */ public static void waveSort(int[] a) { /*Sort the elements in ascending order*/ Arrays.sort(a); /*Swap the alternate elements*/ for (int i = 1; i < a.length - 1; i += 2) { int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } }

## Python

#a: non-empty list that has to be sorted so that the values in it # alternatively increase and decrease. The elements should be unique def wave_sort(a) : #Sort the elements in ascending order a.sort() #Swap the neighboring elements for i in range(1, len(a) - 1, 2): a[i], a[i+1] = a[i+1], a[i]