# Wave sort

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]

```