Left Shift/ Right Shift an array in C

Question

I am trying to implement a Left shift/ Right Shift on arrays.

I was able to accomplish this using double loops. Can the efficiency be improved?

This is the working code for LeftShift/RightShift which is using 2 nested loops.

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

struct Array
{
    int A[10];
    int size;
    int length;
};

void Display(struct Array arr)
{
    printf("\nElements are : \n");
    for(int i = 0;i<arr.length;i++)
        printf("%d ", arr.A[i]);
}

// Left Shift-------------------------------------------------------------------------------
void LeftShift1(struct Array *arr, int n)    //n is the number of shifts
{
    for(int i=0; i<n; i++)
    {
        //int temp = arr->A[0];
        for(int j=0; j<arr->length-1; j++)
        {
            arr->A[j] = arr->A[j+1];
        }
        arr->A[arr->length-1] = 0;
    }
}

//Right Shift-------------------------------------------------------------------------------
void RightShift(struct Array *arr, int n)    //n is the number of shifts
{
    for(int i = 0; i<n; i++)
    {
        for(int j=arr->length-1; j>0; j--)
        {
            arr->A[j] = arr->A[j-1];
        }
        arr->A[0] = 0;
    }
    
}

int main()
{
    struct Array arr={{1,2,3,4,5},10,5};
    
    LeftShift1(&arr, 2);
    //RightShift(&arr, 1);

    Display(arr);

    return 0;
}    

I'm trying something like this which uses 2 iterators to solve this problem!

This is also working!

void LeftShift2(struct Array *arr, int n)
{
    if (n > arr->length) {
            n = arr->length;
    }
    for(int k=0; k<n; k++)
    {
        int i,j;
        for(i=0, j=0; j<arr->length-1; i++, j++)
        {
            arr->A[j] = arr->A[j+1];
        }
        arr->A[arr->length-1] = 0;
    }
}

But can this be solved without loops? OR with a single loop?

Can this be made more efficient?

Answer 1

Why do you have the following line if you are not using temp?

int temp = arr->A[0];

You do not need the nested loops. You are currently shifting the elements one position at a time when you can move them n positions.

void LeftShift1(struct Array* arr, unsigned int n) {
    for (unsigned int i = 0; i < arr->length; i++) {
        if (i + n < arr->length)
            arr->A[i] = arr->A[i + n];
        else
            arr->A[i] = 0;
    }
}

Or use memmove / memset as suggested by @Carlo

Answer 2

You know, C and C++ are different languages. You used both tags, and your code is confused as to which it wants to be. It appears to use C syntax, library calls, and ways of doing things; but it includes a C++ header. It doesn't seem to use that header though. Maybe this is the current state of the file after you have done some experimentation and different versions?

Generally, you want to consider doing this array shifting with element types other than a plain int. In fact, it may be a complex type like a string and you should not be doing raw memcpy stuff on it as some suggested. In your code, you're setting the shifted-out elements to 0 which is OK for an integer and related types, but won't work in general (say, string).

Note that there exists std::rotate which doesn't stick zeros on the shifted-from end but copies the shifted-off elements there instead.

As of C++20, there is a standard std::shift_left and shift_right ready to use.

int arr[] = {1,2,3,4,5};
using std::ranges::begin;
using std::ranges::end;
std::shift_left (begin(arr),end(arr),2);
Display(arr);

I'm not sure what your struct Arr is all about; if it's an array with a maximum and current size, you are not making use of that. In C++, just use vector. But with a real flexible container, do you really want to "shift", putting 0/empty/blank element on the other end, or did you really want to just delete elements from one end? The whole point of flexible containers is you don't have placeholders ready to be assigned to, but only store those elements actually present. So maybe instead of shift_right you really want to vector::erase n elements starting at the beginning, and shift_left is just a resize to make smaller.

If you are doing a lot of adding and removing elements from both ends then there is a container specifically designed for that called deque. Its name means "double ended queue" but it's pronounced like "deck".

summary

• what do you really want to do?
• know what's in the library.

Answer 3

You can use memmove() function to move overlapping areas of memory and memset() to clear the moved items.

LeftShift can be implemented like:

#include <string.h>

void LeftShift(struct Array *arr, int n)    //n is the number of shifts
{
    memmove(&arr->A[0], &arr->A[n], (arr->size-n)*sizeof(arr->A[0]));
    memset(&arr->A[arr->size-n], 0, n * sizeof(arr->A[0]));
}

Answer 4

The code doesn't check if n is within the expected boundaries of the array. Unintentional overwriting of memory is such an infamous concern in C/C++, even in toy code I would add the range check to build good habits, or at the very least document in a comment that the caller is assumed to be trusted.

Answer 5

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

If this is C, don't attempt to include <iostream>. If it's C++, use the C++ headers (<cstdlib> etc), and prefer <iostream> to <stdio.h>. There's almost never any need for an implementation file to be bilingual C and C++ (sometimes it's useful for a header).

---

struct Array
{
    int A[10];
    int size;
    int length;
};

This is a strange way to define an array. Does it ever make sense for size to have a different value to int(sizeof A)? Why are we using a signed integer anyway?

In C, we'd normally use a flexible array member for the elements:

struct Array
{
    size_t capacity;
    size_t length;
    int elements[];
};

In C++, a std::vector<int> provides exactly this functionality.

Answer 6

The fastest way is to use memmove() and memset(), because as library routines they should be optimal. But if you can't do that for whatever reason, your best speed-up is from moving to using pointers. Looping over arrays with indexing is never optimal speed-wise (although it has obvious advantages for code readability). And since you're shifting by a known number of steps, you can build that in too.

/** Right-shift array data in place, one element at a time.
@param arr Array data structure
@param n Number of shifts
@note n should be less than length of array.
*/
void RightShift(struct Array *arr, int n)    /* n is the number of shifts */
{
    int* fromPtr;
    int* toPtr;
    int* endPtr;
    
    if (n == 0)
    {
        /* No shift required */
        return;
    }
    
    /* Limit shift */
    if (n > arr->length)
    {
        n = arr->length;
    }
    
    /* Shift data up, starting at the end and working 
    backwards so that we don't overwrite data to shift.
    Note that the end is one element *before* the start,
    because we're working backwards.
    */
    toPtr = arr->A + (arr->length - 1);
    fromPtr = toPtr - n;
    endPtr = arr->A - 1;
    while (fromPtr != endPtr)
    {
        *toPtr = *fromPtr;
        toPtr --;
        fromPtr --;
    }
    
    /* Clear remaining data */
    fromPtr = arr->A + (n - 1);
    while (fromPtr != endPtr)
    {
        *fromPtr = 0;
        fromPtr --;
    }   
}

This should handle your right-shift. (Note that I have only written this, not run it. :)