Wave Sorting

March 4, 2016

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.

Pages: 1 2