C Programming - Rev()

An array of size N has distinct values 1…N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted

a. For size 3 only 1,3,2 requires 3 moves.

This is what I could think off. Do post in your comments!
Solution:


#include < stdio.h >

int elements[] = {1,23,8,3,4,7,8,9,2,1};
int count = sizeof(elements) /sizeof(int);
void rev(int pos)
{
     int iter,swaptemp;
     for(iter=0; iter < pos/2; iter++) {
                 swaptemp = elements[iter];
                 elements[iter] = elements[pos - iter - 1];
                 elements[pos - iter - 1] = swaptemp;
     }
}

int main()
{
    int iter,max=0,pos=0,loop=0;
    for(iter=0; iter < count; iter++) printf("%d ",elements[iter]); printf("\n");
    
    for(loop=count; loop > 0; loop=pos-1) {
       pos=max=0;
       for(iter=0;iter < loop;iter++) {
             if ( elements[iter] > max ) {
                  max = elements[iter];
                  if ( iter > 0 ) {
                       rev(iter);
                       if ( elements[iter+1] < elements[iter] ) {
                            printf("Swapping %d\n",elements[iter+1]);
                            rev(iter+1);
                       }
                       else 
                           continue;
                 }
            }
            pos++;
      }
      rev(pos);
    }
    
    for(iter=0;iter < count;iter++) printf("%d ",elements[iter]); printf("\n");
}

Labels:

About this entry

You’re currently reading “C Programming - Rev(),” an entry on ANOOB BACKER Technical Blog

Published:
10:32 pm
by -