# Sorting problem with structures and arrays, could I get some guidance?

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 06-10-2009
When you say you want to "establish two bins", - that's where you've thrown a monkey wrench into the gears of the machine.

What you want to do is a simple, multi-key sort - which computers have been doing since day 1 after they were sorting.

Try and strip the work down, into it's smallest necessary parts. It's all you need, and it's also all you should want.
• 06-10-2009
itCbitC
Quote:

why I sort with z and then sort with t is I first want to establish two bins. 1st bin is for z values 0 - 100 and second is 100 and greater. So I sort the whole thing for z and count the amount that fall into each bin. Then I resort the first bin for t and since I have the number that are in that bin make it sort only up to that point (the amount thats in a). Then I sort the 2nd half of the records (the ones that fall in the 2nd bin) for t. Does that make sense?

Example)

So if I have 10 x, y, z, t records

7 are in the first bin for z
3 in the second bin for z

Then I sort up to the 7th value for t, for the records that are in the first bin (7 of them)
sort the 8, 9, and 10th records for t, to account for all the records in the second bin (3 of them).

Does this clear what I am trying to accomplish?

Gotcha! so to accomplish this the "second bin" for loop needs to look like:
Code:

```for (i = (b - 1); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     ...```
• 06-11-2009
iMalc
Quote:

Noob question - I just was always under the assumption to not use a variable (like i) after using it earlier in the program. Upon looking at it since I am setting it to something with = it should be ok to do so. Also that tidbit you quoted had a error by myself- should have been (iiii = a; iiii < b-1; ++iiii) but its still bad practice...

I specifically quoted that part because of the fact that you were using a different variable for the indexing as was being altered in the loop.

There's nothing really weird or wrong about using a variable as a loop counter multiple times. 'i' can be always "the current loop's index" in a function, and it's usage is perfectly clear.
It would certainly be bad to use the same variable for completely different purposes in different places in the same function, of course. You wouldn't use the same variable as a loop counter, then an intermediate calculation result, then a flag, then to hold a dynamically allocated array length etc... (register allocation paranoia, perhaps)
But declaring a separate variable for each loop counter, up front, is almost as bad, when you name them like that, and this bug shows one of the reasons why, firsthand.
• 06-11-2009
iMalc
Just wondering... Why have you used a structure of arrays rather than an array of structures?

Switching to an array of structures would reduce the length of that program by at least 30 lines of code on its own.
• 06-11-2009
itCbitC
Consider moving the bubblesort code snippet into its own separate function.
It'll improve clarity as you won't need three or four i's and reduce the code size.
• 06-11-2009
Quote:

Originally Posted by brewbuck
Then you must have a bug in your sorting algorithm. Look more carefully at my comparison function.

For two elements with unequal z, the one with lower z will come first.

For two elements with EQUAL z, the one with lower t will come first.

Obviously, for a given z0, all elements where z <= z0 will come before elements where z > z0. We can then consider the groups z <= z0 and z > z0 independently. Within these groups, the same argument can be applied, until we have divided all the elements into groups with equal z.

Then, within these groups, it is obvious that the ordering will be by t.

This is nothing more than lexical ordering. An "alphabetic sort", where the first letter is the z value, and the second letter is the t value.

I know you comparison function is correct it just isn't working with the code... I'm really laughing at this point as I don't see a conceivable reason why it isn't work. The two bin sort code tidbits (bin 1 and bin 2) are nearly identical but the second bin will not sort time for some reason.

--------------------------

Here's my code at this point:
Code:

