How does this sorting function work?

Question

As part of my work, I am sometimes attracted to evaluate candidates for position programming. Recently, a piece of code passed through my desk, and my first thoughts were that I was not sure that such code would even compile. But compile it and it also works.

Can someone explain why and how it 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 see the drawbacks of this approach (lack of readability and maintainability for those born after 1970), but can anyone think of any advantages? I do not dare to dismiss him from control, but before we decide whether to return this person to round 2, I would like to know if he has any functions to protect the author from the safety of his work.

Answer 1

This is a fully expanded view of the bubble with the XOR-swap trick expressed inline. I compiled it with several different options, hoping that it will release some amazing compact code, but it really is not that impressive. I put a few __restrict__ keywords so that the compiler knows that none of *a can use each other's aliases, which helps a lot. In general, however, I think the attempt at the skill has gone so far beyond the norm that the compiler does not really optimize the code very well.

I think the only advantage here is the novelty. It surely got your attention! I would be more impressed with the abuses of more modern technologies, such as sorting with MMX / SSE or GPU or using 5 threads that all struggle to try to insert their elements in the right place. Or, perhaps, the look of the merge, just in case the array of 5 elements cannot fit in the kernel.

Answer 2

xor trick simply replaces two integers. Goto - imitation of a cycle. Benefits? Nothing but to show how the code you can write is tangled. The parameter after function () is an obsolete function. And having an array at hand and havong 5 different pointers pointing to each element of the array is just awful. To summarize: Yuck! :)

Answer 3

This is a comic Gnome sort implementation for five elements.

Here's how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the Previous; if they are in the right order him to make one pot forward, otherwise he changes them and takes steps one pot back. Boundary conditions: if there is no previous bank, it steps forward; if he is not nearby, he is made.

“One Step Bank Step Forward” is performed by moving to the next if . goto immediately after each XOR-swap makes "step by step one bank back".

Answer 4

You cannot fire someone out of control of such an answer. Perhaps he was provided with tongue in his cheek.

The question is very artificial, causing far-fetched answers.

You need to find out how the candidate will solve more real problems.

Answer 5

lack of readability and maintainability for those born after 1970

Do people born before 1970 know better to support unreadable code? If so, it’s good because I was, and this can only be a selling point.

before we decide whether to return this person to round 2, I would like to know if he has any features to redeem beyond the safety of the author.

There is no one ransom function s in the code. This bizarrely uses the xor exchange technique, the only possible buyback function of which would be to save the integer value of the stack. However, even this is negated with five pointers and an unused int. It also has free use of the comma operator.

I usually also say "goto, yuck", but in this case it was used quite elegantly as soon as you understand the sorting algorithm used. In fact, you can argue that it makes the gnome sorting algorithm more understandable than using an index variable (except that it cannot be generalized to n elements). So you have the temptation function, it makes goo look good :)

As for "you are returning the candidate for the second interview." If the code fragment was accompanied by a detailed commentary explaining how the algorithm works and the author’s motivation for using it, I would definitely say yes. If not, I would probably call him and ask these questions.

NB, the code snippet uses K & R style parameter declarations. This means that the author is probably not programmed in C for 10-15 years, or he copied it from the Internet.