File I/O — Names Common to Three Sorted Files: 25-Comp-A4 Program Design and Data Structures, May 2016, Q6

Question 6: File I/O — Names Common to Three Sorted Files (20 marks)

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. Three text files, each already sorted alphabetically, one name per line in Last, First format, of unknown and possibly differing length.

Find. A program that prints exactly the names appearing in all three files.

Approach. Since all three files are already sorted, a single synchronized three-pointer scan (analogous to a 3-way merge) finds the intersection in one pass over all three files combined — no need to load any file fully into memory, and no need to sort anything, since sorting has already been done for us.

Generalize two-way merge-intersection to three files. At each step, look at the current line of all three files. If all three are equal, that name is common to all three — print it and advance all three files. Otherwise, whichever file(s) hold the alphabetically smallest current line cannot possibly match the other two (since all files are sorted ascending, that name will never recur later in the other files), so only those file(s) advance.

Write the program. A fixed-size line buffer is sufficient since names are short; strcmp gives the needed lexicographic ordering directly on the "Last, First" strings.

#include <stdio.h>
#include <string.h>

#define LINE_LEN 128

/* Reads one line, stripping the trailing newline. Returns 0 at EOF. */
int readLine(FILE *fp, char *buf)
{
    if (fgets(buf, LINE_LEN, fp) == NULL)
        return 0;
    buf[strcspn(buf, "\n")] = '\0';
    return 1;
}

int main(void)
{
    char nameA[LINE_LEN], nameB[LINE_LEN], nameC[LINE_LEN];
    char fa[100], fb[100], fc[100];
    FILE *A, *B, *C;

    printf("Enter the three file names: ");
    scanf("%99s %99s %99s", fa, fb, fc);
    A = fopen(fa, "r");  B = fopen(fb, "r");  C = fopen(fc, "r");
    if (!A || !B || !C) { printf("Could not open all three files.\n"); return 1; }

    int haveA = readLine(A, nameA);
    int haveB = readLine(B, nameB);
    int haveC = readLine(C, nameC);

    while (haveA && haveB && haveC) {
        int ab = strcmp(nameA, nameB);
        int bc = strcmp(nameB, nameC);
        int ac = strcmp(nameA, nameC);

        if (ab == 0 && bc == 0) {          /* all three equal */
            printf("%s\n", nameA);
            haveA = readLine(A, nameA);
            haveB = readLine(B, nameB);
            haveC = readLine(C, nameC);
        } else {
            /* advance every file tied for the SMALLEST current line -- that
               name can never reappear later in the other two files */
            if (ab <= 0 && ac <= 0) haveA = readLine(A, nameA);
            if (ab >= 0 && bc <= 0) haveB = readLine(B, nameB);
            if (ac >= 0 && bc >= 0) haveC = readLine(C, nameC);
        }
    }

    fclose(A); fclose(B); fclose(C);
    return 0;
}

The advance rule keeps whichever file(s) already hold the current largest line untouched, and steps every file tied for smallest — which is what correctly handles a three-way tie between exactly two of the files without either stalling or over-advancing.

Confirm on a worked example. With advisors = {Adams,Ray; Chen,Amy; Diaz,Ivy; Ng,Tom; Ortiz,Bea}, traders = {Chen,Amy; Diaz,Ivy; Kim,Sam; Ortiz,Bea; Zong,Uma}, rolodex = {Bell,Uri; Chen,Amy; Ortiz,Bea; Ortiz,Cid; Ryan,Max}, the synchronized scan reports exactly the two names present in all three lists. $$\boxed{\text{common names} = \{\text{Chen, Amy};\ \text{Ortiz, Bea}\}}$$

Question 6 — results
Quantity	Value
Names common to all three example files	Chen, Amy; Ortiz, Bea
File comparisons per synchronized step	3 (pairwise strcmp of the current lines)
Total time complexity	$O(n_A+n_B+n_C)$ — each file read once
Any input file empty	Loop condition false immediately; prints nothing

Concept & Theory

Topic. $k$-way merge as a linear-time algorithm on pre-sorted sequences.

Key relations. A synchronized $k$-way scan runs in $O(\sum n_i)$ total, versus $O(n\log n)$ to sort an unsorted union first — the "files are already sorted" given in the question is precisely what buys the better bound.

Why this works. If every input is sorted ascending, the smallest current line among all $k$ pointers is guaranteed never to reappear later in any file (a later line in a sorted file is only ever $\ge$ the current one), so it is always safe to discard it once it has been compared against the other pointers. Generalizing merge from two lists to $k$ costs nothing algorithmically — only the bookkeeping of "which pointers are tied for minimum" grows with $k$.

Common pitfall. Reading an entire file into memory first "to be safe" when the file's length is unknown — unnecessary here, and the question's own phrasing ("the number of lines is not known") is a hint toward the streaming, one-line-at-a-time approach rather than an obstacle to work around with dynamic arrays. A second is advancing all three pointers whenever any two are equal, which loses a genuine three-way match if the third pointer happens to be lagging behind for an unrelated reason.

Source. Cormen et al., Introduction to Algorithms, 4th ed., §2.3.1 (merge as a subroutine); Kernighan & Ritchie, The C Programming Language, 2nd ed., §7.4–7.5 (line input, fopen/fgets).

Question 6 of 8: File I/O — Names Common to Three Sorted Files

Question 6: File I/O — Names Common to Three Sorted Files (20 marks)