# Sorting in Data Oriented Programming

One problem I ran into when writing a 3D program using DOP was sorting. In 3D you have to sort points based on their position from the camera so you can use a painter algorithm and draw things back to front so they occlude realistically. With C this is done using qsort() but qsort is really built around a more traditional object oriented mindset where you're sorting an array of struct pointers. When the data is split into multiple arrays of related data you can't just pick one array and sort it since that would leave the other arrays unsorted and the first element of the sorted array would no longer correspond to the first element of all the other arrays. What you're after isn't to just sort an array but instead how it's reordering applies to all the other arrays.

Let's say you want to sort objects based on one of their properties and you have an object defined by a struct like this:

```struct object {
double a;
bool b;
char c;
};
```

Then you have an array of pointers to a bunch of these object structs and you might want to find the c and b values of the object with the lowest a value.
Normally this is easy, you just call qsort() and tell it to sort your array of struct pointers based on the a member variable of those structs but what if instead of a struct containing a mix of a, b and c values you have three separate arrays containing groups of those values:

```double *a;
bool *b;
char *c;
```

The first object would consist of the first value from each of the three arrays, the fifth object would be a combination of the fifth value from the three arrays e.t.c.
You can't just feed qsort the array containing a values since it will just rearrange that array and the first object in it will no longer relate to the first object in the b and c arrays. So you won't know which b and c values belongs to the object with the lowest a value.
So if we have an array with the distance from the camera for all 3D points then just sorting that list is meaningless. What you want is to be able to tell all the other arrays that e.g. the eight element in them is the one closest to the camera.
This cannot be done with qsort, what it expects is that the relationship between values is encapsulated into a struct representing an object.

Surprisingly it turned out the solution to this was added in C11 so I guess I stand corrected for saying the C11 doesn't have any significant features. In it they added qsort_s which can take a void pointer to some "context" or additional data that qsort need access to. What I wanted to do was to take an int array of indices - say 0 to 99 if you had 100 objects - and then sort them based on some other array like one containing distances from the camera. You could then take your rearranged array of indices and use that to step through all the other arrays. However the ISO group made things difficult because qsort_s isn't in the actual C11 standard, instead it's in something called "Annex K". Apparently the C11 standard has multiple "annexes" which are features that are optional to implement.
Having optional parts of a standard would seem to be the complete opposite of what the intention of having standards usually is, which is to avoid fragmentation. Instead we've predictably gotten several incompatible implementations and some that do not want to implement it at all. In fact the only thing the different implementations appear to have in common is that none of them follow the standard. So much for standardization.

In order not to deal with this confusion I just grabbed a version of qsort with source code and modified it to accept another array in it's arguments. It's a good idea to compile your own version of qsort in C anyways in order to overcome some of it's limitation and get better performance.
The downside being that the implementation is written entirely using the preprocessor which certainly isn't the prettiest solution especially whey you get compiler errors. This is where the creakiness of C shows and it would have been nice to have a more modern language.

The way my modded qsort works is like this:

`QSORT_INDEX( type, data_array, index_array, array_size, comparison_function )`

type: The type of a single element in the data array. So for example could be int, double, char* e.t.c.
data_array: The name of the array which you want to sort by. In the above example this would be the a array.
index_array: An unsigned int array containing numbers 0 through N - 1 where N is the size of both data and index arrays.
array_size: The number of elements in both data and index arrays.
comparison_function: The name of a function doing the comparison that the arrays will be fed through. Needs to be defines as "static inline int function_name( const unsigned int*, const unsigned int*, type* )" where type is the same as above. Can only return 0 or 1.

The index array is used to pick values from the data array for use in the comparison. A regular comparison function for use with qsort might look something like this:

```int compare( const void *a, const void *b )
{
double firstValue = *( double* )a;
double secondValue = *( double* )b;

if( firstValue > secondValue ) return 1;
else return 0;
}
```

Where it takes two values, a and b and compares them and then rearranges the array that those a and b values came from based on the comparison. QSORT_INDEX might be something like this:

```int compare( const unsigned int *a, const unsigned int *b, const double *data )
{
double firstValue = data[ *a ];
double secondValue = data[ *b ];

if( firstValue > secondValue ) return 1;
else return 0;
}
```

Here a and b aren't themselves the values that should be compared. Instead they're integers representing indices in the data array. You pull values from the data array at these two indices and compare them. Then instead of rearranging the data array, QSORT_INDEX rearranges the index array that the a and b indices came from.
So for example if a = 5 and b = 7 then you pull values from data[ 5 ] and data[ 7 ] and compare them. If the value from index 7 is larger than at index 5 the index array will be reordered so that 7 comes before 5.

QSORT_INDEX will thus rearrange the index array but leave the data array as is.
Before the sort the index array could contain integers in numerical order so 0, 1, 2 ,3 e.t.c. representing the order of the objects in all three arrays a, b and c. After the sort the order of the indices in the array will reflect the sorting criterion. For example if you sorted based on lowest values in the a array and then after the sort have number 42 as the first number in the index array then that means that the object on the 42nd index position in arrays a, b and c is the one with the lowest a value.
And so the first value in the index array - index - is the object with the lowest a value and would in the above example be 42. index is the object with the second lowest a value and so on.
If we wanted to access the b value of the object with the lowest a value we could then write:

`b[ index[ 0 ] ];`

Clear as mud?
It's not as intuitive as a more traditional object oriented approach but it's the only way I can figure to sort things when using DOP.
Code and an example program can be found here.