C program to rearrange array such that elements at even positions are greater than odd

In this blog post, we learn how to write a C program to rearrange array such that elements at even positions are greater than odd? So here we will write a C program to rearrange array such that elements at even positions are greater than odd.

Suppose ‘arr’ is an integer array of size N and task to sort the array according to the following relations,

arr[i-1] < = arr[i], if position ‘i’ is odd. 

arr[i-1] > = arr[i], if position ‘i’ is even.

Example,

Input array: int arr[] = {1, 4, 5, 2, 7};


Output array: int arr[] = {1, 7, 2, 5, 4};


 

Logic to rearrange array such that elements at even positions are greater than odd

1. First we need to arrange the array in ascending order.

2. Create two intermediate variables to track the beginning and ending elements of the array.

3. Now assign the largest [ N/2 ] elements to the even positions and the rest of the elements to the odd positions of the temporary array of size N.

4. Now copy the temporary array to the original array.

Now let’s see the c program to rearrange array such that elements at even positions are greater than odd,

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


//call back function
int compare(const void * arr, const void * b)
{
    return ( *(int*)arr - *(int*)b );
}


//print array element
void printArray(int arr[], int n)
{
    int i;
    for ( i = 0; i < n; i++)
    {
        printf("%d ",arr[i]);
    }
}

void rearrangeEvenPositioned(int arr[], const int n)
{
    int tmp[n];
    int begin = 0, end = n - 1, i =0;
    
    //sort array elements using qsort inbuilt function
    qsort(arr,n, sizeof(int), compare);
    
    // Print input array
    printArray(arr,n);
    printf("\n\n");
    
    for (i = 0; i < n; i++)
    {
        // Assign even indexes with maximum elements
        if ((i+1)  % 2 == 0)
        {
            tmp[i] = arr[end--];
        }// Assign odd indexes with remaining elements
        else
        {
            tmp[i] = arr[begin++];
        }
    }
    
    //copy temp array element in
    //original array
    memcpy(arr,tmp,n*sizeof(int));
}


int main()
{
    int arr[] = {1, 3, 2, 2, 5, 7, 4};
    
    //get array size
    int arr_size = ARRAY_SIZE(arr);
    
    //rearrange elements
    rearrangeEvenPositioned(arr, arr_size);
    
    //print array
    printArray(arr,arr_size);
    
    return 0;
}
C program to rearrange array such that elements at even positions are greater than odd

There is another simple approach to rearrange the array. In which we need to traverse the array from the second element and swap the element with the previous one if the condition is not satisfied.

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


// swap two elements
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void rearrangeEvenPositioned(int arr[], int n)
{
    int i =0;

    for (i = 1; i < n; i++)
    {
        // if index is even
        if (i % 2 == 0)
        {
            if (arr[i] > arr[i - 1])
            {
                swap(&arr[i - 1], &arr[i]);
            }
        }
        // if index is odd
        else
        {
            if (arr[i] < arr[i - 1])
            {
                swap(&arr[i - 1], &arr[i]);
            }
        }
    }
}


//print array element
void printArray(int arr[], int n)
{
    int i;
    for ( i = 0; i < n; i++)
    {
        printf("%d ",arr[i]);
    }
}


int main()
{
    int arr[] = {1, 3, 2, 2, 5, 7, 4};

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    rearrangeEvenPositioned(arr, arr_size);

    //print array
    printArray(arr,arr_size);

    return 0;
}

C program to rearrange array such that elements at even positions are greater than odd