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

Adak · 06-10-2009, 10:12 PM

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.

All your "Rube Goldberg" machinations, are just stopping/slowing your effort.

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.

itCbitC · 06-10-2009, 11:10 PM

Quote:

Originally Posted by badtwistofate

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++)
    ...

iMalc · 06-11-2009, 01:28 AM

Quote:

Originally Posted by badtwistofate

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.

iMalc · 06-11-2009, 01:38 AM

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.

itCbitC · 06-11-2009, 09:28 AM

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.

badtwistofate · 06-11-2009, 10:16 AM

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

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?

tabstop · 06-11-2009, 10:22 AM

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?

badtwistofate · 06-11-2009, 10:39 AM

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

itCbitC · 06-11-2009, 11:00 AM

Perhaps this

Code:

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

badtwistofate · 06-11-2009, 11:11 AM

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!

MK27 · 06-11-2009, 11:15 AM

Quote:

Originally Posted by badtwistofate

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...).

itCbitC · 06-11-2009, 11:27 AM

Quote:

Originally Posted by badtwistofate

Works for both cases now.

Thanks.

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

IMO the compare() function isn't needed and a simple numeric comparison between succesive values of t is sufficient, as in

Code:

/* 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])
      {
        ...

06-10-2009, 10:12 PM	#16
Adak Registered User Join Date: Sep 2006 Posts: 2,504	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. All your "Rube Goldberg" machinations, are just stopping/slowing your effort. 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.
Adak is offline

06-11-2009, 01:38 AM	#19
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,475	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. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

06-11-2009, 09:28 AM	#20
itCbitC Registered User Join Date: Oct 2008 Location: TX Posts: 1,262	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.
itCbitC is offline

06-11-2009, 10:22 AM	#22
tabstop and the Hat of Guessing Join Date: Nov 2007 Posts: 8,740	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?
tabstop is offline

06-11-2009, 11:00 AM	#24
itCbitC Registered User Join Date: Oct 2008 Location: TX Posts: 1,262	Perhaps this Code: /* second bin / for (i = (a+b-1); i >= a; i--) { for (j = (a + 1); j <= i; j++) { ... Last edited by itCbitC; 06-11-2009 at 11:29 AM. Reason: Tags*
itCbitC is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Problem with arrays structures sorting.	pitifulworm	C Programming	42	02-09-2009 12:31 PM
Homework problem...structures or arrays?	tortan	C++ Programming	21	08-30-2006 01:26 AM
problem with arrays and structures	gell10	C++ Programming	7	11-03-2003 12:02 AM
pointers to arrays of structures	terryrmcgowan	C Programming	1	06-25-2003 09:04 AM
Methods for Sorting Structures by Element...	Sebastiani	C Programming	9	09-14-2001 12:59 PM