Wednesday, 15 March 2017

C Program to convert an Array into a Wave Array

There are two methods to convert an array into a wave array.

Method 1. Sorting:- First sort the array in ascending order by using sorting algorithms like quicksort, heapsort, mergesort, and then swap all the even positioned elements with the previous odd positioned elements.
For example:   a[]={12, 34, 56, 45, 54, 32}
                      After sorting: a[]= { 12, 32, 34, 45, 54, 56 }
                      After swapping all adjacent elements = { 32, 12, 45, 34, 56, 54}

Method 2. Another efficient solution can give you desired array in Linear time, because it doesn’t involve sorting the array or use of auxiliary space. We start from the second element of the array and increment index by 2 for each iteration of loop. If previous element is greater than the current element, we swap the elements. Similarly if next element is greater than the current element, we swap both elements. At the end of loop, we will get the desired array that satisfies given constraints.

 Time complexity of method 2 is 0(n). 

Algorithm for second method is given below:


set: i=1  /*considering index 0 */

If you want pattern A[0]<=A[1]>=A[2]<=A[3]>=A[4]

for i=1 to n-1:
      If arr[i]<arr[i-1]:  
            swap: arr[i] and arr[i-1]
      If arr[i]<arr[i+1]:
            swap: arr[i] and arr[i+1]
End for loop

If you want patter A[0]>=A[1]<=A[2]>=A[3]<=A[4]

for i=1 to n-1:
      If arr[i]<arr[i-1]:  
            swap: arr[i] and arr[i-1]
      If arr[i]<arr[i+1]:
            swap: arr[i] and arr[i+1]
End for loop


Implementation of Method 2 to convert an Array into a Wave Array is:

#include <stdio.h>
void wave_array(int n);
int arr[100];
int main()
{
    int n,i,j;
    printf("\nEnter the total number of elements of the array: ");
    scanf("%d",&n);
    printf("\nEnter the elements of the array:\n");
    for(i=0;i<n;i++)
    {
          scanf("%d",&arr[i]);
    }
    printf("\nThe original array is: \n");
    for(i=0;i<n;i++)
    {
          printf("%d ",arr[i]);
    }
    wave_array(n);
    printf("\nThe formed wave array is: \n");
    for(i=0;i<n;i++)
    {
          printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}
void wave_array(int n)
{
    int i;
    int temp;
    for(i=1;i<n;i=i+2)
    {
             if(arr[i]<arr[i-1])
             {
                 temp=arr[i];
                 arr[i]=arr[i-1];
                 arr[i-1]=temp;
             }
             if(arr[i]<arr[i+1])
             {
                 temp=arr[i];
                 arr[i]=arr[i+1];
                 arr[i+1]=temp;
             }


    }
}


OUTPUT:

 


EmoticonEmoticon