How can i perform an insertion sort but check a property of the element in the array not just the element?

Question

Sorry, I'm sure this is simple but I'm tired and can't figure it out.

I have an array of elements, each element is in fact a particle which is a data structure (a struct in c) containing, among other things the particles current position (int x,y,z). I want to compare the elements x position not just the element itself.

Looking at the pseudocode on wikipedia, I've attempted to modify it to compare the attribute I want but I think I've done something (probably simple) wrong.

Here's what I've modified:

for (i = 1; i<length; i++) {
    value = particles[i].position.x;    
    j = i - 1;
    while (j >= 0 && particles[j].position.x > value) {
        particles[j+1] = particles[j];
        j = j - 1;
    }
    particles[j+1] = particles[i];
}

If someone could point out my mistake that would be great!

Adam

Answer 1

Your 2nd line acts to store a temporary copy of the ith element, because the while loop overwrites it. Yet in your 2nd last line you're reading from the overwritten value. Change your code to the following and it should work (changes commented):

for (i = 1; i<length; i++) {
    value = particles[i]; // store particles[i] rather than it's x coordinate
    j = i - 1;
    while (j >= 0 && particles[j].position.x > value.position.x) { // changed
        particles[j+1] = particles[j];
        j = j - 1;
    }
    particles[j+1] = value; // copy from temporary
}

Answer 2

You need to swap particle objects, not the values of the x coordinates. Try:

 for (i = 1; i<length; i++) {
    value = particles[ i ];
    /* ... */