How does this sort function work?

As part of my job, I'm occasionally called upon to evaluate candidates for programming positions. A code snipp开发者_运维百科et recently passed across my desk and my first thoughts were that I wasn't sure code like this would even compile any more. But compile it does, and it works as well.

Can anyone explain why and how this works? The mandate was to provide a function to sort five integer values.

void order5(arr) int *arr; {
    int i,*a,*b,*c,*d,*e;
    a=arr,b=arr+1,c=arr+2,d=arr+3,e=arr+4;
    L1: if(*a >*b){*a^=*b;*b^=*a;*a^=*b;}
    L2: if(*b >*c){*b^=*c;*c^=*b;*b^=*c;goto L1;}
    L3: if(*c >*d){*c^=*d;*d^=*c;*c^=*d;goto L2;}
        if(*d >*e){*d^=*e;*e^=*d;*d^=*e;goto L3;}
}

Now I can see the disadvantages of this approach (lack of readability and maintainability for anyone born after 1970) but can anyone think of any advantages? I'm hesitant to dismiss it out of hand but, before we decide whether or not to bring this person back in for round 2, I'd like to know if it has any redeeming features beyond job security for the author.

It's a fully unrolled bubble sort with the XOR-swap trick expressed inline. I compiled it with several different options hoping it produced some awesome compact code, but it's really not that impressive. I threw in some __restrict__ keywords so that the compiler would know that none of the *a could alias each other, which does help quite a bit. Overall though, I think the attempted cleverness has gone so far outside the norm that the compiler is really not optimizing the code very well at all.

I think the only advantage here is novelty. It certainly caught your eye! I would have been more impressed with abuses of more modern technology, like sorting with MMX/SSE or the GPU, or using 5 threads which all fight it out to try to insert their elements into the right place. Or perhaps an external merge sort, just in case the 5 element array can't fit in core.

The xor trick just swaps two integers. The goto's are the imitation of the loop. Advantages? None at all except for showing off how obfuscated a code you can write. The parameter after function () is a deprecated feature. And having an array on hand and havong 5 distinct pointers pointing at each elem of the array is just horrible. To sum it up: Yuck! :)

It's a screwy implementation of Gnome sort for five items.

Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

The "stepping one pot forward" is done by falling through to the next if. The goto immediately after each XOR-swap does the "stepping one pot backwards."

You can't dismiss someone out of hand for an answer like this. It might have been provided tongue-in-cheek.

The question is highly artificial, prompting contrived answers.

You need to find out how the candidate would solve more real-world problems.

lack of readability and maintainability for anyone born after 1970

Are people born before 1970 better at maintaining unreadable code then? If so, that's good because I was and it can only be a selling point.

before we decide whether or not to bring this person back in for round 2, I'd like to know if it has any redeeming features beyond job security for the author.

The code has no one redeeming features. It bizarrely uses the xor swap technique whose only potential redeeming feature would be saving oner integer's worth of stack space. However, even that is negated by the five pointers defined and the unused int. It also has a gratuitous use of the comma operator.

Normally, I'd also say "goto, yuck", but in this case, it has been used in quite an elegant way, once you understand the sort algorithm used. In fact, you could argue that it makes the gnome sort algorithm clearer than using an index variable (except it cannot be generalised to n elements). So there you have the redeeming feature, it makes goto look good :)

As for "do you bring the candidate back for the second interview". If the code fragment was accompanied by a detailed comment explaining how the algorithm worked and the writer's motivation for using it, I'd say definitely yes. If not, I'd probably ring him up and ask those questions.

NB, the code fragment uses K&R style parameter declarations. This means the author probably hasn't programmed in C for 10 to 15 years or he copied it off the Internet.