Question 3 of 9: Programming — Line Reversal and Three-Way Sorting

Question 3: Programming — Line Reversal and Three-Way Sorting (20 marks: (a) 10, (b) 10)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. For (a), lines typed at a terminal, the session ending on an empty line, with three worked examples of the required output format. For (b), twenty coordinate pairs to be presented in three different orders.

Find. Two programs: one that echoes each line reversed until an empty line arrives; one that reads twenty points and prints them sorted by increasing $x$, by decreasing $y$, and by increasing distance from the origin.

Approach. Read whole lines with fgets, strip the newline, and walk the string backwards with an index; for the sorting, define one comparator per criterion and call the library qsort three times.

(a) Printing lines backwards (10 marks)

1. Choose a line-oriented read, not a word-oriented one. scanf("%s", ...) stops at the first space, so “Computer programming is fun.” would arrive as four separate tokens and the spaces would be lost. fgets takes the whole line including its terminating newline, and bounds the read to the buffer size, which gets famously does not.
2. Distinguish an empty line from end of input. After fgets succeeds, the newline is still in the buffer, so a bare carriage return arrives as the two-character string containing only a newline. Overwriting that newline with a terminator — line[strcspn(line, "\n")] = '\0'; — turns it into the empty string, which is then the loop's stopping condition. A NULL return means the input stream itself ended, which must also stop the loop.
3. Reverse by index rather than in place. Because the line is only printed, not stored, walking the index from $\texttt{strlen(line)} - 1$ down to 0 and emitting one character at a time is simpler and cheaper than swapping characters: $$\boxed{\text{output}[k] = \text{line}[\,n-1-k\,], \quad k = 0,\dots,n-1}$$

   #include <stdio.h>
   #include <string.h>
   
   #define MAXLINE 1024
   
   int main(void)
   {
       char line[MAXLINE];
       int i;
   
       for (;;) {
           printf("enter a line of text: ");
   
           if (fgets(line, sizeof line, stdin) == NULL)
               break;                              /* end of input */
   
           line[strcspn(line, "\n")] = '\0';       /* drop the newline fgets kept */
   
           if (line[0] == '\0')                    /* an empty line ends the run */
               break;
   
           printf("the reversed line is: ");
           for (i = (int)strlen(line) - 1; i >= 0; i--)
               putchar(line[i]);
           putchar('\n');
       }
       return 0;
   }

4. Confirm against the printed session. The three examples reproduce exactly: “Computer programming is fun.” reverses to “.nuf si gnimmargorp retupmoC” (note that the full stop leads, which is the usual check that the terminator was stripped and the punctuation was not); “CN Tower” gives “rewoT NC”; and “hello” gives “olleh”. The fourth prompt receives an empty line and the program stops.

(b) Three orderings of twenty points (10 marks)

1. Store the pairs as one array of structures, not two arrays. A point is one object with two fields; keeping x and y in parallel arrays would require every sort to permute both arrays in step, which is where such programs usually go wrong. One Point array lets the library move whole points.
2. Write one comparator per criterion. The three orderings differ only in the key, so the sorting logic is written once and supplied three different comparison functions. Descending order needs no separate machinery — simply subtract in the other direction.
3. Compare squared distances, not distances. Since $t \mapsto \sqrt{t}$ is strictly increasing on $t \ge 0$, $$x_{1}^{2}+y_{1}^{2} \;<\; x_{2}^{2}+y_{2}^{2} \iff \sqrt{x_{1}^{2}+y_{1}^{2}} \;<\; \sqrt{x_{2}^{2}+y_{2}^{2}}$$ $$\boxed{\text{sorting on } x^{2}+y^{2} \text{ gives the same order as sorting on } \sqrt{x^{2}+y^{2}}}$$ so the square root can be dropped: it costs time, and it introduces rounding that can make two genuinely distinct points compare equal.
4. Return the sign of the difference, never the difference. The classic defect in a qsort comparator on floating-point data is return (int)(a-b);, which truncates every difference of magnitude less than 1 to zero and reports unequal points as equal. The idiom (d > 0) - (d < 0) yields exactly −1, 0 or +1.

   #include <stdio.h>
   #include <stdlib.h>
   
   #define N 20
   
   typedef struct { double x, y; } Point;
   
   static Point pts[N];
   
   /* Comparators return the SIGN of a difference. Never write
      "return (int)(a->x - b->x);" -- truncation makes 0.5 compare equal to 0. */
   static int cmp_x_asc(const void *a, const void *b)
   {
       double d = ((const Point *)a)->x - ((const Point *)b)->x;
       return (d > 0) - (d < 0);
   }
   
   static int cmp_y_desc(const void *a, const void *b)
   {
       double d = ((const Point *)b)->y - ((const Point *)a)->y;   /* b - a: descending */
       return (d > 0) - (d < 0);
   }
   
   static double dist2(const Point *p) { return p->x * p->x + p->y * p->y; }
   
   static int cmp_dist_asc(const void *a, const void *b)
   {
       double d = dist2((const Point *)a) - dist2((const Point *)b);
       return (d > 0) - (d < 0);
   }
   
   static void show(const char *heading)
   {
       int i;
       printf("%s\n", heading);
       for (i = 0; i < N; i++)
           printf("  (%g, %g)\n", pts[i].x, pts[i].y);
   }
   
   int main(void)
   {
       int i;
   
       for (i = 0; i < N; i++)
           if (scanf("%lf %lf", &pts[i].x, &pts[i].y) != 2) {
               fprintf(stderr, "expected %d coordinate pairs\n", N);
               return 1;
           }
   
       qsort(pts, N, sizeof pts[0], cmp_x_asc);
       show("i.   increasing x");
   
       qsort(pts, N, sizeof pts[0], cmp_y_desc);
       show("ii.  decreasing y");
   
       qsort(pts, N, sizeof pts[0], cmp_dist_asc);
       show("iii. increasing distance from the origin");
   
       return 0;
   }

5. Demonstrate on a reduced set. Eight of the twenty points are enough to show the three orders differ completely; the program itself reads all twenty. With $P_1(3,4)$, $P_2(-6,8)$, $P_3(1,-1)$, $P_4(0,7)$, $P_5(-2,-3)$, $P_6(9,2)$, $P_7(4,-8)$, $P_8(-5,1)$ the results are those in the table below. Sorting is $O(n \log n)$ per criterion, so all three together remain $O(n \log n)$.