Phase 1 labWeeks 1–4 3–4 hours

Lab 1: Grade Analyzer

Read student scores, rank them with all three simple sorts, compare their operation counts, and binary-search students by name.

Uses:2.3 Counting Time Units 3.1 Selection Sort 3.2 Bubble Sort 3.3 Insertion Sort 3.6 Binary Search

01Spec

The task

Your department wants a tiny console tool for marking. Given a list of students and scores, it must:

Rank the students from highest to lowest score.
Do the ranking three times, with selection, bubble and insertion sort, and report how many comparisons and swaps (or shifts) each one made on the same data. This is Chapter 2’s analysis in practice.
Print each student’s letter grade (A ≥ 85, B ≥ 70, C ≥ 55, D ≥ 40, else F) and the class average.
Binary-search students by name. Binary search needs sorted data, so sort a copy by name first.

Input format

n
name score      (n lines, names have no spaces)
query names     (until end of input)

Rules

Use plain arrays of struct Student. No std::sort, no std::vector for the sorting part.
Each sort works on its own copy of the input so the counts are fair.
Ties: students with the same score stay in input order in the printed ranking. Print the insertion-sort result, which is stable.

Questions to answer in your report

Which sort made the fewest comparisons on the sample? Why?
What happens to the counts if the input is already sorted? Reversed? Try it.
How many steps can binary search take at most for 8 students? For 1,000?

02Starter file

It compiles as-is. Every TODO is a milestone below.

Download grade-analyzer.cpp

grade-analyzer-starter.cpp56 lines · C++17

Compiler ExplorerRun OnlineGDB

// Lab 1: Grade Analyzer (starter). Fill in every TODO, then compare with the sample output.
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 100;

struct Student {
    string name;
    int score;
};

struct Counter {
    long comparisons = 0, swaps = 0;
};

// Each sort orders students by score, HIGHEST first, and counts its work in c.
void selectionSort(Student a[], int n, Counter& c) {
    // TODO: find the best remaining student, swap it into place, count comparisons and swaps
    (void)a; (void)n; (void)c;
}

void bubbleSort(Student a[], int n, Counter& c) {
    // TODO: adjacent compare-and-swap with an early-exit flag
    (void)a; (void)n; (void)c;
}

void insertionSort(Student a[], int n, Counter& c) {
    // TODO: shift lower scores right and insert the key; count shifts in c.swaps
    (void)a; (void)n; (void)c;
}

void sortByName(Student a[], int n) {
    // TODO: any simple sort, A to Z by name (binary search needs this)
    (void)a; (void)n;
}

int binarySearch(const Student a[], int n, const string& name, int& steps) {
    // TODO: return the index of name, or -1; count loop iterations in steps
    (void)a; (void)n; (void)name;
    steps = 0;
    return -1;
}

int main() {
    int n;
    Student input[MAXN];
    if (!(cin >> n) || n < 1 || n > MAXN) { cout << "bad input\n"; return 1; }
    for (int i = 0; i < n; i++) cin >> input[i].name >> input[i].score;

    // TODO 1: copy input into three arrays and run each sort with its own Counter
    // TODO 2: print the ranking, the average, and the three operation counts
    // TODO 3: sort by name, then read names until end of input and binary-search each one

    cout << "read " << n << " students\n";
}

// Lab 1: Grade Analyzer (starter). Fill in every TODO, then compare with the sample output.
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 100;

struct Student {
    string name;
    int score;
};

struct Counter {
    long comparisons = 0, swaps = 0;
};

// Each sort orders students by score, HIGHEST first, and counts its work in c.
void selectionSort(Student a[], int n, Counter& c) {
    // TODO: find the best remaining student, swap it into place, count comparisons and swaps
    (void)a; (void)n; (void)c;
}

void bubbleSort(Student a[], int n, Counter& c) {
    // TODO: adjacent compare-and-swap with an early-exit flag
    (void)a; (void)n; (void)c;
}

void insertionSort(Student a[], int n, Counter& c) {
    // TODO: shift lower scores right and insert the key; count shifts in c.swaps
    (void)a; (void)n; (void)c;
}

void sortByName(Student a[], int n) {
    // TODO: any simple sort, A to Z by name (binary search needs this)
    (void)a; (void)n;
}

int binarySearch(const Student a[], int n, const string& name, int& steps) {
    // TODO: return the index of name, or -1; count loop iterations in steps
    (void)a; (void)n; (void)name;
    steps = 0;
    return -1;
}

