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

2 Responses to “Wave Sorting”

  1. 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.

  2. Brendan said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: