Hi everybody - I'm taking my first programming class ever......online (which I wouldn't have done if I had it to do over). I'm working on this assignment and I cant get through to my instructor. Here's what he wants:
Write a program to declare and initialize the following array:
int array[] = { 10, 20, 30, 40, 50, 60 };
Now add code to the program that uses a loop to exchange the outermost pair
of element values, then the next interior pair, and so on until the innermost
pair of values is exchanged. Write the program so that it is not sensitive to
the number of elements in the array and test it on an integer array that
contains an odd number of elements. Your program may not have more than one
array. You may use a temp variable in the swapping process.
The program output should be similar to the following:
NOTE: you can determine the number of elements in an array with the
following:
int array[] = { 10, 20, 30, 40, 50, 60 };
int x;
x = sizeof(array) / sizeof(array[0]);
// sizeof is a function in iostream.h
Use the sizeof() function to determine the number of elements in any arrays
that are initialized before compilation in all the following assignments. If
the number of elements is determined at run time by console input, then you
may use a counter variable to determine the number of elements in an array.
Here's what I was trying:
#include<iostream>
using namespace std;
int main() {
int array[] = { 10, 20, 30, 40, 50 };
int s = sizeof(array) / sizeof(array[0]);
int n = s - 1;
int x = 0;
while (n > s / 2) {
array[x] = array[n];
n--;
x++;
}
cout << "The inverted array is " << array[s] << endl;
system("PAUSE");
return 0;
}
But it's not giving back what I'd like..... Any insight? - And remember you're dealing with a newbie here Thanks - And sorry this is so long.
You should implement a swap in your while-loop rather than a simple assignment. As a result, you only copy the result from, e.g. x[4] into x[0] and x[3] into x[1] but forgetting to do x[0] into x[4] and x[1] into x[3]. The swapping functionalities can be achieved as follows.
Code:
int temp = array[x];
array[x] = array[n];
array[n] = temp;
In addition, you shouldn't use array[s] where s = 5 for displaying the result of the last element in the array. Since array in C/C++ is always zero-based, the valid range is from 0 to 4 for a 5 elements array.
quoted from C++ Coding Standards:
KISS (Keep It Simple Software):
Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
Avoid magic number:
Programming isn't magic, so don't incant it.
iostream.h is not a standard header - use <iostream>.
sizeof is not a function - but an operator.
There is a std::swap that you can use.
If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.
Also, always try to encapsulate small pieces of logic into functions. Like in you code you could choose to make a swap function - one to print the array and one to fill the array and things like that instead of writing everything in main().
Last edited by exterminator; April 11th, 2006 at 03:13 AM.
xenodamus
Debug your code. See what state your data are in on every step and what changes you get after each operation. If you are not familiar with debugger, write printing methods which print state of system every now and then. For example you could change your source so (not fixing your bugs here):
Code:
#include<iostream>
using namespace std;
int array[] = { 10, 20, 30, 40, 50 };
int size = sizeof(array) / sizeof(array[0]);
void print_array() {
for(int i=0;i<size;++i)
cout<<array[i]<<" ";
cout<<endl;
}
int main() {
int s = size;
int n = s - 1;
int x = 0;
while (n > s / 2) {
cout<<"before change (n= "<<n<<", x= "<<x<<"): ";
print_array();
array[x] = array[n];
cout<<"after change: ";
print_array();
n--;
x++;
}
cout << "The inverted array is ";
print_array();
system("PAUSE");
return 0;
}
Originally Posted by exterminator
There is a std::swap that you can use.
If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.
Also, always try to encapsulate small pieces of logic into functions. Like in you code you could choose to make a swap function - one to print the array and one to fill the array and things like that instead of writing everything in main().
I think it's definately too much for "first programming lesson ever with instructor who says that sizeof() is function from iostream.h".
"Programs must be written for people to read, and only incidentally for machines to execute."
You might not care about this, but I'll post it here in case you are interested.
A really neat trick exists by which you can swap two values without going through a temporary variable. It relies on bit manipulation using XOR.
Code:
int a, b;
// assign values to a and b.
// Swap starts here
a = a ^ b; // a ^= b;
b = a ^ b; // b ^= a;
a = a ^ b; // a ^= b;
// Swap ends here
To see how it works, imagine the four possible combinations of pairs of bits, where one bit of each pair is in a and one bit of each pair is in b.
Code:
a = 1010 // binary number
b = 1100 // binary number
Now watch what happens at each step.
Code:
a ^= b;
// Result a = 0110
// b = 1100
b ^= a;
// Result a = 0110
// b = 1010
a ^= b;
// Result a = 1100
// b = 1010
This trick does have one pitfall. You have to make sure you are not using it in an algorithm where a memory location will be swapped with itself because array[i] ^ array[j] == 0 if i == j. If this could happen you want to use a temporary variable.
I think this trick might have come from MIT's AI lab. Their people had a list of tricks and problems collectively refererred to as HAKMEM. See <http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html>.
A really neat trick exists by which you can swap two values without going through a temporary variable. It relies on bit manipulation using XOR.
It is a funny trick, but not a neat trick!
At best, it won't change the program's speed.
At worst, it will reduce the program's speed, and may introduce bugs.
Moreover it only works with integers!
That you see no temporary variable doesn't mean that there are none!
In fact, a^=b, needs at least a temporary register for the value of b.
This trick avoid the explicit declaration of an automatic variable. That's fun, but useless.
This trick is inefficient for compilers supporting temporaries in registers!
Moreover if a and b may be aliases, not only it behaves incorrectly, but also it reduces the possibilities of compiler optimization (the work can't be done in registers)!
Last edited by SuperKoko; April 12th, 2006 at 02:08 AM.
"inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
Club of lovers of the C++ typecasts cute syntax: Only recorded member.
Out of memory happens! Handle it properly!
Say no to g_new()!
In inline code (or with a less good optimizer) , these speed differences may be greater.
"inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
Club of lovers of the C++ typecasts cute syntax: Only recorded member.
Out of memory happens! Handle it properly!
Say no to g_new()!
If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.
Reversing vectors is not efficient. That is the reason why standard vector doesn't have reverse member function and std::list does.
Unfortunately the source data is a C style array and I don't see anything more simplier and efficient than the methods proposed above.... may be you do.
I thought at first that std::reverse(array[0],array[n]); could do the job efficiently but I was wrong.
He would have to first copy the array into std::lilst than reverse it and then copy back. That is so inefficient.
Last edited by LanTHrusteR; April 12th, 2006 at 05:24 AM.
Reversing vectors is not efficient. That is the reason why standard vector doesn't have reverse member function and std::list does.
Correct, the reverse is probably just a member in microsoft implementations. I did not find it in the standards.. or Dinkumware implementation. However, as far as efficiency is concerned - I am not sure that it would be really bad considering we are using the swap mechanism with the array.
However, the vector might not actually need to be reverse at all. One could always use the reverse_iterator whenever a reverse vector is to be used. One can also mimic this behaviour with C-style arrays. And since the OP is only doing that to print to the standard output.. this is the best way to go.. without even actually doing the reverse unless that is a rigid requirement. Regards.
Last edited by exterminator; April 12th, 2006 at 07:23 AM.
It is a funny trick, but not a neat trick!
At best, it won't change the program's speed.
At worst, it will reduce the program's speed, and may introduce bugs.
These objections are practical, certainly, and ultimately we are all concerned with what's going to happen when the rubber meets the road. From other perspectives though, I sometimes find the theoretical to be interesting. Moreover, principles don't change when practical implementations do.
Originally Posted by SuperKoko
Moreover it only works with integers!
...but data in a digital computer is just a bunch of 0s and 1s. Those 0s and 1s could be an integer, text, music, or a picture. Consider the probably not portable code sample below...
That you see no temporary variable doesn't mean that there are none!
In fact, a^=b, needs at least a temporary register for the value of b.
This trick avoid the explicit declaration of an automatic variable. That's fun, but useless.
If the data you are swapping comes from memory, the compiler will have to fetch it and put it somewhere where the processor can operate on it, regardless of how you actually perform the swap. If the compiler decides to put it in registers, the actual swap could in principal be as simple as the C code implies consder...
void swapf(int& a,int& b)
{
int c=a;
a=b;
b=c;
}
void swap(int& a,int &b)
{
a^=b;
b^=a;
a^=b;
}
On a different note, isn't it best to avoid using references in a function like this? Wouldn't "void swap(int * a, int * b)" make clearer at the point where this function is invoked that a and b might be altered. I try to limit my use of references to places where they are really needed, such as when overriding some operator or in a copy constructor.
We have some code in use where I work that was written before a certain gigantic software company's version of the STL was useable. This code implements its own queues and vectors, but unfortantly the function to enqueue something takes its argument as a reference. We don't have to look at this code often enough to remember how it works, and more than once we have we have thought we have stumbled onto a memory leak because we will see something like this...
Code:
if (pThing != NULL)
{
Node * pNode = new Node;
pNode->data = pThing;
queue.enque(*pNode); // So enqueue makes a copy of pNode?
// memory leak? Where is pNode deleted if not here since it has local scope?
}
What is totally unobvious is that enqueue internally generates a pointer to the reference and stores it. pNode gets deleted later when it is dequeued. But all of this would be much more obvious if enqueue accepted the non-const pointer instead of a reference.
Cheers,
GeoRanger
Last edited by GeoRanger; April 12th, 2006 at 11:59 PM.
Reason: Meant to indicate that pNode is of local scope in last code snippet.
...but data in a digital computer is just a bunch of 0s and 1s. Those 0s and 1s could be an integer, text, music, or a picture. Consider the probably not portable code sample below...
Did you ever heard of non-POD types?
If the data you are swapping comes from memory, the compiler will have to fetch it and put it somewhere where the processor can operate on it, regardless of how you actually perform the swap. If the compiler decides to put it in registers, the actual swap could in principal be as simple as the C code implies consder...
Which is excessively slow : 3 CPU cycles! Absolutely not parallelizable!
While, with an intermediate temporary, a good compiler (I tested with GCC 3.2.3) may even produces no operation, and simply "rename" the variables as far as possible!
Or, a bad compiler, will simply generate:
Code:
mov edx,eax
mov eax,ebx ; 1 cycle (k6-2 processor)
mov ebx,edx ; 0.5 cycle (I mean that it can be paired with the next instruction)
But, a good compiler will often find "tricks" to optimize!
For example, with GCC 3.2.3:
Code:
#include <stdio.h>
void Swap(int& i,int& j)
{
int k=i;
i=j;
j=i;
}
int input();
int main()
{
int i,j;
i=input(); j=input();
if (input()) Swap(i,j);
printf("%d %d", i, j);
return 0;
}
Code:
#include <stdio.h>
int input()
{
int w;
scanf("%d",&w);
return w;
}
In short, the swap operation used 2.5 cycles instead of 1.5 !
Originally Posted by GeoRanger
On a different note, isn't it best to avoid using references in a function like this? Wouldn't "void swap(int * a, int * b)" make clearer at the point where this function is invoked that a and b might be altered. I try to limit my use of references to places where they are really needed, such as when overriding some operator or in a copy constructor.
Do you come from a C background?
I used the cannonical syntax of the standard library (std::swap), all C++ programmers can understand that perfectly, since they are used to std::swap!
In fact, std::swap is the best candidate for optimization, since the compiler is free to create optimizations specifically for that function.
Originally Posted by GeoRanger
What is totally unobvious is that enqueue internally generates a pointer to the reference and stores it. pNode gets deleted later when it is dequeued. But all of this would be much more obvious if enqueue accepted the non-const pointer instead of a reference.
Here, a reference is not natural, because it is a "pointer sink". But for std::swap, it is natural (at least from the point-of-view of a C++ programmer). std::swap does not delete the data!
In fact, since it is a pointer sink, a std::auto_ptr would be very natural, and implicitly documents perfectly that the function "gets ownership" of the data.
"inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
Club of lovers of the C++ typecasts cute syntax: Only recorded member.
Out of memory happens! Handle it properly!
Say no to g_new()!
duuuuuuuuudesss, swap sounds VERY BAD!!! i mean swap?? no need to swap !!
create a new array copy old array reversed to the new array destroy old array and set the old array pointer to the new array pointer. and thats it. dont you think its HECK ALOT faster than swapping all vars??
Array Inversion??
Thanks - And sorry this is so long.
Reply With Quote
My Blogs : 
Re: Array Inversion??
Originally Posted by exterminator
Bookmarks