March 4, 2016 9:00 AM
A list of integers is sorted in “wave” order if alternate items are greater than their immediate neighbors (thus the other alternate items are less than their immediate neighbors). Thus, the list [4 1 7 5 6 2 3] is in wave order because 4 > 1, then 1 < 7, then 7 > 5, then 5 < 6, then 6 > 2, and finally 2 < 3. Note that the two alternate streams [4 7 6 3] and [1 5 2] need not themselves be sorted. It doesn’t matter if the first item is the high wave or the low trough between waves, though starting with a wave is traditional.
Your task is to write a program that takes a list of unique integers and sorts it into wave order. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
What about sorting the given integers, and then swapping ith element with (n-i)th element. It will solve the repeated integer problem for most of the cases.
By Rajesh Kumar on March 5, 2016 at 7:19 AM
That’s what I was thinking – sort lowest to highest in a temporary array, then return the largest, then smallest, then second-largest, then second-smallest, etc – so the same result with more or less the same method.
The problem comes if the last few numbers to be processed (ie the middle numbers in the highest-to-lowest temporary array) contain duplicates…
…I haven’t thought of a bullet-proof algorithm yet.
By Brendan on March 8, 2016 at 6:12 AM
[…] have written a function to perform wave-sort as shown below. The resulting array should begin with a number bigger than the next one but my code […]
By Wave sort in Javascript - Tutorial Guruji on June 4, 2021 at 9:18 AM