Left Shift/ Right Shift an array using two pointers in C-CodePudding

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

I was able to accomplish this using double loops. Can I get some help to improve the efficiency?

This is the working code for LeftShift/RightShift which is using 2 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
{
    int temp = arr->A[0];
    for(int i=0; i<n; i  )
    {
        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)
{
    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?

CodePudding user response：

some help to improve the efficiency?

Shift: Shift once. Go from O(n*length) to O(length).

Rotate: Shift once into a temporary. Go from O(n*length) to O(length).

Qualify n first.

void LeftShift_alt(struct Array *arr, int n) {
    if (n > arr->length) {
        n = arr->length;
    }
    memmove(&arr->A[0], &arr->A[n], (arr->length - n)*sizeof arr->A[0]);
    memset(&arr->A[arr->length - n], 0, n * sizeof arr->A[0]);
}

void LeftRotate_alt(struct Array *arr, int n) {
  if (arr->length > 0) {
    n %= arr->length;
    if (n > 0) {
      int temp[n];
      memcpy(temp, arr->A, sizeof temp);
      memmove(arr->A, arr->A   n, sizeof arr->A[0] * (arr->length - n));
      memcpy(arr->A   n, temp, sizeof temp);
    }
  }
}

Replace mem...() with pointer code if desired.

CodePudding user response：

Rather than actually moving the contents of the array around, you could provide all the common accessor operators (<<, >>, [], etc.) in the struct. (Assuming you're using a compiler that supports this. Otherwise, you'll need to create these functions C-style.) If someone did this:

my_array <<= 5;
my_array >>= 2;

...you'd simply keep track of how much the array has been shifted. In this case, they've shifted a total of 3 positions to the left. When someone indexes into the array, you add the accumulated offset to their index (modulo the size of the array) to get the actual location of the entry they're looking for. This makes shifts O(1) instead of O(n). If you're looking for an efficient solution, this is about as good as it gets.