int main() {
    int n;
    Student input[MAXN];
    if (!(cin >> n) || n < 1 || n > MAXN) { cout << "bad input\n"; return 1; }
    for (int i = 0; i < n; i++) cin >> input[i].name >> input[i].score;

// TODO 1: copy input into three arrays and run each sort with its own Counter
    // TODO 2: print the ranking, the average, and the three operation counts
    // TODO 3: sort by name, then read names until end of input and binary-search each one

cout << "read " << n << " students\n";
}

03Milestones

Read n and n lines of "name score" into an array of structs.
Implement selection sort (highest score first) and count comparisons and swaps.
Implement bubble sort with the early-exit flag, counting the same way.
Implement insertion sort, counting comparisons and shifts. Check that all three rankings agree.
Print the ranking with letter grades and the class average.
Sort a copy by name, then binary-search every remaining input name and print the number of steps.
Bonus: explain in a comment why bubble and insertion keep Hana before Sara (stability) and whether selection does.

0/7 ticked

04Sample input & output

Save the input as input.txt and run ./grade-analyzer < input.txt. Your output should match the solution's output exactly.

input.txt

8
Abebe 72
Hana 91
Dawit 58
Liya 85
Kebede 40
Sara 91
Yonas 66
Meron 77
Liya
Yonas
Tigist

05Reference solution

Don't just watch: implement it yourself, then solve 2–3 problems. Try for at least an hour before opening this.

Show the solution

grade-analyzer.cpp111 lines · C++17

Compiler ExplorerRun OnlineGDB

// Lab 1: Grade Analyzer (solution)
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 100;

struct Student {
    string name;
    int score;
};

struct Counter {
    long comparisons = 0, swaps = 0;
};

// Sort by score, highest first. Ties keep input order (stable sorts only).
void selectionSort(Student a[], int n, Counter& c) {
    for (int i = 0; i < n - 1; i++) {
        int best = i;
        for (int j = i + 1; j < n; j++) {
            c.comparisons++;
            if (a[j].score > a[best].score) best = j;
        }
        if (best != i) { swap(a[i], a[best]); c.swaps++; }
    }
}

void bubbleSort(Student a[], int n, Counter& c) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            c.comparisons++;
            if (a[j].score < a[j + 1].score) { swap(a[j], a[j + 1]); c.swaps++; swapped = true; }
        }
        if (!swapped) break;
    }
}

void insertionSort(Student a[], int n, Counter& c) {
    for (int i = 1; i < n; i++) {
        Student key = a[i];
        int j = i - 1;
        while (j >= 0) {
            c.comparisons++;
            if (a[j].score >= key.score) break;
            a[j + 1] = a[j];
            c.swaps++;                       // counts shifts
            j--;
        }
        a[j + 1] = key;
    }
}

void sortByName(Student a[], int n) {        // insertion sort, A to Z
    for (int i = 1; i < n; i++) {
        Student key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j].name > key.name) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

int binarySearch(const Student a[], int n, const string& name, int& steps) {
    int lo = 0, hi = n - 1;
    steps = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        steps++;
        if (a[mid].name == name) return mid;
        if (a[mid].name < name) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

char grade(int s) { return s >= 85 ? 'A' : s >= 70 ? 'B' : s >= 55 ? 'C' : s >= 40 ? 'D' : 'F'; }

int main() {
    int n;
    Student input[MAXN];
    if (!(cin >> n) || n < 1 || n > MAXN) { cout << "bad input\n"; return 1; }
    long total = 0;
    for (int i = 0; i < n; i++) { cin >> input[i].name >> input[i].score; total += input[i].score; }

    Student a[MAXN], b[MAXN], c[MAXN];
    for (int i = 0; i < n; i++) a[i] = b[i] = c[i] = input[i];
    Counter cs, cb, ci;
    selectionSort(a, n, cs);
    bubbleSort(b, n, cb);
    insertionSort(c, n, ci);

    cout << "Ranking:\n";
    for (int i = 0; i < n; i++)
        cout << "  " << i + 1 << ". " << c[i].name << " " << c[i].score << " (" << grade(c[i].score) << ")\n";
    cout << "Average: " << (double)total / n << "\n\n";

    cout << "Operation counts (n = " << n << "):\n";
    cout << "  selection  comparisons " << cs.comparisons << ", swaps " << cs.swaps << "\n";
    cout << "  bubble     comparisons " << cb.comparisons << ", swaps " << cb.swaps << "\n";
    cout << "  insertion  comparisons " << ci.comparisons << ", shifts " << ci.swaps << "\n\n";

    sortByName(c, n);
    string q;
    while (cin >> q) {
        int steps;
        int k = binarySearch(c, n, q, steps);
        if (k == -1) cout << "search " << q << ": not found (" << steps << " steps)\n";
        else cout << "search " << q << ": " << c[k].score << " (" << steps << " steps)\n";
    }
}

// Lab 1: Grade Analyzer (solution)
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 100;

struct Student {
    string name;
    int score;
};

struct Counter {
    long comparisons = 0, swaps = 0;
};

// Sort by score, highest first. Ties keep input order (stable sorts only).
void selectionSort(Student a[], int n, Counter& c) {
    for (int i = 0; i < n - 1; i++) {
        int best = i;
        for (int j = i + 1; j < n; j++) {
            c.comparisons++;
            if (a[j].score > a[best].score) best = j;
        }
        if (best != i) { swap(a[i], a[best]); c.swaps++; }
    }
}

void bubbleSort(Student a[], int n, Counter& c) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            c.comparisons++;
            if (a[j].score < a[j + 1].score) { swap(a[j], a[j + 1]); c.swaps++; swapped = true; }
        }
        if (!swapped) break;
    }
}

