How to shift elements of an array?

Hi,

I have an 1D array with depth values (say from 0 to 5cm). The user will input an amount to shift the depth (say shift=2cm). How would I then use the value to produce a second array that has the depth from 1 to 3cm and then have zeros in the elements after 3cm so that the new array is the same size as he original?

Such as:
a[0]: 0
a[1]: 1
a[2]: 2
a[3]: 3
a[4]: 4
a[5]: 5

becomes:
a[0]: 2
a[1]: 3
a[2]: 4
a[3]: 5
a[4]: 0
a[5]: 0

Thanks for your help!

Use a for loop and assignment... Try it yourself first. Just iterate over the index of the array and assign the proper value.

Use a loop. (show some code for further help).

EDIT: Bummer, dup post and I was last.

Better would be to use a stack. They seem to be a common subject these days so look around the C forum for implementation details.

Originally Posted by whiteflags

Better would be to use a stack. They seem to be a common subject these days so look around the C forum for implementation details.

Given an array of, say 4096. You think it would be better to use a stack? How would you go about this? Are you speaking of recursion?

Originally Posted by Kennedy

Given an array of, say 4096. You think it would be better to use a stack? How would you go about this? Are you speaking of recursion?

A stack might be defined like this:

Code:

struct stack {
      int *array,  
           size,
           first_element;  
};

Then you have push and pop functions to operate on this. Notice you can shift the first element without moving the array at all and use size-first_element to determine when to wrap around.

More detailed explanation here:

Stack - Array Implementation

I don't see how a stack could be used to shift the individual elements. But I suppose the illusion of a shift could be done by doing something similar as above, then have a function returning a pointer to the "new" base of the array.

Originally Posted by Subsonics

I don't see how a stack could be used to shift the individual elements.

In the OP's original post the whole thing is being shifted, there are no insertions or deletions. You pop two elements off the top ( 0 and 1) then add two zeros to the end.

I guess that is a loose use for the term "pop" -- this is actually a double ended queue, but big dif. It's certainly much more efficient that reassigning every element to a new position.

Yes, but if the original array is {0, 1, 2, 3, 4} then doing two pop operations would give {0, 1, 2} not
{2, 3, 4, 0, 0}.

Why the #(-|| would you use a stack for this? That's called an anti-pattern. And a queue isn't a good idea either...
Just use an array and a for loop.

With a stack, we lose the possibly important feature of random access, or we use an O(n) operation for shifting.
Granted, a queue MAY be better suited for what this guy wants, but with the information he has given us, there is no reason to assume this is the case.

Originally Posted by Subsonics

Yes, but if the original array is (0, 1, 2, 3, 4) then doing two pop operations would give (0, 1, 2) not
(2, 3, 4, 0, 0).

That's why I said it's a loose use of "pop" and really this is double ended queue. Which the term I'm used to there (meaning: pop from top) is "shift". If you shift two off (0, 1, 2, 3, 4) you have (2, 3, 4). Now push two zero's.

What that really means is you would move first_element forward two (from [0] to [2]) then replace [0] and [1] with zeros. The queue still has a size of 5, so it wraps around and the "last element" is now first_element-1, ie [1].

I'm not gonna write the whole thing out, I think anyone with a brain can figure on the details

Originally Posted by EVOEx

With a stack, we lose the possibly important feature of random access, or we use an O(n) operation for shifting.
Granted, a queue MAY be better suited for what this guy wants, but with the information he has given us, there is no reason to assume this is the case.

Who's implementation are we on about?* Nb, my shift as descibed is a whole lot better than O(n). The underlying structure is still an array, not a linked list, so random access just requires quick arithmetic on first_element.

* nb, I cannot make promises about the link I posted, I have not used it personally or looked at it thoroughly but the idea is there (you define the stack as a struct containing an array and implement push/pop functions, plus in this case I guess a shift and remove or something).

But, to nitpick, then it's not a stack. My comment was aimed at the use of a stack nothing else. Moving pointers about, and giving the illusion of a true shift is a solution that should work as well, which I mentioned earlier as well.

BTW if the range and size of values in the first post is representative of what is needed in the real program a true bit shift could be done on the whole array as well (given that it's < 9 in size and contains only chars).

Originally Posted by Subsonics

But, to nitpick, then it's not a stack.

Nitpick eh...I would define a stack based on it's external functionality. You have to fulfill some qualifications, like push & pop functions that work FILO. How that's accomplished doesn't matter. If you can pop and push FILO style it will be identical for the user to a stack, hence it's a stack.

Whether or not the bottom/top corresponds absolutely to the first and last index of an array is irrelevant as long as you black box the interface (eg, use function calls -- get/set(stack_pointer, 3) -- instead of subscripting).

Originally Posted by MK27

Nitpick eh...I would define a stack based on it's external functionality. You have to fulfill some qualifications, like push & pop functions that work FILO. How that's accomplished doesn't matter. If you can pop and push FILO style it will be identical for the user to a stack, hence it's a stack.

Yeah, exactly. That is what I am doing. You put things on the stack and take them out according to the LIFO principle. That's it. There is only one entry point, you can't change the base of a stack with your push and pop operations.

Originally Posted by MK27

Whether or not the bottom/top corresponds absolutely to the first and last index of an array is irrelevant as long as you black box the interface (eg, use function calls -- get/set(stack_pointer, 3) -- instead of subscripting).

Yeah, well if it's irrelevant that means that the use of LIFO is also irrelevant, which of course it isn't. You can only do operations on the last element added to the stack, hence it's using a Last In First Out principle. Agreed?

MK27 is perfectly right. It's a stack if it's exposed functionality supports the operations of a stack.
You can only say something is not a stack if it doesn't support the necessary operations.
Some would go so far as to say perhaps being bounded by certain time constraints as well. e.g. amortised O(1) time pop. Using a circular buffer as the underlying container still fits that as well.