Sort the array based on position without extra space
Question:
Write a program to sort the array based on position. Sort odd position elements in descending order and even position elements in ascending order. Must not use any extra array.
Logic
- The logic is very simple, sort the odd position elements separately and even position elements separately.
- Use insertion sorting method to sort the odd position numbers.
- After that sort the even position numbers.
- Finally, print the array.
Program
[code lang=”c”]
#include<stdio.h>
void swap(int* ,int*);
void main()
{
int ar[20];
int n,i,k,j,m,temp;
printf("enter limit");
scanf("%d",&n);
for( i =0;i<n;i++)
{
scanf("%d",&ar[i]);
}
// insertion sort for odd position
for(i=0;i<=n-3; i=temp+2)
{
temp=i; // store the index so not affected in next iteration
while(i>=0)
{
if(ar[i]<ar[i+2]) // if ar[i] is small
{
swap(&ar[i],&ar[i+2]);
i=i-2; //decrement to check previous odd position,ar[i] and ar[i-2] in next iteration
}
else
break; // end loop when sorting finised
}
}
for(j=1;j<=n-3;j=temp+2) // insertion sort for even position
{
temp=j;
while(j>=1)
{
if(ar[j]>ar[j+2]) //if ar[i] is large
{ swap(&ar[j],&ar[j+2]);
j=j-2;
}
else
break;
}
}
for( k=0;k<n;k++)
printf("%d ",ar[k]); //sorted array
}
void swap(int *a,int *b) //call by reference swap
{
int temp ;
temp = *a;
*a = *b;
*b = temp;
}
[/code]
