# Thread: Circular rotation pf string array

1. ## Circular rotation pf string array

Hi!

I'm trying to write a function ('rotate') that rotates the first n elements of my string array arr by shift positions in the clockwise direction if shift is positiv (anti-clockwise if negativ shift).

For example:
For arr = "hello",
shift = 2,
n = 4,
I'd like to obtain "llheo".

My code:
Code:
```
void rotate(char *arr, int shift, int n) {
if (shift >= 0){
for (int j=0; j<= shift; j++){
char tempfirst = arr[n-1];
for (int i=n-1; i>0; i--){
arr[i]=arr[i-1];
arr[0]=tempfirst;
}
}
}
else {
shift = -shift;
for (int j=0; j<= shift; j++){
char templast = arr[0];
for (int i=0; i<(n-1); i++){
arr[i]=arr[i+1];
arr[n-1]=templast;
}
}
}
return;
}
​```
Although there are no syntax errors, my code doesn't work.

2. > arr[0]=tempfirst;
These things should be outside your loops.
You want to do them last, after you've moved the whole array.

3. I'm trying to write a function ('rotate') that rotates the first n elements of my string array arr by shift positions in the clockwise direction if shift is positiv (anti-clockwise if negativ shift).

May be you need some steps to develop this code.
The first step could be like this below:
Code:
```#include <stdio.h>
#include <stdlib.h>  /* strncpy, EXIT_SUCCESS */
#include <string.h>

// copies a part of a string of zfolge from the sign 'beginn' including to 'ende' to the string  'erge*
void STRITEIL(char *zfolge, char *erge, int beginn, int ende)
{
int laenge, lge = 0;

lge = strlen(zfolge);
laenge = (ende - beginn) + 1;

if((beginn >= 0) && (beginn <= ende) && (ende < lge) && (laenge >= 1))
{
strncpy( erge, zfolge + beginn, laenge);
}
}

// deletes a part of the string 'erge* from the sign 'beginn' including to 'ende'
void delstrpart(char *erge, int beginn, int ende)
{
int lge = 0, i, j;

lge = strlen(erge);

//printf("*erge: %s\n", erge);
if((beginn >= 0) && (beginn <= ende) && (beginn < lge) && (ende <= lge))
for (i = beginn; i <= ende; i++)
{
for (j = beginn; j < lge; j++)
{
erge[j] = erge[j + 1];
}
//printf("*erge: %s\n", erge);
}

}

int main(int argc, char **argv)
{
char wort[] = "012345678901234567890";
char erge[100] = {0};
char stra[100] = {0};
char strb[100] = {0};
char strc[100] = {0};
char strd[100] = {0};
int lge = -1;

lge = strlen(wort);

// copy part of string
printf("Word: %s\n", wort);
STRITEIL(wort, erge, 7, 11);
printf("est ergo: %s\n", erge);

// deletes a part of a string
printf("Word: %s\n", wort);
strcpy(erge, wort);
delstrpart(erge, 4, 6);
printf("est ergo: %s\n", erge);

// moves part of a string (sings 4 to 6) 2 steps to the left side
strcpy(erge, wort);
STRITEIL(wort, strb, 4, 6); // to moved part
delstrpart(erge, 4, 6);     // del moved part

STRITEIL(wort, stra, 0, 2); // erster Teil
STRITEIL(wort, strd, 3, 4); // erster Teil
STRITEIL(wort, strc, 7, (lge -1)); // erster Teil

printf("deleted ergo: %s\n", erge);

printf("%s %s %s %s\n", stra, strb, strd, strc);

strcpy(erge, stra);
strcat(erge, strb);
strcat(erge, strd);
strcat(erge, strc);

printf("after moved erge: %s\n", erge);

return EXIT_SUCCESS;
}```
For some problems it is better to take first not the computer, but rather
a paper and a pencil to determine coarse the way of proceeding.