void insertionSort(Student a[], int n, Counter& c) {
    for (int i = 1; i < n; i++) {
        Student key = a[i];
        int j = i - 1;
        while (j >= 0) {
            c.comparisons++;
            if (a[j].score >= key.score) break;
            a[j + 1] = a[j];
            c.swaps++;                       // counts shifts
            j--;
        }
        a[j + 1] = key;
    }
}

void sortByName(Student a[], int n) {        // insertion sort, A to Z
    for (int i = 1; i < n; i++) {
        Student key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j].name > key.name) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

int binarySearch(const Student a[], int n, const string& name, int& steps) {
    int lo = 0, hi = n - 1;
    steps = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        steps++;
        if (a[mid].name == name) return mid;
        if (a[mid].name < name) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

char grade(int s) { return s >= 85 ? 'A' : s >= 70 ? 'B' : s >= 55 ? 'C' : s >= 40 ? 'D' : 'F'; }

int main() {
    int n;
    Student input[MAXN];
    if (!(cin >> n) || n < 1 || n > MAXN) { cout << "bad input\n"; return 1; }
    long total = 0;
    for (int i = 0; i < n; i++) { cin >> input[i].name >> input[i].score; total += input[i].score; }

Student a[MAXN], b[MAXN], c[MAXN];
    for (int i = 0; i < n; i++) a[i] = b[i] = c[i] = input[i];
    Counter cs, cb, ci;
    selectionSort(a, n, cs);
    bubbleSort(b, n, cb);
    insertionSort(c, n, ci);

cout << "Ranking:\n";
    for (int i = 0; i < n; i++)
        cout << "  " << i + 1 << ". " << c[i].name << " " << c[i].score << " (" << grade(c[i].score) << ")\n";
    cout << "Average: " << (double)total / n << "\n\n";

cout << "Operation counts (n = " << n << "):\n";
    cout << "  selection  comparisons " << cs.comparisons << ", swaps " << cs.swaps << "\n";
    cout << "  bubble     comparisons " << cb.comparisons << ", swaps " << cb.swaps << "\n";
    cout << "  insertion  comparisons " << ci.comparisons << ", shifts " << ci.swaps << "\n\n";

sortByName(c, n);
    string q;
    while (cin >> q) {
        int steps;
        int k = binarySearch(c, n, q, steps);
        if (k == -1) cout << "search " << q << ": not found (" << steps << " steps)\n";
        else cout << "search " << q << ": " << c[k].score << " (" << steps << " steps)\n";
    }
}

Expected output (with sample input)

Ranking:
  1. Hana 91 (A)
  2. Sara 91 (A)
  3. Liya 85 (A)
  4. Meron 77 (B)
  5. Abebe 72 (B)
  6. Yonas 66 (C)
  7. Dawit 58 (C)
  8. Kebede 40 (D)
Average: 72.5

Operation counts (n = 8):
  selection  comparisons 28, swaps 7
  bubble     comparisons 25, swaps 13
  insertion  comparisons 19, shifts 13

search Liya: 85 (3 steps)
search Yonas: 66 (4 steps)
search Tigist: not found (4 steps)