Coding a Bubble Sort routine using a pointer array

[loonychune]

I have been asked to code a Bubble Sort using a pointer array and pointer notation as opposed to the square bracket notation...(there should be two uses of square brackets when declaring the arrays). It will not work! :(

Basically the data does not sort. I am trying to swap pointer array elements rather than the main array elements (as this is a faster process) but cannot quite figure it out.

A quick gander over the work would be much appreciated!

#include <iostream>
using namespace std;

const int size = 1000;

int main(void){

int arr[size];
int *p[size];
for(int i = 0; i < size; ++i){
*(p + i) = (arr + i);
} //each pointer *p gives the address of arr

int j = sizeof(arr)/sizeof(int);
for(int i = 0; i < size; ++i){
count << "Please enter an integer (0 to end):" << ' ';

cin >> *(arr + i);
if (*(arr + i) == 0){
j = i - 1;
break;
}
}

count << "\nThe unsorted array is:\n" << endl;
for(int i = 0; i < j + 1; ++i){
count << "Element "<< i <<": " << *(arr + i) << endl;
}

int *t;
for(int a = 0; a < j; ++a){ //determines number of passes
for(int i = 0; i < j; ++i){ //iterates through input data for each pass
if(*(arr + i) > *(arr + i + 1)){
t = *(p + i);
*(p + i) = *(p + i + 1);
*(p + i + 1) = t;
}
}
} //end of bubble sort

count << "\nThe sorted array is:\n" << endl;
for(int i = 0; i < j + 1; ++i){

count << "Element "<< i <<": " << *(arr+i) << endl;
}
count << "\nThank you for using Bubble Sort." << endl;
} // end of main

 

[Coin]

Hmm, okay... so...

Couple small pieces of advice before I say anything...

First off you should never ever say *(p + i). The reason for this is that p[ i ] is actually the same thing as *(p+i). When the compiler sees p[ i ], this is actually shorthand for *(p+i). (Arrays and pointers in C are secretly the same thing, kind of.) It is better to say p[ i ] because your code will be clearer.

Also, it is probably not a good idea to say "i < j + 1". Here it is probably better to say "i <= j". This is "i is less than or equal to j" and it comes out to the same thing as "i < j + 1". The reason is the same: It is clearer what your intent is.

Another, small bug: You seem to be using j in contradictory ways in different places. The first time you set it, you set it to "sizeof(arr)/sizeof(int)" (won't this just be the same as "size", because of how you defined arr above? Well, not important). The second time you set it is the "j = i - 1". This is a bug because you are setting slightly different things both times. The first time you are setting j to be an array length. The second time you are setting j to be an array index. Worse, some of the code that follows expects j to be an array length and some expects it to be an array index. For example, when you say
for(int i = 0; i < j + 1; ++i)
...when you print the values, you are expecting j to be the final index of arr. You are iterating i over [0 to j] inclusive. However when you say
for(int a = 0; a < j; ++a){ //determines number of passes
...when you perform a pass of the bubble sort, you are expecting j to be the length of arr. You are iterating i over [0 to j) not including j.

Have I lost you? Basically this is bad because if you enter 1000 elements, then your sort will work, but your "count element" line will print 1001 elements-- including one junk element at the end; but if you enter 5 elements, then your count will print the right number of elements, but the sort will sort only the first 4 elements, ignoring the fifth!

Finally, why the bubble sort itself does not work:

The reason why it does not work is that you are not sorting arr. You are sorting p, based on values from the array which the pointers in p point to. This does not work for two reasons. First off, it does not work because at the end of your "bubble sort", arr is unchanged! You do not at any point do anything at all to alter arr, you only alter p. Second off, you are not actually "bubble sorting" p because the bubble sort assumes that the array being tested is being changed with each pass. Because you are testing the values of arr against each other, but only altering the values of the pointers in p, each pass is exactly the same.

You need to either
- Change your swap so that you are swapping arr and arr[i+1], not p and p[i+1], or
- Change your test so that instead of comparing arr to arr[i+1], you are comparing *p to *p[i+1]; and change your final count so that instead of printing the values of arr in order you are printing the values in the order that they are pointed to by the pointers in p.

Does this make sense?

 

[loonychune]

Yes it makes sense thanks a lot, especially for going over the whole code...

I see your point about p as opposed to *(p + i) however the nature of the task is to use pointer notation and so i might well have to leave the latter notation in there (I have several submissions and will review the feedback after each submission).

I got caught up on the question he gave us, in which he said swap the array elements, so was reluctant to swap the arr elements.

What i tried also was this:

int arr[size];
int *p = arr;

instead of declaring int* p[], and equating *(p + i) = *(arr + i), so by swapping the pointers i am really just swapping array elements (which i don't suppose is at all necessary in general but again i come back to the notation necessities the tutor imposed).

If i do in fact have to declare int *p[size] and then relate each *p to &arr, how do i go about actually doing this bit?:

and change your final count so that instead of printing the values of arr in order you are printing the values in the order that they are pointed to by the pointers in p.

Again, thanks a lot.

 

[Coin]

If i do in fact have to declare int *p[size] and then relate each *p to &arr, how do i go about actually doing this bit?:

change your final count so that instead of printing the values of arr in order you are printing the values in the order that they are pointed to by the pointers in p

So, if you have a pointer
(POINTER)
then the value it is pointed to can be accessed by
*(POINTER)

So, if *( p + i ) is a pointer, then *( *( p + i ) ) is the value that pointer points to. You want to iterate over p instead of arr, and instead of printing out the items in p, print out the dereferenced (*-ed) value of each item in p.

 

[loonychune]

Oh aye i did try *(*()) but it kept falling over, just didn't seem to like it without any reason. I'll try it if the first few submissions don't work out...

Thanks a lot Coin. :)