Wave Sorting

March 4, 2016

We give three solutions. Our first solution is “sort-and-twiddle;” first sort the integers, then swap adjacent items. Thus, the input [8 7 3 10 0 4 13 9 11 2] is sorted as [0 2 3 4 7 8 9 10 11 13], then the 0/2, 3/4, 7/8, 9/10 and 11/13 pairs are swapped, giving [2 0 4 3 8 7 10 9 13 11]:

(define (wave-sort-and-twiddle xs)
(let loop ((xs (sort < xs)) (zs (list)))
(cond ((null? xs) (reverse zs))
((null? (cdr xs)) (reverse (cons (car xs) zs)))
(else (loop (cddr xs) (cons (car xs) (cons (cadr xs) zs)))))))
> (wave-sort-and-twiddle '(8 7 3 10 0 4 13 9 11 2))
(2 0 4 3 8 7 10 9 13 11)

Because of the sort, that algorithm requires time O(n log n). A second solution first finds the median, which can be done in O(n) time, then partitions the input around the median, and finally takes from the two halves alternately, starting with whichever half is larger. We’re not going to implement that algorithm, because it gets messy and because there is a better O(n) algorithm.

A third solution is similar to a single pass of bubble sort: run through the input from left to right, considering each adjacent pair of integers, swapping those that are out of order. For instance, starting with [3 2 0 1], the first comparison is 3 > 2, which is correct, so the list is unchanged; the second comparison is 2 < 0, which is incorrect, so those two integers are swapped and the list becomes [3 0 2 1]; and the third comparison is 2 > 1, which is correct, so the list is unchanged and the algorithm is complete:

(define (wave-bubble xs)
(let loop ((xs xs) (dir 1) (zs (list)))
(cond ((null? xs) (reverse zs))
((null? (cdr xs))
(reverse (cons (car xs) zs)))
((positive? (* dir (- (car xs) (cadr xs))))
(loop (cdr xs) (- dir)
(cons (car xs) zs)))
(else (loop (cons (car xs) (cddr xs))
(- dir) (cons (cadr xs) zs))))))
> (wave-bubble '(8 7 3 10 0 4 13 9 11 2))
(8 3 10 0 7 4 13 9 11 2)

You can run the program at http://ideone.com/j878OP.

Things get harder if you relax the rule that all the integers are distinct. Actually, there may not be a solution; consider the case where all the integers are the same. I haven’t found an algorithm that works in all cases. For instance, the input [1 2 3 3 3 4 5] with valid wave sorts [3 1 4 3 5 2 3] or [4 1 3 5 3 2 3] or [3 1 3 2 4 3 5] becomes [2 1 3 3 4 3 5] with the sort-and-twiddle algorithm, but that fails because of the two adjacent 3s, the partition-around-median might either fail or succeed, depending on how items are chosen from the two partitions, and the bubble algorithm fails if there are more than two duplicates adjacent to each other in the original input, because it only considers adjacent pairs. Of course, if you additionally relax the rule of strict less-than or greater-than and allow equality, then everything is once again simple. If you are determined to find a solution that works with duplicate integers, use [0 1 2 3 3 3 3 3 8 9] as your test case, with one solution [3 0 3 1 3 2 8 3 9 3]; it gave me fits.

Pages: 1 2

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

3. […] 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 […]