DEV Community

Discussion on: Daily Challenge #308 - Wave Sort

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
 
qm3ster profile image
Mihail Malo

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

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 ~