Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Best way to shift an array in C?

I have an array that holds a history of values, and when adding a new value, I need to shift all previous values one position to the left, to loose the oldest value and make room for the next.

I can think of two ways of doing this, by using memmove:

memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr));

Or by swapping the pointers:

for (i = 0; i != sizeof(arr) - 1; i++) {
   *(arr + i) = *(arr + i + 1);
}

Is there a performance difference between the two methods, and if not, which one would be advised?

like image 937
Maestro Avatar asked Sep 02 '13 14:09

Maestro


People also ask

Can we shift an array in C?

Logic To Shift Elements of An Array by n Position. First we ask the user to input N integer numbers and store it inside array variable a[N]. We then ask the user to input the number of positions to shift the elements of the array, and then the direction of shifting.

How do you shift an array to the right?

An array is said to be right rotated if all elements of the array are moved to its right by one position. One approach is to loop through the array by shifting each element of the array to its next position. The last element of the array will become the first element of the rotated array.

How do you shift elements in an array?

Create a temp variable and assign the value of the original position to it. Now, assign the value in the new position to original position. Finally, assign the value in the temp to the new position.

How do you shift an array to the left?

The array can be left rotated by shifting its elements to a position prior to them which can be accomplished by looping through the array and perform the operation arr[j] = arr[j+1]. The first element of the array will be added to the last of rotated array.


2 Answers

There is a faster option:

A circular buffer where insert, remove and read are all O(1).

like image 128
Klas Lindbäck Avatar answered Oct 07 '22 12:10

Klas Lindbäck


They both have the same time complexity. Any other difference in performance would be due to specific circumstances, such as the CPU, the compiler, how memmove is implemented, and the size of the array, so you have to actually measure the performance each way and see what is best.

like image 45
Vaughn Cato Avatar answered Oct 07 '22 11:10

Vaughn Cato