Sorting a List of Marks in the Least Number of Lines

[HRI]

A *long* while back we had a competition to see who could write a program to sort an entered list of marks and output the median. Another student and I tied at 11 lines that were crucial to the program running. A few days ago, I found out that I could reduce where I swap two numbers from three lines to one using ^= (assuming they're not equal). The problem is that most of the numbers turn to 0. Debugging, I found that when it compares the marks 33 and 38 to start off with, 38 turns to 33 and 33 turns to 0. Taking 33 and 38 and making a different program with a and b set to those values, the swap worked perfectly fine!

c++:

// Calculates the median of given marks #include <iostream> // necessary for I/O // 1 #include <cstdio> // used for freopen if using files //#define screen // switches from screen I/O to file I/O int main() // main function // 2 {     int marks[100000], i = 0; // create array and variable to keep track of size and inputs // 3     #ifndef screen // if using files     freopen ("marks.TXT", "r", stdin); // open file for reading     #endif     while (     #ifdef screen // output prompt if using screen I/O     (std::cout << "Enter mark (EOF to exit): ") &&     #endif     (std::cin >> marks [i++])); // until EOF, fill array // 4     for (int j = 0; j <= i - 2; j++) // go through whole array beginning to end // 5     {         for (int k = i - 2; k > j; k--) // go from end of array to current place in above loop // 6         {             if (marks [k - 1] > marks [k]) // if marks are not sorted // 7             {                     // swap marks                     marks [k] ^= marks [k - 1] ^= marks [k] ^= marks [k - 1]; // 8 <--------PROBLEM ONLY WHEN USING THE ARRAY, NOT INDIVIDUAL VARIABLES WITH THE SAME VALUES             } // end if         } // end for     } // end for     #ifndef screen // if using files (outputting sorted marks was not included in assignment, only the median)     freopen ("sortedMarks.TXT", "w", stdout); // open file for writing     for (int j = 0; j <= i - 2; j++) // go through whole array left to right         std::cout << marks [j] << '\n'; // output sorted marks     freopen ("median.TXT", "w", stdout); // open new file for writing     #endif     // output median     ((i - 1) % 2 == 1) ? std::cout << // not counted as line, continues     #ifdef screen     "The median is " <<     #endif     marks [(i - 1) / 2] << '\n' : std::cout << // still continues     #ifdef screen     "The median is " <<     #endif     (double (marks [(i - 1) / 2 - 1]) + double (marks [(i - 1) / 2])) / 2 << '\n'; // 9 // outputs the correct median (whether odd or even number of marks)     #ifdef screen     system ("pause"); // pause for key press if using screen I/O     #endif } // end main

To assure you, I made sure the marks were all different, but it doesn't matter as the first swap (33 and 38) is not working, even though the exact same thing works in a new program :/

[DemonWasp]

You're abusing what's called "undefined behaviour" there, which means that your C++ compiler can output whatever it wants for that bit of code.

When you're compiling with just some (non-array) variables, it probably keeps both variables in registers, which results in the correct calculation. However, when you introduce the array, it will store values to temporary registers, resulting in an extra read from the array with a "stale" value and some assignments from those temporary registers back to the array, with "incorrect" results.

This link starts off talking about Java, but there's some info on this exact construct in C++: http://stackoverflow.com/questions/3844934/why-is-this-statement-not-working-in-java-x-y-x-y

[HRI]

Thanks, I never would have guessed that. It helps a lot. Making it into two statements would help with the same variable being modified twice in one statement, and would still be one line less than before :3 Any idea if that would work?

[DemonWasp]

The kind of undefined behaviour you're running into is typified by the pattern where you have multiple store-operations on the same line, and the value stored is reused in another calculation.

The correct way to do it is:

code:

x ^= y; y ^= x; x ^= y;

This requires three assignments, and the value of the first two are re-used on the very next calculation. There is no more line-compact way to express this correctly, as far as I can tell.

[HRI]

That makes more sense now that I think about it Thanks for the help.