Adding a Problem that Sorts an Array in the Wave Form

[JuOllie]

Hey, I haven't come across this one among all the other algos that have been listed.Wanted to know if I could contribute to this one.

[faheel]

Can you tell me more about it? What the algorithm is for and how it works?

[JuOllie]

Yeah,sure.It's also called wiggle sort where a[0] <= a[1] >= a[2] <= a[3]>=a[4] and so on i.e. Alternating increasing and decreasing values. There's are two approaches based on the conditional:

1. Sorting the array in ascending order and then starting by arranging the lower elements in odd positions (LHS to RHS). While the higher numbers can be placed from the other direction(RHS to LHS),in the even places.The complexity depends on the type of sorting algorithm we choose to use. 2.This can be slightly modified to a better approach in case the condition is a[0] > a[1] < a[2] > a[3]<a[4],by :
   • Finding the median of the array
   • 3 way partition where elements less than ,equal to and greater than the median are split into 3 separate partitions.
   • Picking an element from each of the 3 partitions in the order central partition,left partition and right partition. This will ensure that the elements are strictly lesser or greater than their adjacent neighbours.

[faheel]

@JuOllie Yes sure, you can contribute to this. But since this isn't really a sorting algorithm but instead a rearranging algorithm, I'm not sure at the moment where to add it. So you can create a folder named 'Other' and add it there for now.

[JuOllie]

Sure @faheel ,I'll do that.

[JuOllie]

I have made a Pull Request at https://github.com/faheel/Algos/pull/56

[JuOllie]

The Modified pull request to the master branch is at #57

[faheel]

@JuOllie While reviewing your PR I realised that a much simpler solution can be made for this problem, with the same time and space complexities of O(N) and O(1) respectively. Here's my approach:

(Given a[0..N-1])

for i = 1 to N-1
    if i is odd
        if a[i] is not >= a[i - 1]
            swap(a[i], a[i - 1])
    else
        if a[i] is not <= a[i - 1]
            swap(a[i], a[i - 1])

Also since the operation for each condition is the same (to swap a[i] and a[i - 1]), the solution can be made more concise by grouping the 4 conditions into a single if condition, and by eliminating the not boolean operation by using complementary comparisons (< for not >= and > for not <=), as follows:

for i = 1 to N-1
    if i is odd and a[i] < a[i - 1], or i is even and a[i] > a[i - 1]
       swap(a[i], a[i - 1])

[stale[bot]]

This issue has been automatically marked as inactive because it has not had recent activity. It will be closed in 15 days if no further activity occurs. Thank you for your contributions.