4. A example who is better to understand is:
Code:
```#include <stdio.h>
#include <stdlib.h>  /* strncpy, EXIT_SUCCESS */
#include <string.h>  /* strlen */

// copies a part of a string of zfolge from the sign 'beginn' including to 'ende' to the string  'erge*
void part_of_string(char zfolge[], char erge[], int beginn, int ende)
{
int laenge, lge = 0;

lge = strlen(zfolge);
laenge = (ende - beginn) + 1;

if((beginn >= 0) && (beginn <= ende) && (ende < lge) && (laenge >= 1))
{
strncpy( erge, zfolge + beginn, laenge);
}
}

// deletes a part of the string 'erge* from the sign 'beginn' including to 'ende'
void delstrpart(char erge[], int beginn, int ende)
{
int lge = 0, i, j;

lge = strlen(erge);

//printf("*erge: %s\n", erge);
if((beginn >= 0) && (beginn <= ende) && (beginn < lge) && (ende <= lge))
for (i = beginn; i <= ende; i++)
{
for (j = beginn; j < lge; j++)
{
erge[j] = erge[j + 1];
}
//printf("*erge: %s\n", erge);
}

}

// inserts the string 'ins' in string 'ziel' at position 'pos'
void insstr(char ziel[], char ins[], int pos)
{
int lgz = 0, i, j, lgi, lge;

lgz = strlen(ziel);
lgi = strlen(ins);
lge = lgz + lgi;

//printf("laenge ziel ur: %d\n", lgz);
//printf("laenge ziel ins: %d\n", lgi);
//printf("neue laenge: %d\n", lge);
// printf("ziel vorher : %s\n", ziel);

for (i = lge; i >= pos; i--)
{
ziel[i] = ziel[i - lgi];
//printf("ziel[i]: %c\n", ziel[i]);
}

j = 0;
for (i = pos; i < pos + lgi ; i++)
{
ziel[i] = ins[j++];
//printf("ziel[i]: %c\n", ziel[i]);
}

}

int main(int argc, char **argv)
{
char wort[] = "012345678901234567890";
char erge[100] = {0};
char strb[100] = {0};
int lge = -1;

lge = strlen(wort);

// copy part of string
printf("Word..........: %s\n", wort);
printf("Word length...: %d\n", lge);
part_of_string(wort, erge, 7, 11);
printf("part of string: %s\n\n", erge);
// ---------------End of first test-------------------

// moves a part of a string
strcpy(erge, wort);                   // copies string to edit
printf("Word..........: %s\n", erge);
part_of_string(wort, strb, 4, 6);     // copies the part of string to move from position 4 to 6
printf("to delete.....: %s\n", strb);
delstrpart(erge, 4, 6);               // deletes part of string to moded
printf("after delete..: %s\n", erge); // String after delete the part
insstr(erge, strb, 1);                // inserts string 'strb' at position given by argument 3 (here 1) in string 'erge'
printf("after insstr..: %s lge=%lu\n", erge, strlen(erge)); // shows the result

return EXIT_SUCCESS;
}
```