```#include <stdlib.h> #include <stdio.h> struct record {   double *x;   double *y;   double *z;   double *t; }; int compare( double z1, double time1, double z2, double time2 ) {     if( z1 < z2 ) return -1;     if( z1 > z2 ) return 1;     if( time1 < time2 ) return -1;     if( time1 > time2 ) return 1;     return 0; } int main(int argc, char *argv[]) {   FILE *ifp, *ofp;   ifp = fopen(argv[1], "r"); // Input data file   ofp = fopen(argv[2], "w"); // Output data file   int c; // counter   int a, b; // to store the number in the bins /* Used for sorting the data */   int i, j;   double temp;     double temps;     double temp3; /* z sorting */   double s1;   double s2;    double s3; /* 1st bin*/   double ss1;   double ss2;    double ss3; /* 2nd bin*/   double sss1;   double sss2;    double sss3; /* Structure */   struct record tmp; /* file formats to be read in */   double *x;   double *y;   double *z;   double *t;   const int max_el = 40; // Max array size   int al = 0; // Actual array length   int ap = 0; // array pointer /* Memory Allocation */   tmp.x = malloc(max_el * sizeof(double));   tmp.y = malloc(max_el * sizeof(double));   tmp.z = malloc(max_el * sizeof(double));   tmp.t = malloc(max_el * sizeof(double));   while(!feof(ifp)) {     al = al + 1;     fscanf(ifp, "%lf,%lf,%lf,%lf\n",                 &tmp.x[ap], &tmp.y[ap], &tmp.z[ap],                 &tmp.t[ap]);     ap = ap + 1;   }   fclose(ifp); a = 0; /* Initialize the counters */ b = 0; /* z bin counting */   for (c = 0; c < al; c++) {           if ((tmp.z[c] >= 0.0)&&(tmp.z[c] <= 100))                         a += 1;         else if (tmp.z[c] > 100)                         b += 1;   } /***********************************************/ /* Bubble Sort to sort the data by z */   for (i = (al - 1); i >= 0; i--)   {     for (j = 1; j <= i; j++)     {       if (tmp.z[j-1] > tmp.z[j])       {         temp = tmp.z[j-1];         tmp.z[j-1] = tmp.z[j];         tmp.z[j] = temp;         s1 = tmp.x[j-1];         tmp.x[j-1] = tmp.x[j];         tmp.x[j] = s1;         s2 = tmp.y[j-1];         tmp.y[j-1] = tmp.y[j];         tmp.y[j] = s2;         s3 = tmp.t[j-1];         tmp.t[j-1] = tmp.t[j];         tmp.t[j] = s3;       }     }   } /***************************************/ /* first bin */   for (i = (a - 1); i >= 0; i--)   {     for (j = 1; j <= i; j++)     {       if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)       {         temp3 = tmp.t[j-1];         tmp.t[j-1] = tmp.t[j];         tmp.t[j] = temp3;         ss1 = tmp.x[j-1];         tmp.x[j-1] = tmp.x[j];         tmp.x[j] = ss1;         ss2 = tmp.y[j-1];         tmp.y[j-1] = tmp.y[j];         tmp.y[j] = ss2;         ss3 = tmp.z[j-1];         tmp.z[j-1] = tmp.z[j];         tmp.z[j] = ss3;       }     }   } /* second bin */     for (i = (b - 1); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     {       if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)       {         temps = tmp.t[j-1];         tmp.t[j-1] = tmp.t[j];         tmp.t[j] = temps;         sss1 = tmp.x[j-1];         tmp.x[j-1] = tmp.x[j];         tmp.x[j] = sss1;         sss2 = tmp.y[j-1];         tmp.y[j-1] = tmp.y[j];         tmp.y[j] = sss2;         sss3 = tmp.z[j-1];         tmp.z[j-1] = tmp.z[j];         tmp.z[j] = sss3;       }     }   }   printf("Sorting complete \n");   fprintf(ofp,"Data Sorted\n");   fprintf(ofp,"The amount in each z bin:\n");   fprintf(ofp,"%d, %d\n", a, b);   fprintf(ofp,"time, z, y, x \n");     for (i = 0; i < a; ++i)     fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[i], tmp.z[i],tmp.y[i], tmp.x[i]);     fprintf(ofp,"***************\n");   for (i = a; i < al; ++i)     fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[i], tmp.z[i],tmp.y[i], tmp.x[i]);   free(tmp.x);   free(tmp.y);   free(tmp.z);   free(tmp.t);   fclose(ofp);   return 0; }```
produces output:
Code:

```time, z, y, x 1.000000, 1.000000, 2.000000, 15.000000 5.000000, 1.000000, 2.000000, 5.000000 6.000000, 11.000000, 22.000000, 5.000000 10.000000, 11.000000, 52.000000, 5.000000 3.000000, 13.000000, 2.000000, 45.000000 7.000000, 15.000000, 42.000000, 5.000000 8.000000, 51.000000, 2.000000, 5.000000 *************** 4.000000, 111.000000, 32.000000, 5.000000 2.000000, 122.000000, 2.000000, 25.000000 9.000000, 221.000000, 2.000000, 5.000000```
still gives me the 2nd bin not sorted correctly :confused:

