DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #308 - Wave Sort

#challenge

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)

Collapse
 
danielt404 profile image
DanielT404 • • Edited

I've come up with the following C# solution to this problem;
O(n) time complexity

public class Kata
{
  public static void swapElements(int i, int j, int[] inputArr) { 
    int temp = inputArr[i];
    inputArr[i] = inputArr[j];
    inputArr[j] = temp;
  }

  public static void WaveSort(int[] arr)
  {
    int anchor = 0; 
    int explorer = 1;
    bool isAnchorWaveSorted = false;

    Array.Sort(arr); 

    while(explorer < arr.Length) {
      if(!isAnchorWaveSorted) { 
        swapElements(anchor, explorer, arr);
      }
      isAnchorWaveSorted = !isAnchorWaveSorted;
      anchor++;
      explorer++;
    }
  }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
desirtechnologies profile image
Jeffrey Desir •

I'm not knee-deep in algorithm optimization having tasted the instant-gratifications of web development, but this resource was neat to me ~

Collapse
 
qm3ster profile image
Mihail Malo •

Sorting is O(n log n) - O(n²) depending on if you allocate additional space.

Collapse
 
willsmart profile image
willsmart •

A little one version in pretty damn cryptic but possibly speedy JS.

const waveSort = array => array
    .sort((a, b) => b - a)
    .map((_, i, arr) => arr[(i & 1) * ((arr.length + 1) >> 1) + (i >> 1)]);
Enter fullscreen mode Exit fullscreen mode

The call to sort sorts the array by descending value.

The call to map performs a one-to-one mapping of elements:

  • The (i & 1) * ((arr.length + 1) >> 1) alternates between the first half of the array and the second half
  • The 'i >> 1` adds an index that increments every second element

Because 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

Collapse
 
alfredosalzillo profile image
Alfredo Salzillo • 
const partion = (n) => (list) => Array(n).fill(0).map((_, i) => list.slice(i * (Math.ceil(list.length / n)), (i + 1) * Math.ceil(list.length / n)));
const merge = ([list1, list2]) => list1.flatMap((n, i) => [n, list2[i]]).filter(Boolean);
const waveSort = (list) => list.sort((a, b) => a - b)
   |> partion(2) 
   |> merge;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
peter279k profile image
peter279k •

Here is the simple solution in PHP:

function wave_sort(&$array) {
  sort($array);
  for ($index=0; $index<count($array)-1; $index+=2) {
    $tmp = $array[$index];
    $array[$index] = $array[$index+1];
    $array[$index+1] = $tmp;
  }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
qm3ster profile image
Mihail Malo • • Edited

Rust 

use itertools::Itertools;
fn wave(nums: &mut [u32]) -> impl Iterator<Item = u32> + '_ {
    nums.sort_unstable();
    let (small, big) = nums.split_at(nums.len() / 2);
    big.iter().interleave(small).copied()
}
Enter fullscreen mode Exit fullscreen mode

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.

fn main() {
    let mut cases: [&mut [u32]; 3] = [
        &mut [1, 2, 34, 4, 5, 5, 5, 65, 6, 65, 5454, 4],
        &mut [3, 2, 5, 1, 6],
        &mut [1, 2, 3],
    ];
    for nums in &mut cases {
        println!("{:?}", wave(nums).collect::<Vec<_>>());
    }
}
Enter fullscreen mode Exit fullscreen mode

Look at it go!

Read next

abhay_yt_52a8e72b213be229 profile image

Docker with Helm: Simplifying Kubernetes Deployment and Management

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Docker and Kubernetes Integration: The Ultimate Solution for Containerized Applications

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Docker Autoscaling: Dynamically Adjust Containers Based on Demand

Abhay Singh Kathayat -

nozibul_islam_113b1d5334f profile image

A Pleasant Work Environment = Better Productivity

Nozibul Islam -