Draineh Draineh - 2 days ago 6
C Question

Recursion in C - Bubble sort?

Apologies in advance for the amount of code at the end, because there is a bit I Will leave it until last.
I am reading some variables into a struct, and I want to re-order these so the number closest to 0 is at the top (they are all minus values as they are decibel readings).
If I remember my stuff correctly I think I may have done a bubble sort (or some horrible attempt of)
Anyway, I decided that I should have a go at solving this with recursion, I can think of 2 or 3 ways to do this with maybe more code but less of a headache but I had a go, and it works!

However... everything sorts perfectly but I am left with a random duplicate at the end.. I have 10 nodes, nodes[0] to nodes[9]. I deliberately declare everything after and including 5 as null simply as a test that it will stop if it doesn't have a full 10 entries.
My printf's indicate that it stops, yet I end up with one of my 5 values being duplicated into nodes[9]?

I'm quite tired so it may be staring me in the face but I really can't understand how this is happening. Any hints/tips would be appreciated. Also any observations about bad practice or ways to improve the efficiency of my code would not be frowned on!

Don't worry about the hard coded values or global variables, it is for an embedded device and the struct will be populated by another function. Also, I have left all print statements for debugging in the below code for anyone that tries to give it a quick compile.

Thanks

#define MAX_NAME_SIZE 16
#define MAX_RSSI_SIZE 5

struct route_data
{
char* ssid;

int rssi;
};

struct route_data nodes[9];
struct route_data temp;


void main(){
nodes[0].ssid = "N1";
nodes[0].rssi = -20;
nodes[1].ssid = "N2";
nodes[1].rssi = -40;
nodes[2].ssid = "N3";
nodes[2].rssi = -34;
nodes[3].ssid = "N4";
nodes[3].rssi = -27;
nodes[4].ssid = "N5";
nodes[4].rssi = -80;

nodes[5].ssid = "NULL";
nodes[6].ssid = "NULL";
nodes[7].ssid = "NULL";
nodes[8].ssid = "NULL";
nodes[9].ssid = "NULL";

int y =0;

while(y!=10){
printf("Node[%d] -\n\t%s\t %d\n\n",y,nodes[y].ssid, nodes[y].rssi);
y++;
}

chooseBest(0,1);

y=0;

while(y!=10){
printf("Node[%d] -\n\t%s\t %d\n\n",y,nodes[y].ssid, nodes[y].rssi);
y++;
}

}

int chooseBest(int x, int i){

//No point comparing the same values, increment up
if(x==i){
printf("X and I match - x %d\t i %d\n\n",x,i);
i++;
chooseBest(x,i);
}
//if X is less than I, and I is not null, check if i is greater than x and then swap
else if((nodes[x].rssi<nodes[i].rssi)&&(nodes[i].rssi!=0)){
printf("\nNode X Rssi %d\t Node I Rssi %d\n",nodes[x].rssi,nodes[i].rssi);
printf("Node[X] is smaller than I - i %d\n",i);
printf("X - %d\tI - %d\n\n",x,i);
if(i>x){
if(i!=0){
temp.ssid = nodes[x].ssid;
temp.rssi = nodes[x].rssi;

nodes[x].ssid = nodes[i].ssid;
nodes[x].rssi = nodes[i].rssi;

nodes[i].ssid = temp.ssid;
nodes[i].rssi = temp.rssi;
}
}
i++;
chooseBest(x,i);
}
//Is X greater than I and X is not null? If so, is X greater than I. Swap values
else if((nodes[x].rssi>nodes[i].rssi)&&(nodes[x].rssi!=0)){
printf("Node[X] is bigger\n");
printf("X - %d\tI - %d\n\n",x,i);
if(x>i)
{
temp.ssid = nodes[x].ssid;
temp.rssi = nodes[x].rssi;

nodes[x].ssid = nodes[i].ssid;
nodes[x].rssi = nodes[i].rssi;

nodes[i].ssid = temp.ssid;
nodes[i].rssi = temp.rssi;

}
i++;
chooseBest(x,i);
}
else{
//If X is null we have traversed all values
if(nodes[x].rssi==0){
printf("Nodes[x] equals null\n");
printf("X - %d\tI - %d\n\n",x,i);
return 0;
}
//Otherwise, we have reached the end of I and need to increment X and reset I
else{
printf("About to increment X\n");
printf("X - %d\tI - %d\n\n",x,i);
x++;
i=0;
chooseBest(x,i);
//printf("End of the line\n");
}

}

Answer

You've only allocated 9 nodes, and you're using 10. That could very well lead to problems.

Comments