6
\$\begingroup\$

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?

\$\endgroup\$
7
  • 5
    \$\begingroup\$ This looks like a use-case for std::rotate: en.cppreference.com/w/cpp/algorithm/rotate \$\endgroup\$
    – user673679
    Oct 18 at 19:18
  • \$\begingroup\$ @user673679 I will try to implement it. I was trying not to use inbuilt functions for now, but this helped me! Thank you! \$\endgroup\$
    – Vishnu
    Oct 18 at 20:01
  • 1
    \$\begingroup\$ Is this a C or a C++ question? \$\endgroup\$
    – G. Sliepen
    Oct 18 at 20:02
  • 2
    \$\begingroup\$ <iostream> is a C++ header, so obviously not C. \$\endgroup\$ Oct 19 at 6:46
  • 1
    \$\begingroup\$ "...which uses 2 iterators..." The word to use here is "index". When you start working with C++, "iterator" has a very specific meaning. \$\endgroup\$
    – Graham
    Oct 19 at 9:36
8
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ That line was copied from the array rotation part. My bad! \$\endgroup\$
    – Vishnu
    Oct 18 at 20:12
  • 1
    \$\begingroup\$ Doing it with a single loop like this is possible, but for efficiency you need the compiler to unswitch the loop, aka make two loops. Writing it in the source with two loops is about neutral in terms of complexity for future readers of the code. And if performance is relevant at all, it won't make them worry about whether the compiler (or which compilers) can optimize it easily into memmove and memset like they will with separate loops. \$\endgroup\$ Oct 19 at 4:48
  • 2
    \$\begingroup\$ @PeterCordes, you are correct, as always =). I had some fun playing around with this \$\endgroup\$
    – jdt
    Oct 22 at 17:17
9
\$\begingroup\$

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]));
}
\$\endgroup\$
0
9
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$
#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.

\$\endgroup\$
3
  • \$\begingroup\$ I was using size for testing dynamic array earlier. size was being used for allocating the size of the array in heap using something like this : arr.A=(int *)malloc(arr.size*sizeof(int));. On the other hand, can we not intermix legal C code with C++ code? C++ is backward compatible with C right? \$\endgroup\$
    – Vishnu
    Oct 19 at 7:46
  • \$\begingroup\$ No, you can't change an array to a pointer like that; you would need int *A rather than int A[]. (And there's no need to cast the result of malloc() in C). Yes, you could write C++ that's also valid C - but why would you want to do that? \$\endgroup\$ Oct 19 at 8:43
  • \$\begingroup\$ Yes, it was int *A before! Thanks for this insight, it helped a lot! \$\endgroup\$
    – Vishnu
    Oct 19 at 9:02
0
\$\begingroup\$

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. :)

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I like your idea of using pointers but there are two errors: ` toPtr = arr->A + (&arr->length - 1);` should be ` toPtr = arr->A + (arr->length - 1);` and there is a ; dangling after the while statement that results in an infinite loop. \$\endgroup\$
    – jdt
    Oct 19 at 12:10
  • 2
    \$\begingroup\$ Most modern compilers should also be able to optimize basic loops into memmove / memcpy. I am not the expert on this but I think your approach may confuse the compiler and cause more harm than good =) \$\endgroup\$
    – jdt
    Oct 19 at 12:13
  • \$\begingroup\$ @upkajdt The perils of writing code without having time to compile and run it! Thanks! :) I agree that memmove/memcpy would be better, but I'm not aware that modern compilers are smart enough to turn regular array indexing into something better, because that's about guessing the coder's intent rather than what they've written. Either way, pointers are going to be faster than array operations though AFAIK. Although perhaps I'm not up on the latest optimisation techniques. \$\endgroup\$
    – Graham
    Oct 20 at 10:31
  • \$\begingroup\$ Cool, as I said, I'm not the expert, but I decided to do some benchmarking see here and you may find the results interesting. I would also like to know what sort of times you get if you have access to gcc and a linux box. \$\endgroup\$
    – jdt
    Oct 20 at 11:22
  • \$\begingroup\$ Interestingly if you look at the following, testA and testB have about the same results with MSVC and Intel compiler, but the inline incrementation seems to confuse gcc. \$\endgroup\$
    – jdt
    Oct 20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.