Thread: Left Shift elements of a 2D array

  1. #1
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Left Shift elements of a 2D array

    I am rather new to C programming and I am trying to learn as much as possible.
    We recently had an assignment centered around 2D arrays.
    We had to write several functions...

    InitializeAllZeroes2D
    PopulateRandom2D
    BubbleSort2D
    LinearSearch2D and
    PrintArray2D

    I got them all, but there is a BONUS point.

    I need to perform a single left shift on the 2D array which moves
    the first element Array[1] [1] to the last element Array[R] [C],
    (where R and C are the size dimensions of the array) and in
    doing so, all of the other elements should move one index to
    the left.

    And I can't figure it out!!!!

    I'm not looking for a coded answer. I prefer to figure it out on my own.
    What I hope to get here, is a starting point or a push in the right direction.
    Some advice as to how to tackle the problem.

    I know I need to store the first element of the array in a temp variable,
    so I can store it in the last element later, but I don't know how to
    move all of the other elements before replacing it.

    Any advice is appreciated.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Now that you have the first element of the array stored, what number goes there now? (Note that this is the only element you can replace without stomping over a number you need to keep.)
    Now that you have <the answer to the last question> stored, what number goes there now? (Note that this is the only element you can replace without stomping over a number you need to keep.)
    Now that you have <the answer to the last question> stored, what number goes there now? (Note that this is the only element you can replace without stomping over a number you need to keep.)
    .
    .
    .
    Repeat until the answer is "the original first element" and you're done.

  3. #3
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    So I guess I should use 2 temporary variables then.
    One for the first element that I will keep until the end
    And one to temporarily keep the elements that I'm moving.

    How do I keep from overwriting the first temporary variable
    on each new revolution of the loop?

  4. #4
    Registered User
    Join Date
    Dec 2007
    Posts
    214
    Quote Originally Posted by w2look View Post
    So I guess I should use 2 temporary variables then.
    One for the first element that I will keep until the end
    And one to temporarily keep the elements that I'm moving.

    How do I keep from overwriting the first temporary variable
    on each new revolution of the loop?
    No. You only have to save the first element for later use. Then you can overwrite the array elements as you are moving things.
    Last edited by DaveH; 01-22-2009 at 09:46 AM.

  5. #5
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    OK, here is what I have come up with.

    Code:
    void LeftShift2D(int array [R] [C])
    {
    	int lim = R * C;
    	int temp = array[R-1] [C-1];
    	
    	for(int i = lim - 1; i >= 0; i--)
    	{
    		int ri = i / C;
    		int ci = i % C;
    	
    		for(int j = 0; j < i; j++)
    		{
    			int rj = j / C;
    			int cj = j % C;
    			
    			array[ri] [ci] = array[rj] [cj];
    			
    		}
    	}
    	array[0] [0] = temp;
    }
    Unfortunately, this performs a right shift and I need a left shift.

    I can't see what I'm doing wrong.

    Any suggestions?

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    do you think one element of the array could hold more than one value?

    Why you are using a loop to fill array[ri] [ci]

    You do not beleive that the computer could do corect assignment first time you ask him and you should repeate it several times as does teacher in the class?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    You want to make it really easy?
    • Cast the 2-dimensional array to a 1-dimensional array.
    • Store the first element in a temporary variable.
    • Shift the entire array to the left by 1.
    • Store the temporary value back into the last element of the array.

    That's what I would do at least. In fact, if you had a function already written called LeftShift1D(int *array, int size), you could use it like this: LeftShift1D((int*)array2d, R*C).

  8. #8
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    Wow!

    Thanks for all the replies.

    I actually got it to work while I was away from the board.
    However, I did it by cheating.
    The function I wrote will return the array with all the elements
    shifted one index to the left, but the program actually shifts
    the array one index to the right over and over again until it
    merely appears to have been shifted left.

    Code:
    void LeftShift2D(int array [R] [C])
    {
    	int lim = R * C;
    	int n = 0;
    	
    	while(n < lim - 1)
    	{
    	
    	int temp = array[R-1] [C-1];
    	
    	for(int i = lim - 1; i >= 0; i--)
    	{
    		int ri = i / C;
    		int ci = i % C;
    	
    		for(int j = 0; j < i; j++)
    		{
    			int rj = j / C;
    			int cj = j % C;
    			
    			array[ri] [ci] = array[rj] [cj];
    			
    		}
    	}
    	array[0] [0] = temp;
    	n++;
    	}
    }
    I know, I know, I took the easy way out. I just slapped it in
    a while loop until it did my bidding. It may work, but the
    complexity is through the roof and it can be done much more
    efficiently.

    I'm going to take some time, look over the advice presented here
    and see if I can improve it.

    Thanks to all who offered help.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Hah, I was going to suggest that option as a joke.
    I guess the joke's on me!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. Replies: 1
    Last Post: 10-21-2007, 07:44 AM
  3. Copying from one 2d array to another....with a twist
    By Zildjian in forum C++ Programming
    Replies: 2
    Last Post: 10-24-2004, 07:39 PM
  4. 2d array problem
    By LiLgirL in forum Windows Programming
    Replies: 1
    Last Post: 03-15-2004, 02:23 PM
  5. Please help me
    By teedee46 in forum C++ Programming
    Replies: 9
    Last Post: 05-06-2002, 11:28 PM

Tags for this Thread