5. Originally Posted by rusyoldguy
A example who is better to understand is:
<snip>
I'm assuming that this is a student project so if it's not, please forgive me. But if it is, for student tasks like these the students are usually expected to not use library functions like strcpy (and if they are they're told which they're allowed to use; e.g. the task might say "no library functions to be used except strlen()". Also, I understand why you've used more than one array -- and the biggest reason I can think of is to avoid undefined behaviour of overlapping arrays when using strcpy and friends -- but I kind of have a gut feeling that the task wants them to do it in place, without secondary arrays. Without seeing the assignment description who knows though.

6. Originally Posted by rusyoldguy
A example who is better to understand
Ok, since you've provided code I decided I'd provide some as well. I haven't really tested either of these extensively but I think they're ok.

Attempt 1 (the obvious way)
Code:
```#include <stdio.h>
#include <assert.h>

void rotate(char *arr, int shift, int n);
void print_array(const char *arr, int n);

int main(void)
{
char arr[] = {'h', 'e', 'l', 'l', 'o'};

print_array(arr, sizeof arr / sizeof arr[0]);
rotate(arr, 2, 4);
print_array(arr, sizeof arr / sizeof arr[0]);

return 0;
}

void rotate(char *arr, int shift, int n)
{
int i, j;
char tmp;

/* The calling function is responsble for making sure that arr != NULL */
assert (arr != NULL);

/* Return early if the calling function is being silly
* i.e. rotating 0 or 1 characters of the sequence makes no sense because the result
* would be the same as no rotatation at all for any value of 'shift'
*/
if (n < 2)
return;

/* No point rotating more than we need to so limit shift. This line can be omitted if
* you don't mind the loops iterating more than they need to; the result will be the same
*/
shift %= n;

if (shift < 0) {    /* Rotate anti-clockwise (to the left) */
shift = -shift;
for (i = 0; i < shift; ++i) {
tmp = arr[0];
for (j = 0; j < n - 1; ++j)
arr[j] = arr[j + 1];
arr[j] = tmp;
}
} else {    /* Rotate clockwise (to the right) */
for (i = 0; i < shift; ++i) {
tmp = arr[n - 1];
for (j = n - 1; j > 0; --j)
arr[j] = arr[j - 1];
arr[j] = tmp;
}
}
}

void print_array(const char *arr, int n)
{
int i;

for (i = 0; i < n; i++)
printf("%c", arr[i]);
printf("\n");
}```
Attempt 2 (a probably more efficient way, at least in theory)
Code:
```#include <stdio.h>
#include <assert.h>

void rotate(char *arr, int shift, int n);
static void rotate_left(char *arr, int shift, int n);
static void rotate_right(char *arr, int shift, int n);
void print_array(const char *arr, int n);
int gcd(int a, int b);

int main(void)
{
char arr[] = {'h', 'e', 'l', 'l', 'o'};

print_array(arr, sizeof arr / sizeof arr[0]);
rotate(arr, 2, 4);
print_array(arr, sizeof arr / sizeof arr[0]);

return 0;
}

void rotate(char *arr, int shift, int n)
{
int i, j, k;
char tmp;

/* The calling function is responsble for making sure that arr != NULL */
assert (arr != NULL);

/* Return early if the calling function is being silly
* i.e. rotating 0 or 1 characters of the sequence makes no sense because the result
* would be the same as no rotatation at all for any value of 'shift'
*/
if (n < 2)
return;

/* No point rotating more than we need to so limit shift. This line can be omitted if
* you don't mind the loops iterating more than they need to; the result will be the same
*/
shift %= n;

if (shift < 0)
rotate_left(arr, -shift, n);
else
rotate_right(arr, shift, n);
}

/*========================================================================*/
/* See "juggling algorithm" */

static void rotate_left(char *arr, int shift, int n)
{
int i, j, k;
int g_cd;
char tmp;

g_cd = gcd(shift, n);
for (i = 0; i < g_cd; i++) {
tmp = arr[i];
j = i;
while (1) {
k = j + shift;
if (k >= n)
k -= n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = tmp;
}
}

static void rotate_right(char *arr, int shift, int n)
{
int i, j, k;
int g_cd;
char tmp;

g_cd = gcd(shift, n);
for (i = 0; i < g_cd; i++) {
tmp = arr[i];
j = i;
while (1) {
k = j - shift;
if (k < 0)
k += n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = tmp;
}
}

/*========================================================================*/

int gcd(int a, int b)
{
if (a < 0)
a = -a;
if (b < 0)
b = -b;
if (b) {
while ((a %= b) && (b %= a))
;
}
return a + b;
}

void print_array(const char *arr, int n)
{
int i;

for (i = 0; i < n; i++)
printf("%c", arr[i]);
printf("\n");
}```

-----

If I use this for main (using the second implementation above):
Code:
```int main(void)
{
char arr[] = "012345678901234567890";

print_array(arr, 21);

rotate(arr, 7, 11);

print_array(arr, 21);
print_array(arr, 11);

return 0;
}```
I get as output:
Code:
```012345678901234567890
456789001231234567890
45678900123```
This is slightly different to what you provide as output. So one of us has something wrong. The output of my program looks right, but perhaps I'm missing something (maybe missing enough beer)

-------
Edit 2: If anyone has more information on the juggling algorithm implemented, please let me know. Writing it down on paper I can understand how it works and I recall first using it (or a very similar variant) around about the year 2000. The datestamp on my archive for the implementation is for the year 2000 anyway, but the problem is I think the datestamp reflects the date I restored from a backup and not when I wrote the original program. I can't recall where I came across the algorithm (I doubt I derived it myself). I've just looked through Knuth (TAOCP) and can't really see it mentioned so I don't think it's from there. But TAOCP, especially back in 2000, is my first call for algorithms and I can't think of where else I may have come across it. Unfortunately I don't have a comment in the original code referencing where the algorithm comes from (ugh).

7. Well, I still can't find a good reference. However I did find this paper (https://pages.mtu.edu/~shene/PUBLICA...y-Rotation.pdf) (the paper is linked to from the Author's web page (Publications). I can't remember ever seeing that paper before but I do recall looking at early STL implementations so maybe I just copied the idea from there. Who knows. The paper is an interesting read anyway

8. For some reason I found this problem interesting so I did some more testing. I modified the gcd function to make it clearer (the new version might be faster but not significantly and the call to gcd() contributes nothing to overall execution time anyway). I also wrote another version of the loop method but replaced the inner loop with memmove() (cheating because I doubt a class assignment would allow calls to library functions). Then I tested them all using valgrind and different gcc optimisation levels.

Code:
```ARRSIZE  90000000
Shift    100

compiler optimisation: none
rotate_loops         126000000924    Incl. Cost: Ir
rotate_memmove          914067971        Incl. Cost: Ir
rotate_juggle          1890000854        Incl. Cost: Ir

compiler optimisation: -O2
rotate_loops          45000000221        Incl. Cost: Ir
rotate_memmove          914068595        Incl. Cost: Ir
rotate_juggle           990000528        Incl. Cost: Ir

compiler optimisation: -O3
rotate_loops            914064900        Incl. Cost: Ir
rotate_memmove          914068595        Incl. Cost: Ir
rotate_juggle           900000628        Incl. Cost: Ir```
Looking at the asm generated when using -O3 the code for the looping method is virtually identical to that using memmove (they both use memcpy actually but I can't use that function because of UB when there is overlapping areas of memory... the compiler can, and does, though). I would say that using a temporary array could improve speed even more (at the expense of increased memory usage obviously) because I could then move whole chunks like rusyoldguy, but my interest waned and I should be doing real work anyway. I also implemented the variation of the juggle method described in the aforementioned paper, but it makes basically no difference at all in my tests (probably because the call to gcd() is so insignificant). I'm quite impressed that when using -O3 that gcc replaced the inner loop with memcpy; pretty tricky. Of course these results are CPU/Instruction set dependent as well, but it was an interesting exercise, so *shrug*.

Edit: I did not anticipate that using -O3 using gcc for my CPU would replace that inner loop with a very fast memory copy, so it was worth doing

I should also add that for the tests I don't print the results like in the source code I provided in a previous post; that'd be silly

Although maybe less meanginful than the Ir I compiled each version with no optimisation and took the average time of three runs (using the time command and with array size of 90000000 and a shift of 100 just like above)

Code:
```rotate_loops:     16.862 seconds
rotate_memmove:    0.635 seconds
rotate_juggle:     0.693 seconds```