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

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

Task: Sorting a array data set that I made a structure for.
Arrays are in x, y, z, time....

First I count the number of records of z that fall into two bins ( 0 < z < 100 and z > 100)

I then sort the data set for z in ascending order no problem. I use a structure and have swaps so that other data records (x, y, and time) stay with the z record.

Now the problem arises. I have sorted the data by z and now want to sort it further by time for just those two sections. What I mean is - if the first bin say collects 30 and second collects 10. Then I want it to sort the first 30 items in the array records by time and then sort the last 10 by time - so to keep the distinction of the two bins by z in tact (if that makes any sense). Tried multiple things and just can't get it to work.

Seems the first sort works fine - just using a bubble sort (don't hate - its a small data set). But can't get the rest to work.

Full code:
Code:
```#include <stdlib.h>
#include <stdio.h>

struct record
{
double *x;
double *y;
double *z;
double *t;
};

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;

int iii, jjj;
double temps;

int iiii, jjjj;
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 (iii = (a - 1); iii >= a; iii--)
{
for (jjj = 1; jjj <= iii; jjj++)
{
if (tmp.t[jjj-1] > tmp.t[jjj])
{
temp3 = tmp.t[jjj-1];
tmp.t[jjj-1] = tmp.t[jjj];
tmp.t[jjj] = temp3;

ss1 = tmp.x[jjj-1];
tmp.x[jjj-1] = tmp.x[jjj];
tmp.x[jjj] = ss1;

ss2 = tmp.y[jjj-1];
tmp.y[jjj-1] = tmp.y[jjj];
tmp.y[jjj] = ss2;

ss3 = tmp.z[jjj-1];
tmp.z[jjj-1] = tmp.z[jjj];
tmp.z[jjj] = ss3;

}
}
}

/* second bin */

for (iiii = (b - 1); iiii >= b; iiii--)
{
for (jjjj = a; jjjj <= iiii; jjjj++)
{
if (tmp.t[jjjj-1] > tmp.t[jjjj])
{

temps = tmp.t[jjjj-1];
tmp.t[jjjj-1] = tmp.t[jjjj];
tmp.t[jjj] = temps;

sss1 = tmp.x[jjj-1];
tmp.x[jjjj-1] = tmp.x[jjjj];
tmp.x[jjjj] = sss1;

sss2 = tmp.y[jjjj-1];
tmp.y[jjjj-1] = tmp.y[jjjj];
tmp.y[jjjj] = sss2;

sss3 = tmp.z[jjj-1];
tmp.z[jjjj-1] = tmp.z[jjjj];
tmp.z[jjjj] = sss3;

}
}
}

printf("Sorting complete \n");

fprintf(ofp,"Data Sorted");
fprintf(ofp,"The amount in each z bin:\n");
fprintf(ofp,"%d, %d\n", a, b);

for (iii = 0; iii < a; ++iii)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iii], tmp.x[iii],tmp.y[iii], tmp.z[iii]);

for (i = a; i < b-1; ++i)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iiii], tmp.x[iiii],tmp.y[iiii], tmp.z[iiii]);

free(tmp.x);
free(tmp.y);
free(tmp.z);
free(tmp.t);

fclose(ofp);

return 0;

}```
Troublesome part of the code
Code:
```/* first bin */

for (iii = (a - 1); iii >= a; iii--)
{
for (jjj = 1; jjj <= iii; jjj++)
{
if (tmp.t[jjj-1] > tmp.t[jjj])
{
temp3 = tmp.t[jjj-1];
tmp.t[jjj-1] = tmp.t[jjj];
tmp.t[jjj] = temp3;

ss1 = tmp.x[jjj-1];
tmp.x[jjj-1] = tmp.x[jjj];
tmp.x[jjj] = ss1;

ss2 = tmp.y[jjj-1];
tmp.y[jjj-1] = tmp.y[jjj];
tmp.y[jjj] = ss2;

ss3 = tmp.z[jjj-1];
tmp.z[jjj-1] = tmp.z[jjj];
tmp.z[jjj] = ss3;

}
}
}

/* second bin */

for (iiii = (b - 1); iiii >= b; iiii--)
{
for (jjjj = a; jjjj <= iiii; jjjj++)
{
if (tmp.t[jjjj-1] > tmp.t[jjjj])
{

temps = tmp.t[jjjj-1];
tmp.t[jjjj-1] = tmp.t[jjjj];
tmp.t[jjj] = temps;

sss1 = tmp.x[jjj-1];
tmp.x[jjjj-1] = tmp.x[jjjj];
tmp.x[jjjj] = sss1;

sss2 = tmp.y[jjjj-1];
tmp.y[jjjj-1] = tmp.y[jjjj];
tmp.y[jjjj] = sss2;

sss3 = tmp.z[jjj-1];
tmp.z[jjjj-1] = tmp.z[jjjj];
tmp.z[jjjj] = sss3;

}
}
}

printf("Sorting complete \n");

fprintf(ofp,"Data Sorted");
fprintf(ofp,"The amount in each z bin:\n");
fprintf(ofp,"%d, %d\n", a, b);

for (iii = 0; iii < a; ++iii)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iii], tmp.x[iii],tmp.y[iii], tmp.z[iii]);

for (i = a; i < b-1; ++i)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iiii], tmp.x[iiii],tmp.y[iiii], tmp.z[iiii]);```

2. I assume you want something like this:
Code:
```{ A, A, A }
{ A, A, B }
{ A, B, A }
{ A, B, B }
...```
Where it is first sorted by column 0, then by column 1, and optionally, by column 2. That being the case, consider:
Code:
```sort everything by just the first column
for each unique value in the first column
count how many have this value
copy that block off to another array
sort that array by its column of choice
copy that array back over top of the original array```
Quzah.

3. Code:
```/* first bin */

for (iii = (a - 1); iii >= 0; iii--)
{
for (jjj = 1; jjj <= iii; jjj++)
...```
same terminal condition for the 2nd bin

4. You want to sort by (z, time). In other words:

Code:
```int compare( int z1, int time1, int z2, int time2 )
{
if( z1 < z2 ) return -1;
if( z1 > z2 ) return 1;
if( time1 < time2 ) return -1;
if( time1 > time2 ) return 1;
return 0;
}```
Then do your sort using this comparison function.

5. This doesn't look right either:
Code:
```  for (i = a; i < b-1; ++i)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iiii], tmp.x[iiii],tmp.y[iiii], tmp.z[iiii]);```
You know you've got a problem when you've got four eyes, erm I mean four I's.
Why not just reuse 'i'?

6. Originally Posted by brewbuck
You want to sort by (z, time). In other words:

Code:
```int compare( int z1, int time1, int z2, int time2 )
{
if( z1 < z2 ) return -1;
if( z1 > z2 ) return 1;
if( time1 < time2 ) return -1;
if( time1 > time2 ) return 1;
return 0;
}```
Then do your sort using this comparison function.
How does this comparison function help the sorting process?

Should it work such that if, comparing the first bin, 1st time is larger and the second time is bigger it gives a value of 1 and then the bubble sort would then swap it?

I modified yours so the two if statements with z are not there.

Thus i fixed the code for the first and second bin such that now:
Code:
```  for (iii = (a - 1); iii >= a; iii--)
{
for (jjj = 1; jjj <= iii; jjj++)
{
if (compare(tmp.z[jjj-1], tmp.t[jjj-1], tmp.z[jjj], tmp.t[jjj]) == 1)
{
temp3 = tmp.t[jjj-1];
tmp.t[jjj-1] = tmp.t[jjj];
tmp.t[jjj] = temp3;

ss1 = tmp.x[jjj-1];
tmp.x[jjj-1] = tmp.x[jjj];
tmp.x[jjj] = ss1;

ss2 = tmp.y[jjj-1];
tmp.y[jjj-1] = tmp.y[jjj];
tmp.y[jjj] = ss2;

ss3 = tmp.z[jjj-1];
tmp.z[jjj-1] = tmp.z[jjj];
tmp.z[jjj] = ss3;

}
}
}

/* second bin */

for (iiii = (b - 1); iiii >= b; iiii--)
{
for (jjjj = a; jjjj <= iiii; jjjj++)
{
if (compare(tmp.z[jjjj-1], tmp.t[jjjj-1], tmp.z[jjjj], tmp.t[jjjj]) == 1)
{

temps = tmp.t[jjjj-1];
tmp.t[jjjj-1] = tmp.t[jjjj];
tmp.t[jjj] = temps;

sss1 = tmp.x[jjj-1];
tmp.x[jjjj-1] = tmp.x[jjjj];
tmp.x[jjjj] = sss1;

sss2 = tmp.y[jjjj-1];
tmp.y[jjjj-1] = tmp.y[jjjj];
tmp.y[jjjj] = sss2;

sss3 = tmp.z[jjj-1];
tmp.z[jjjj-1] = tmp.z[jjjj];
tmp.z[jjjj] = sss3;

}
}
}

printf("Sorting complete \n");

fprintf(ofp,"Data Sorted");
fprintf(ofp,"The amount in each z bin:\n");
fprintf(ofp,"%d, %d\n", a, b);
fprintf(ofp,"time, z, y, x \n");

for (iii = 0; iii < a; ++iii)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iii], tmp.z[iii],tmp.y[iii], tmp.x[iii]);

for (iiii = a; iiii < b-1; ++iiii)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iiii], tmp.z[iiii],tmp.y[iiii], tmp.x[iiii]);```
Suffice to say still not working the way I want haha
Note that the output still is off

Input:
Code:
```15,2,1,1
25,2,122,2
45,2,13,3
5,32,111,4
5,2,1,5
5,22,11,6
5,42,15,7
5,2,51,8
5,2,221,9
5,52,11,10```
Output:
Code:
```Data SortedThe amount in each z bin:
7, 3
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```
So it correctly sorts the elevation but what I want it to sort this time is just time... Note the first column of time still isn't in order and elevation is still in order (like the first sort did). Note still doesn't output the second bin of z's.

Any thoughts?

7. Originally Posted by iMalc
This doesn't look right either:
Code:
```  for (i = a; i < b-1; ++i)
fprintf(ofp,"%lf, %lf, %lf, %lf \n", tmp.t[iiii], tmp.x[iiii],tmp.y[iiii], tmp.z[iiii]);```
You know you've got a problem when you've got four eyes, erm I mean four I's.
Why not just reuse 'i'?
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...

8. Do you think that the outer loop will ever be executed given this (in red)?
Code:
`for (iii = (a - 1); iii >= a; iii--)`

9. Originally Posted by itCbitC
Do you think that the outer loop will ever be executed given this (in red)?
Code:
`for (iii = (a - 1); iii >= a; iii--)`
Hmm.. I guess not :0
Fixed the first bin sorting problem when the red term is set to zero ala the first sort done in the program.....

Seems the second bin sorting is not as forgiving. I have it printing now but it still is only sort by elevation hmmmm :-/

10. See my post #3

How does this comparison function help the sorting process?
You said you wanted to sort by z. Then, within each group of z, you wanted to sort by time. That's what this comparison function accomplishes. Unless I misunderstand what you are trying to do, this is correct.

You do not need to sort more than once.

Did you even try it?

12. Originally Posted by brewbuck
You said you wanted to sort by z. Then, within each group of z, you wanted to sort by time. That's what this comparison function accomplishes. Unless I misunderstand what you are trying to do, this is correct.

You do not need to sort more than once.

Did you even try it?
Yes i tried it. It didn't work right:
Code:
```Data SortedThe amount in each z bin:
7, 3
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```
This is my output. Z is sorted which I have done but it still doesnt sort by time for the two Z bin.

SO by trying this way:

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 = (b - 1); i >= 0; i--)
{
for (j = (a); 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");
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]);```
Reason for this way is I wanted the output to be like:
Code:
```Data SortedThe amount in each z bin:
7, 3
time, z, y, x
1.000000, 1.000000, 2.000000, 15.000000
3.000000, 13.000000, 2.000000, 45.000000
5.000000, 1.000000, 2.000000, 5.000000
6.000000, 11.000000, 22.000000, 5.000000
7.000000, 15.000000, 42.000000, 5.000000
8.000000, 51.000000, 2.000000, 5.000000
10.000000, 11.000000, 52.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```
Minus the second bin not being sorted by t

13. So why sort first with z and then sort with t? Just sort with t and you should be on your way, and the initial condition for 2nd bin should be (in red):
Code:
```for (i = (b - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
...```

14. Originally Posted by itCbitC
So why sort first with z and then sort with t? Just sort with t and you should be on your way, and the initial condition for 2nd bin should be (in red):
Code:
```for (i = (b - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
...```
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?

Yes i tried it. It didn't work right:
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.