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

This is a discussion on Sorting problem with structures and arrays, could I get some guidance? within the C Programming forums, part of the General Programming Boards category; When you say you want to "establish two bins", - that's where you've thrown a monkey wrench into the gears ...

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  2. #17
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by badtwistofate View Post
    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++)
        ...

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Quote Originally Posted by badtwistofate View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    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.

  6. #21
    Registered User
    Join Date
    Mar 2009
    Posts
    12
    Quote Originally Posted by brewbuck View Post
    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?
    Last edited by badtwistofate; 06-11-2009 at 10:31 AM.

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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?

  8. #23
    Registered User
    Join Date
    Mar 2009
    Posts
    12
    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
    Last edited by badtwistofate; 06-11-2009 at 10:43 AM.

  9. #24
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    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

  10. #25
    Registered User
    Join Date
    Mar 2009
    Posts
    12
    Quote Originally Posted by itCbitC View Post
    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!

  11. #26
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by badtwistofate View Post
    I think I will come away more knowledgeable from these posts!
    Yes.

    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...).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #27
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by badtwistofate View Post
    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])
          {
            ...

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

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

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21