Pretty confident right now the problem lies in the condition statements for the 2nd bins sorting:
IE
Code:

```/* second bin */     for (i = (b - 1); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     {```
As in this case: A count was 7 and B count was 3... the first condition wont decrease if the 2nd elevation bin (which is the b count) has less number of records then the first bin (the a count)

Looking to see if there's way to say, directly for the array records, that after the 7 array record resort again for t?
• 06-11-2009
tabstop
Code:

`if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)`
Code:

`if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)`
I would expect these to do the exact same thing. If you want the second one to sort by t before z, shouldn't you swap t and z around?
• 06-11-2009
THINK I FIXED IT!!
Code:

``` /* first bin */   for (i = (a - 1); i >= 0; i--)   {     for (j = 1; j <= i; j++)     {       if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)       {         temp3 = tmp.t[j-1];         tmp.t[j-1] = tmp.t[j];         tmp.t[j] = temp3;         ss1 = tmp.x[j-1];         tmp.x[j-1] = tmp.x[j];         tmp.x[j] = ss1;         ss2 = tmp.y[j-1];         tmp.y[j-1] = tmp.y[j];         tmp.y[j] = ss2;         ss3 = tmp.z[j-1];         tmp.z[j-1] = tmp.z[j];         tmp.z[j] = ss3;       }     }   } /* second bin */     for (i = (a + b); i >= b; i--)   {     for (j = (a + 1); j <= i; j++)     {       if (compare(tmp.z[j-1], tmp.t[j-1], tmp.z[j], tmp.t[j]) == 1)       {         temps = tmp.t[j-1];         tmp.t[j-1] = tmp.t[j];         tmp.t[j] = temps;         sss1 = tmp.x[j-1];         tmp.x[j-1] = tmp.x[j];         tmp.x[j] = sss1;         sss2 = tmp.y[j-1];         tmp.y[j-1] = tmp.y[j];         tmp.y[j] = sss2;         sss3 = tmp.z[j-1];         tmp.z[j-1] = tmp.z[j];         tmp.z[j] = sss3;       }     }   }   printf("Sorting complete \n");   fprintf(ofp,"Data Sorted\n");   fprintf(ofp,"The amount in each z bin:\n");   fprintf(ofp,"%d, %d\n", a, b);   fprintf(ofp,"time, z, y, x \n");     for (i = 0; i < a; ++i)     fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[i], tmp.z[i],tmp.y[i], tmp.x[i]);     fprintf(ofp,"***************\n");   for (i = a + 1; i <= al; ++i)     fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[i], tmp.z[i],tmp.y[i], tmp.x[i]);```
Does that make sense what I did? Because it looked like before (in the second bin sort)
Code:

```  for (i = (b - 1); i >= b; i--)   {     for (j = (a + 1); j <= i; j++)```
It would never satisfy the first condition if the amount in 2nd bin was less then the first bin.

so by changing it so:
Code:

```for (i = (a + b); i >= b; i--)   {     for (j = (a + 1); j <= i; j++)```
IT would now sort the 2nd bin.

BUT... Now i tested that if the 1st bin has less amount then the 2nd bin it fails... YUCK
• 06-11-2009
itCbitC
Perhaps this
Code:

```/* second bin */     for (i = (a+b-1); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     {       ...```
• 06-11-2009
Quote:

Originally Posted by itCbitC
Perhaps this
Code:

```/* second bin */     for (i = (a+b); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     {       ...```

Works for both cases now.

Thanks. :)

I think I will come away more knowledgeable from these posts!
• 06-11-2009
MK27
Quote:

I think I will come away more knowledgeable from these posts!

Yes.

Quote:

I'm really laughing at this point as I don't see a conceivable reason why it isn't work.
After doing that about ten thousand times, it will stop seeming interesting or amusing and you will gain an insight into your "blind spots" (they probably contain a conceivable reason...).
• 06-11-2009
itCbitC
Quote:

```/* first bin */   for (i = (a - 1); i >= 0; i--)   {     for (j = 1; j <= i; j++)     {       if (tmp.t[j-1] > tmp.t[j])       {         ...       /* second bin */   for (i = (a + b - 1); i >= a; i--)   {     for (j = (a + 1); j <= i; j++)     {       if (tmp.t[j-1] > tmp.t[j])       {         ...```