RE: circshift C

[Graham Toal]

There's another shuffling algorithm that's trickier to get right and can be 
faster if the left and right sections of the rotation are closer in size.  This 
is a function where measuring performance is worth the effort, if it is a 
significant overhead in your code.  (If not, the reversal code is almost 
idiot-proof to get right)  You should instrument it to count the swaps as well 
as timing it...

Anyway, I had 15 minutes spare at the end of the day and I wanted to see if I 
could still hack these CS101 style problems, so here's my version of array 
reversing, with the two best algorithms :-)

It's not this complicated if you can afford the space for a duplicate array to 
hold the results, which I think is how circshift is spec'd?  But if you can 
rewrite your code to use your own functions and avoid the memory overhead, then 
one or both of these (or a hybrid) are the ticket...

(btw I modified the recursive algorithm to use explicit tail recursion which 
converts it to an iterative solution.)

G

#include <stdio.h>
#include <stdlib.h>

// Rotate a subset of a array

//           0 1 2 3 4 5 6 7 8 9
// eg rotate A B C D E F G H I J, 2, 3, 8
//               \_/ \_______/

// =>        A B E F G H I C D J
//               \_______/ \_/


void reverse(int *A, int low, int high)
{
  while (low < high) {
    register int temp = A[low];
    A[low++] = A[high];
    A[high--] = temp;
  }
}

void rotate_by_reversals(int *A, int first_index, int rot_index, int last_index)
{
  //               f r         l
  //           0 1 2 3 4 5 6 7 8 9
  // eg rotate A B C D E F G H I J, 2, 3, 8
  //               \_/ \_______/
  // =>        A B E F G H I C D J, 2, 3, 8
  //               \_______/ \_/



  if (first_index == rot_index || rot_index+1 == last_index) return;
  reverse(A, first_index, rot_index);
  //               f r         l
  //           A B C D E F G H I J
  //               \_/
  // =>        A B D C E F G H I J

  reverse(A, rot_index+1, last_index);
  //               f r         l
  //           A B D C E F G H I J
  //                   \_______/
  // =>        A B D C I H G F E J

  reverse(A, first_index, last_index);
  //               f r         l
  //           0 1 2 3 4 5 6 7 8 9
  //           A B D C I H G F E J
  //               \___________/

  // =>        A B E F G H I C D J
  //               \___________/

}

void swap_blocks(int *A, int left, int right, int len)
{
  // preserve order
  while (len-- > 0) {
    register int temp = A[left];
    A[left++] = A[right];
    A[right++] = temp;
  }
}

void rotate_by_blocks(int *A, int first_index, int rot_index, int last_index)
{
  int len;
  while (first_index != last_index) {
  if (rot_index-first_index+1 < last_index-rot_index) {

    len = rot_index-first_index+1;

    //               f r         l
    //           0 1 2 3 4 5 6 7 8 9
    // eg rotate A B C D E F G H I J, 2, 3, 8
    //               \_/ \_______/

    // =>        A B E F G H I C D J
    //               \_______/ \_/


    swap_blocks(A, first_index, rot_index+1, len);
    //               f r         l
    //           0 1 2 3 4 5 6 7 8 9
    //           A B C D E F G H I J
    //               \_/ \_/
    // =>        A B E F C D G H I J
    //               \_/ \_/

    // rotate_by_blocks(A, rot_index+1, rot_index+len, last_index);
                           first_index = rot_index+1;
                                        rot_index += len;
    //               f r         l
    //           A B E F C D G H I J
    //                   \_/ \___/
    // =>        A B E F G H I C D J
    //                   \___/ \_/

  } else {
    len = last_index-rot_index;
    //               f       r   l
    //           0 1 2 3 4 5 6 7 8 9
    // eg rotate A B C D E F G H I J, 2, 6, 8
    //               \_______/ \_/
    // =>        A B H I C D E F G J
    //               \_/ \_______/


    swap_blocks(A, rot_index-len+1, last_index-len+1, len); // or rot_index, 
last_index, -len ???
    //               f       r   l
    //           0 1 2 3 4 5 6 7 8 9
    //           A B C D E F G H I J
    //                     \_/ \_/
    // =>        A B C D E H I F G J

    // rotate_by_blocks(A, first_index, rot_index-len, rot_index);
                                                       last_index = rot_index;
                                        rot_index -= len;
    //               f       r   l
    //           A B C D E H I F G J
    //               \___/ \_/
    // =>        A B H I C D E F G J
    //               \_/ \___/
  }
  }
}

int main(int argc, char **argv) {
  int fred[10], i;

  for (i = 0; i < 10; i++) fred[i] = i+'A';
  fprintf(stdout, "rotate_by_reversals(ABCDEFGHIJ, 2, 3, 8) => ");
  rotate_by_reversals(fred, 2, 3, 8);
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n');

  for (i = 0; i < 10; i++) fred[i] = i+'A';
  fprintf(stdout, "rotate_by_blocks(ABCDEFGHIJ, 2, 3, 8) => ");
  rotate_by_blocks(fred, 2, 3, 8);
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n');

  exit(0);
  return(1);
}

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Graham Toal
Sent: Thursday, March 14, 2013 9:32 AM
To: address@hidden
Subject: RE: circshift C

> hi all,

> can anyone provide C version of circshift function?

> regards,
> abhishek

You need the old reversing trick.

http://leetcode.com/2010/04/rotating-array-in-place.html

modify appropriately for your data type...

_______________________________________________
Help-octave mailing list
address@hidden
https://mailman.cae.wisc.edu/listinfo/help-octave