Coding a Bubble Sort routine using a pointer array

In summary, the conversation is about coding a bubble sort using pointer array and pointer notation. The code provided is not correctly sorting the data due to not swapping the correct elements and using contradictory variables. The expert suggests changing the swap to involve arr[i] instead of p[i] or changing the test and final cout to compare and print the values pointed to by the pointers in p. There is also discussion about the use of pointer notation and the task requirements.
  • #1
loonychune
92
0
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){
cout << "Please enter an integer (0 to end):" << ' ';

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

cout << "\nThe unsorted array is:\n" << endl;
for(int i = 0; i < j + 1; ++i){
cout << "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

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

cout << "Element "<< i <<": " << *(arr+i) << endl;
}
cout << "\nThank you for using Bubble Sort." << endl;
} // end of main
 
Technology news on Phys.org
  • #2
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 "cout element" line will print 1001 elements-- including one junk element at the end; but if you enter 5 elements, then your cout 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 cout 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?
 
  • #3
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 cout 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.
 
  • #4
loonychune said:
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 cout 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.
 
  • #5
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. :)
 

What is a Bubble Sort routine?

A Bubble Sort routine is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

What is a pointer array?

A pointer array is an array where each element is a pointer to another location in memory. It allows for more efficient manipulation and access of data.

What are the steps involved in coding a Bubble Sort routine using a pointer array?

The steps involved in coding a Bubble Sort routine using a pointer array are as follows:

  1. Create a pointer array with the same size as the original array
  2. Copy the elements of the original array to the pointer array
  3. Loop through the pointer array and compare adjacent elements
  4. If the elements are in the wrong order, swap them in the original array
  5. Continue looping until the array is sorted

What are the advantages of using a pointer array in a Bubble Sort routine?

Using a pointer array in a Bubble Sort routine can lead to faster performance and more efficient use of memory. This is because swapping elements in a pointer array does not require copying the entire element, but rather just changing the pointer to a different location in memory.

What are the limitations of using a Bubble Sort routine with a pointer array?

One limitation of using a Bubble Sort routine with a pointer array is that it can only be used for sorting data that can be accessed through a pointer. This means that it cannot be used for sorting data structures that do not support pointers, such as linked lists. Additionally, Bubble Sort has a time complexity of O(n^2), which can be inefficient for large datasets.

Similar threads

  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
29
Views
1K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
15
Views
1K
  • Programming and Computer Science
Replies
3
Views
702
  • Programming and Computer Science
Replies
23
Views
1K
  • Programming and Computer Science
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
713
  • Programming and Computer Science
Replies
7
Views
3K
  • Programming and Computer Science
Replies
22
Views
2K
Back
Top