1,105,331 Community Members

question about dynamic array and shifting array

Member Avatar
koricha
Newbie Poster
15 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hello

This program uses a dynamic array , which shifts x elements to the right. the program works, but my question is whether i defined shift_elements(int index,int pl) in the right way or is there a different way to do the function in the main()

thank you

class MyArray {
	public:
		MyArray(int size);
		~MyArray();
		int read_element(int index);
		void write_element(int index, int value);
		void shift_elements(int index,int pl);
	
	private:
		int *storage;


};
#include <iostream>
#include "myarray.h"

using namespace std;

int main()
{
	int i,size;
	int places;
	int x;
	cout<<"please enter the size of the  dynamic array"<<endl;
	cin >> size;
	cout<<"please enter the dynamic array"<<endl;
	MyArray p(size);

	for(i=0 ; i<size; i++){	
		cin >> x;
		p.write_element(i, x);
	}
	cout<<"This is your dynamic array"<<endl;
	for(i=0 ; i<size; i++){
		cout << p.read_element(i)<<" ";
	}
	cout<<endl;
	
	cout<<"how many place you want to shift? " <<endl;
	cin>>places;
	cout<<"This is the shifted array"<<endl;

	
		 p.shift_elements(size,places);
		
		
}
#include <iostream>
#include "myarray.h"
using namespace std;
MyArray::MyArray(int size)
{
	storage = new int [size];
}

MyArray::~MyArray()
{
	delete [] storage;
}

int MyArray::read_element(int index)
{
	return storage[index]; 
}

void MyArray::write_element(int index, int value)
{
	storage[index] = value;
}
void MyArray::shift_elements(int index,int pl)
{
for(int k=0;k<pl;k++)
{
	int temp;
	
		for (int i=0; i<(index -1); i++)
		{
		temp = 	storage[index-1];
		storage[index-1] = storage[i];
		storage[i] = temp;
		}
}
		for(int e=0;e<index;e++)
		{
			cout<<storage[e]<<" ";
		}
}
Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 
void MyArray::shift_elements(int index,int pl)
{
    for(int k=0;k<pl;k++)
    {
	int temp;
 
        for (int i=0; i<(index -1); i++)
        {
            temp = storage[index-1];
            storage[index-1] = storage[i];
            storage[i] = temp;
        }
    }
}

Any shifting algorithm that requires swapping or a nested loop is inefficient. Do it all in one shot. If you are shifting right four spaces, then you should set up a temporary array for the four right-most bytes, copy them into that temporary array, then have ONE loop that moves each remaining byte right 4 places. No swaps are necessary. When the shift is complete, copy the temporary array to the beginning of the permanent array.

As an alternate to the loop, you can also use the memmove function from the cstring library.

http://www.cplusplus.com/reference/clibrary/cstring/memmove/

Member Avatar
koricha
Newbie Poster
15 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Thank you VernonDozier

How can i shift the elements without swapping, also can you tell me more about the temporary array

Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

Let's look at what needs to be accomplished, forgetting the computer program. Focus on the algorithm.

Before : 1 2 3 4 5 6 7 8 9 10
After  : 7 8 9 10 1 2 3 4 5 6

Pretend that you as a human being needed to do this. Pretend these are 10 blocks with numbers on them next to each other. How would you do it? Would you swap anything? Almost assuredly not. Here's what you would do.

  1. Create a spot large enough to hold blocks 7 through 10 if one does not already exist.
  2. Move blocks 7 through 10 out of the way. In other words, shove them somewhere TEMPORARILY so they were out of the way. In other words, put them where you cleared the space in step 1.
  3. Shove blocks 1 through 6 fours spaces right all at once.
  4. Shove blocks 7 through 10 where 1 through 4 used to be all at once.
  5. At this point, the space from step 1 is no longer needed.

That's what you would do as a human being. Make your program follow this.

  1. If a temporary array does not already exist, create one. In other words, declare an array statically that is large enough to handle the largest possible storage. If this is unknown, create it dynamically with the "new" command.
  2. Move blocks 7 to 10 to this temporary array using a loop, memmove, or memcpy.
  3. Move blocks 1 through 6 using a loop or memmove.
  4. Move blocks 7 to 10 where 1 through 4 were using memcpy, memmove, or a loop.
  5. If you created an array in step 1 with "new", "delete" it.

So you model your program after the way you'd explain step by detailed step to a person who didn't understand how to do it. It might be useful to actually create pieces of paper and number them and physically move them around first. Get the algorithm down before attacking the code. If you didn't need to "swap" when moving the papers around, you don't need to swap in the program. Look at what you do with the papers and make your loop follow that.

Member Avatar
koricha
Newbie Poster
15 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

thank you very helpful

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: