Rearrange the array in such a way that the first element is first maximum and second element is first minimum?

Question

Given an array of integers, rearrange the array in such a way that the first element is first maximum and second element is first minimum.

Answer 1

here is the code in which array is rearranged according to the condition in complexity of O(n),without using any sorting technique

#include <stdio.h>
void swap(int *x,int *y)
{
    int temp;
    temp=*x;
    *x=*y;
    *y=temp;
}

int main(void) {
 int i,minIndex,maxIndex,n;
 int max=-32768; //negative limit for integer value
 int min=32767; //positive limit for integer value
 int array[10001];
 scanf("%d",&n);
 for(i=0;i<n;i++)
  scanf("%d",&array[i]);
//logic starts here and will extract max as maximum and min as minimum value and record their indexes
  for(i=0;i<n;i++)
   {
       if(max<array[i])
        {
          max=array[i];
          maxIndex=i;
        }
       if(min>array[i])
        {
          min=array[i];
          minIndex=i;
        }
   }
           swap(&array[0],&array[maxIndex]);  //place maximum value at first position
           swap(&array[1],&array[minIndex]);  //place minimum value at second position
           for(i=0;i<n;i++)
             printf("%d ",array[i]);
    return 0;
}

Comments

here space complexity is also very less ... better solution shashi

---

thanks..shivam

Answer 2

Here is the function to define another array from given array according to the problem:

void FirstMaxFirstMinSequence(int *arrayGiven , int n )
{
  int resultArray[10000],value=0;
  qsort(arrayGiven,n);   //quick sort which sort the array in O(nlog n)

  for(i=0;i<n/2;i++){
    resultArray[value++]=arrayGiven[i];  // insert max from first position

    if(value<n)
      resultArray[value++]=arrayGiven[n-i-1]; //insert min from last position
  }

  for(i=0;i<n;i++)
  {
    printf("%d",resultArray[i]);
  }
}