Sort an array in wave form
Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..
Examples:
Input: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
{20, 5, 10, 2, 80, 6, 100, 3} OR
any other array that is in wave form
Input: arr[] = {20, 10, 8, 6, 4, 2}
Output: arr[] = {20, 8, 10, 4, 6, 2} OR
{10, 8, 20, 2, 6, 4} OR
any other array that is in wave form
Input: arr[] = {2, 4, 6, 8, 10, 20}
Output: arr[] = {4, 2, 8, 6, 20, 10} OR
any other array that is in wave form
Input: arr[] = {3, 6, 5, 10, 7, 20}
Output: arr[] = {6, 3, 10, 5, 20, 7} OR
any other array that is in wave form
A Simple Solution is to use sorting. First sort the input array, then swap all adjacent elements.
For example, let the input array be {3, 6, 5, 10, 7, 20}. After sorting, we get {3, 5, 6, 7, 10, 20}. After swapping adjacent elements, we get {5, 3, 7, 6, 20, 10}.
[ad type=”banner”]Below are implementations of this simple approach.
C++ Implementation of Sort an array in wave form:
[pastacode lang=”cpp” manual=”%2F%2F%20A%20C%2B%2B%20program%20to%20sort%20an%20array%20in%20wave%20form%20using%0A%2F%2F%20a%20sorting%20function%0A%23include%3Ciostream%3E%0A%23include%3Calgorithm%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20method%20to%20swap%20two%20numbers.%0Avoid%20swap(int%20*x%2C%20int%20*y)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*x%3B%0A%20%20%20%20*x%20%3D%20*y%3B%0A%20%20%20%20*y%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20sorts%20arr%5B0..n-1%5D%20in%20wave%20form%2C%20i.e.%2C%20%0A%2F%2F%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D%20%3E%3D%20arr%5B5%5D..%0Avoid%20sortInWave(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Sort%20the%20input%20array%0A%20%20%20%20sort(arr%2C%20arr%2Bn)%3B%0A%20%0A%20%20%20%20%2F%2F%20Swap%20adjacent%20elements%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-1%3B%20i%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20swap(%26arr%5Bi%5D%2C%20%26arr%5Bi%2B1%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20sortInWave(arr%2C%20n)%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”c++” highlight=”” provider=”manual”/]Output:
2 1 10 5 49 23 90
JAVA Implementation of Sort an array in wave form:
[pastacode lang=”java” manual=”%2F%2F%20Java%20implementation%20of%20naive%20method%20for%20sorting%0A%2F%2F%20an%20array%20in%20wave%20form.%0Aimport%20java.util.*%3B%0A%20%0Aclass%20SortWave%0A%7B%0A%20%20%20%20%2F%2F%20A%20utility%20method%20to%20swap%20two%20numbers.%0A%20%20%20%20void%20swap(int%20arr%5B%5D%2C%20int%20a%2C%20int%20b)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Ba%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Ba%5D%20%3D%20arr%5Bb%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Bb%5D%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20This%20function%20sorts%20arr%5B0..n-1%5D%20in%20wave%20form%2C%20i.e.%2C%0A%20%20%20%20%2F%2F%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D..%0A%20%20%20%20void%20sortInWave(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Sort%20the%20input%20array%0A%20%20%20%20%20%20%20%20Arrays.sort(arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20adjacent%20elements%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-1%3B%20i%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20swap(arr%2C%20i%2C%20i%2B1)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Test%20ob%20%3D%20new%20Test()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20ob.sortInWave(arr%2C%20n)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3A%20arr)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(i%20%2B%20%22%20%22)%3B%0A%20%20%20%20%7D%0A%7D” message=”java” highlight=”” provider=”manual”/]Output:
2 1 10 5 49 23 90
PYTHON
[pastacode lang=”python” manual=”%23%20Python%20function%20to%20sort%20the%20array%20arr%5B0..n-1%5D%20in%20wave%20form%2C%0A%23%20i.e.%2C%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D%20%3E%3D%20arr%5B5%5D%0Adef%20sortInWave(arr%2C%20n)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23sort%20the%20array%0A%20%20%20%20arr.sort()%0A%20%20%20%20%0A%20%20%20%20%23%20Swap%20adjacent%20elements%0A%20%20%20%20for%20i%20in%20range(0%2Cn-1%2C2)%3A%0A%20%20%20%20%20%20%20%20arr%5Bi%5D%2C%20arr%5Bi%2B1%5D%20%3D%20arr%5Bi%2B1%5D%2C%20arr%5Bi%5D%0A%20%0A%23%20Driver%20progrM%0Aarr%20%3D%20%5B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%5D%0AsortInWave(arr%2C%20len(arr))%0Afor%20i%20in%20range(0%2Clen(arr))%3A%0A%20%20%20%20print%20arr%5Bi%5D%2C” message=”python” highlight=”” provider=”manual”/]Output:
2 1 10 5 49 23 90
The time complexity of the above solution is O(nLogn) if a O(nLogn) sorting algorithm like Merge Sort, Heap Sort, .. etc is used.
[ad type=”banner”]