CODEWITHSUNDEEP
carrays
Constantine1001
Constantine1001

Reputation: 81

How to circular shift array for n positions

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int main()
{
    int niz[MAX], i, pom; 


// two more var, n,m=0;

char c;

for(i=0;i<MAX;i++)
{
    niz[i]=rand()%100;
}
for(i=0;i<MAX;i++)
{
    printf("%d\n", niz[i]);
}


printf("\n\nEnter L(l) for left shift or R(r) for right shift\n");
scanf("%c", &c);

if(c=='L' || c=='l')
{

//while(m<n) and on the end n++; or for(m=0;m<n;m++)... you know what i mean 
//but its not working...


    pom=niz[0];
    for(i=0;i<MAX-1;i++)
    {
        niz[i]=niz[i+1];
    }
    niz[MAX-1]=pom;


    //for loop to shift array for 1 position
}

else if(c=='R' || c=='r')
{

//.....

    pom=niz[MAX-1];
    for(i=MAX-1;i>0;i--)
    {
        niz[i]=niz[i-1];
    }
    niz[0]=pom;
    //for loop to shift array for 1 position
}

for(i=0;i<MAX;i++)
{
    printf("%d\n", niz[i]);
}
return 0;
}

Ok this is code to shift array left or right for 1 position and it works fine. But if i want to shift array for n positons my first thought was ok just put code from IF and ELSE IF in one more loop which will repeat until some variable is increased to less than n, i tried puting code from IF and ELSE IF in while and for loop but its not working.. BTW is there some alternative to my way of shifting array for n positions... ?

Upvotes: 1

Views: 4818

Answers (2)

kuroi neko
kuroi neko

Reputation: 8661

If you're dealing with arrays, you will need to copy every single element at least once.

Let's call S the size of the array.

The most time-efficient method would be to split your array in two contiguous parts, copy the smallest one into a temporary storage (of a length of at most S/2), move the biggest chunk into place, and copy back the smallest chunk where it belongs.
This will require at most 3S/2 copies.

The most space-efficient would be to swap elements one by one, requiring only one element for temporary storage, but that would be slower (you would lose the benefit of block copies).

Upvotes: 1

Austin Mullins
Austin Mullins

Reputation: 7427

My basic idea was to copy the original array and then set the elements of the array based on a shifted index into the copy. After getting the value for n and the shift direction (and any error checking), this was my approach:

if(toupper(c)=='L')
{
    n = -n;
}

for(i=0;i<MAX;i++)
{
    copy[i] = niz[i];
}

for(i=0;i<MAX;i++)
{
    shift_i = (i+n+MAX) % MAX;
    niz[i]=copy[shift_i];
}

Since n could be negative, I add the length of the array to it before taking the modulo. An in-place shift would be more efficient, but I haven't figured that out yet. You would need to keep track of original values somehow.

Upvotes: 1

Related Questions