A list of integers is sorted in “Wave” order if alternate items are not less than their immediate neighbors.
Therefore, the array [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.
The wave-sorted lists has to begin with an element not less than the next, so [1, 4, 5, 3] is not sorted in wave because 1 < 4
Your task is to implement a function that takes a list of integers and sorts it into wave order.
Tests
[1, 2, 34, 4, 5, 5, 5, 65, 6, 65, 5454, 4]
[3,2,5,1,6]
[1, 2, 3]
Good luck!
This challenge comes from kodejuice on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (7)
I've come up with the following C# solution to this problem;
O(n) time complexity
I'm not knee-deep in algorithm optimization having tasted the instant-gratifications of web development, but this resource was neat to me ~
Sorting is O(n log n) - O(n²) depending on if you allocate additional space.
A little one version in pretty damn cryptic but possibly speedy JS.
The call to
sort
sorts the array by descending value.The call to
map
performs a one-to-one mapping of elements:(i & 1) * ((arr.length + 1) >> 1)
alternates between the first half of the array and the second halfBecause the elements in the first half are all greater than or equal to the elements in the first half, it's a wave sort.
Tested in the kata
Here is the simple solution in
PHP
:Rust
Mutates your slice to sort. Don't want it sorted? Clone it yourself!
Doesn't actually verify if successful, since by
<=
>=
rules this can never fail. This enables us to return an iterator with confidence instead of having to collect.And integer division means that with odd length input the right "half" (greater numbers) will be longer, so we can start with greater numbers as per rules.
Look at it go!