Wave sort

© 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]