Wave Array

A wave array is an array of numbers where the elements form a wave-like pattern when sorted in a particular way. In a wave array, the elements have a specific order that alternates between being smaller or equal to their adjacent elements and being larger or equal to their adjacent elements. This pattern creates a wave-like shape when you visualize the array.

Here’s an example to illustrate a wave array:

Input Array: [3, 1, 4, 6, 2, 5]

When you sort this array in ascending order, you get:

Sorted Array: [1, 2, 3, 4, 5, 6]

Now, if you look at the sorted array, you can see the wave-like pattern:

1. The first element (1) is smaller than or equal to the second element (2).
2. The second element (2) is larger than or equal to the third element (3).
3. The third element (3) is smaller than or equal to the fourth element (4).
4. The fourth element (4) is larger than or equal to the fifth element (5).
5. The fifth element (5) is smaller than or equal to the sixth element (6).

This alternating pattern of smaller-or-equal and larger-or-equal continues throughout the sorted array, creating the wave-like shape:

1 ≤ 2 ≥ 3 ≤ 4 ≥ 5 ≤ 6

So, the sorted array [1, 2, 3, 4, 5, 6] is a wave array because it follows this wave-like pattern. Wave arrays can have various applications in algorithms and can be used to simplify certain problems by exploiting this pattern in the data.

Example :

fun main() {
    waveArray(intArrayOf(1,2,3,4,5,6))
}

fun waveArray(array:IntArray){
    for (i in 0 until array.size-1 step 2){
        var temp = array[i]
         array[i] = array[i+1]
        array[i+1] = temp   
        
        
    }
    println(array.toList())
}

Time complexity :

The time complexity for creating a wave array is determined by two main operations:

1. Sorting the input array: The time complexity of sorting depends on the sorting algorithm used. Common sorting algorithms like Quick Sort, Merge Sort, or Heap Sort have average-case time complexities of O(n log n), where “n” is the size of the input array.
2. Swapping adjacent elements: After sorting the array, you need to swap adjacent elements to create the wave pattern. This operation typically takes linear time since you need to visit each element of the array once. Therefore, it has a time complexity of O(n).

Combining these two operations, the overall time complexity for creating a wave array is dominated by the sorting step, which is O(n log n) in the worst case if a comparison-based sorting algorithm is used. If you use a more specialized sorting algorithm tailored to this specific task, you might achieve a better time complexity, but in general, it’s O(n log n) due to the sorting step.

Thanks for reading, HAPPY CODING !!