Module assignment: sorting toolkit in Python

What you are building

A teacher gives you the scores of one class. She wants a short report, and she wants it to be correct for ties, for a class of one student, and for a class of a thousand. The report has four parts. Each part uses one of the ideas from this module:

A ranking, which uses a key and a sort (lesson 4).
A median, which uses a sorted copy of the scores (lessons 1 and 4).
A histogram, which uses counting (lesson 2).
A count of out-of-order pairs, which uses the merge step of merge sort (lesson 3).

You will write one Python program that reads the input and prints the report. The program must follow the rules below exactly, because a checker will compare your output with the expected output, character by character, except for blank lines at the end.

This assignment is a problem set, not a project. It asks for a single file and no extra features. The stretch task at the end is optional, and it is for learners who finish early.

The input

The first line holds n, the number of students. Then come n lines. Each line has one student's name and score, separated by one space.

1 <= n <= 1000.
A name uses only letters. It starts with a capital letter, and the other letters are small letters. Names can repeat.
A score is a whole number from 0 to 100.

Example input 1:

6
Asha 72
Ravi 91
Meera 72
Dev 60
Kiran 91
Tara 45

Example input 2:

4
Zed 88
Amy 88
Bob 95
Cy 50

Read the input with input(), one line at a time. You do not need to handle bad input, such as a missing score or a letter where a number should be.

The output

The report has four sections, in this order. Every line must match the format exactly.

Section 1: the ranking. Print one line for each student, in ranked order. The ranked order is by score, highest first. Students with the same score are listed by name, alphabetically. The line format is rank name score, with single spaces. Students with the same score share the same rank. The rank of the next student skips the number of tied students. Scores 91, 91, 72, 72, 60, 45 get ranks 1, 1, 3, 3, 5, 6.

Section 2: the median. Print one line: Median: followed by the lower median of all the scores. Sort the scores from lowest to highest. The lower median is the value at index (n - 1) // 2, using integer division. For an even count, this is the lower of the two middle values. Do not compute an average.

Section 3: the histogram. Print six lines, one for each band, in this order and with these exact labels: 90-100, 80-89, 70-79, 60-69, 50-59, 0-49. Each line is the label, one space, and the number of students whose score is in that band. Print a band even when its count is zero.

Section 4: the upward pairs. Print one line: Upward pairs: followed by the number of pairs of positions i and j with i < j and score[i] < score[j]. The positions are the input order, not the ranked order. A pair is counted once. The answer can be large, but Python integers have no size limit, so a plain int is exact.

Here is the full output for example input 1:

1 Kiran 91
1 Ravi 91
3 Asha 72
3 Meera 72
5 Dev 60
6 Tara 45
Median: 72
90-100 2
80-89 0
70-79 2
60-69 1
50-59 0
0-49 1
Upward pairs: 4

Check the ranking. Kiran and Ravi both have 91, so both get rank 1, and Kiran comes first because K comes before R. Asha and Meera both have 72, so both get rank 3. The next student, Dev, gets rank 5, because two students stood above him. The median is 72, because the sorted scores are 45, 60, 72, 72, 91, 91, and index 2 holds 72.

Check the upward pairs. The scores in input order are 72, 91, 72, 60, 91, 45. The pairs that count are: 72 (Asha) with 91 (Ravi), 72 (Asha) with 91 (Kiran), 72 (Meera) with 91 (Kiran), and 60 (Dev) with 91 (Kiran). That is 4 pairs. Ravi's 91 has no bigger value after it, and Tara's 45 has nothing after it.

The output for example input 2 is:

1 Bob 95
2 Amy 88
2 Zed 88
4 Cy 50
Median: 88
90-100 1
80-89 2
70-79 0
60-69 0
50-59 1
0-49 0
Upward pairs: 2

Notice the rank of Cy. Two students have rank 2, so the next student gets rank 4, not 3.

A class of one student is also valid. The input 1 followed by Solo 73 gives this output:

1 Solo 73
Median: 73
90-100 0
80-89 0
70-79 1
60-69 0
50-59 0
0-49 0
Upward pairs: 0

Your program must not crash for n = 1. The median hint explains why the index works for one student.

Requirements checklist

Copy this checklist into your notes and tick each line when it is true. Do not tick a line until you have run the program and checked the output.

Grading rubric

Your grade depends on what your program does on a set of hidden inputs, and on the clarity of the code. Read the three levels before you start, so you know what each one looks like.

60 percent: it runs and gets the easy parts right. The program runs and prints the four sections in the right order. The ranking is correct for students with different scores. The median and the histogram are correct on the examples. The upward pairs are counted with two nested loops, which is correct and slow, and it gives the right answer for the examples. The program may fail on ties in the ranking, and it may crash for n = 1.

80 percent: all four parts are correct, including the tricky cases. The ranking handles ties with shared ranks and skipped numbers, and it sorts names correctly within a tie. The median is the lower median, and the program works for both odd and even counts. The histogram includes zero bands. The upward pair count is correct for every input and is fast enough for n = 1000, either with two nested loops or with a merge. The program works for n = 1.

100 percent: it is correct, fast and easy to read. Everything at 80 percent holds, and the upward pair count uses the merge method, which runs in O(n log n) time. The code is split into functions with names that match the four sections, and each function has a short docstring that says what it returns. You have tested at least two inputs of your own, beyond the examples, such as all scores equal, all students with one score, and a class of two students. The final message to your teacher, or your notes, says in two sentences how each part's time grows with n.

The grade does not depend on whether you used the exact function names in the reference solution. It depends on the output.

Checking your parts with small programs

Each of the four programs below does one part of the report the slow, simple way. They are checks, not the answer. Use them to confirm the numbers your own program prints. Save each program as a file, for example check1.py, then run it with python3 check1.py and type example input 1 when it waits for input. Each program reads its input with input(), so type one student per line.

The first check counts the upward pairs with two nested loops. It is correct for any class size and slow only for very big ones, so it is a good reference for your merge version.

n = int(input())
scores = []
for _ in range(n):
    name, score = input().split()
    scores.append(int(score))
 
count = 0
for i in range(n):
    for j in range(i + 1, n):
        if scores[i] < scores[j]:
            count += 1
print("Upward pairs:", count)

The second check prints the sorted scores and the index used for the lower median. The last line shows the index formula for three class sizes: one student, five students and six students.

n = int(input())
scores = []
for _ in range(n):
    name, score = input().split()
    scores.append(int(score))
 
ordered = sorted(scores)
print("sorted:", ordered)
index = (n - 1) // 2
print("index", index, "holds", ordered[index])
print("indexes for sizes 1, 5 and 6:", 0 // 2, 4 // 2, 5 // 2)

The third check computes each student's rank without sorting. The rank is 1 plus the number of students with a strictly higher score. Compare its output with your ranking. The lines come out in input order here, so you must match them by name. Your report must print the ranking in ranked order.

n = int(input())
names = []
scores = []
for _ in range(n):
    name, score = input().split()
    names.append(name)
    scores.append(int(score))
 
for i in range(n):
    higher = sum(1 for s in scores if s > scores[i])
    print(higher + 1, names[i], scores[i])

The fourth check counts the histogram bands with explicit ranges, one band at a time. Each band has a lowest and a highest score. A score counts for a band when it is inside both limits. It is a different method from your if chain, so matching output is a real cross-check.

n = int(input())
scores = []
for _ in range(n):
    name, score = input().split()
    scores.append(int(score))
 
labels = ["90-100", "80-89", "70-79", "60-69", "50-59", "0-49"]
low = [90, 80, 70, 60, 50, 0]
high = [100, 89, 79, 69, 59, 49]
for b in range(6):
    count = 0
    for score in scores:
        if low[b] <= score <= high[b]:
            count += 1
    print(labels[b], count)

The chained comparison low[b] <= score <= high[b] is a Python form that checks both limits in one line. It means the same as low[b] <= score and score <= high[b].

When the four checks agree with your program on example 1, example 2 and one student, your program is very likely right. Make a few inputs of your own, such as a class where every score is equal, and run the checks and your program on them too. Two methods that agree on many inputs are a stronger result than one method that passes the examples alone.

Hints

Try each part on paper with a class of four students before you write any code. Use the hints in order. Each one is hidden, so open it only after you have tried.

Show the hint for the ranking

Make a list of tuples or dataclass objects, like the Student class in the fourth lesson. Sort it with a key of (-score, name). Then walk the sorted list once. Keep a variable called rank. Set rank to the current position plus one only when the score is different from the score of the student before. Otherwise keep the old rank. This gives shared ranks and the skipped numbers at once.

Show the hint for the median

Use sorted(scores), which returns a new list and leaves the input order alone. You still need the input order for the upward pairs. The index you want is (n - 1) // 2. For n = 6 that is index 2, and for n = 1 that is index 0. This is why a class of one student works without a special case.

Show the hint for the histogram

Use a list of six counts, one per band, in the same order as the labels. Use an if chain from the highest band to the lowest. Check score >= 90 first, then score >= 80, and so on. Each score goes into exactly one count. Print the labels and counts with zip(labels, counts), so the labels and the counts always stay in the same order.

Show the hint for the upward pairs

An upward pair has an earlier value smaller than a later value. The merge method you learned in the third lesson counts pairs where an earlier value is bigger than a later one. To use it, make a second list with each score negated, so -score. An earlier score that is smaller than a later score becomes an earlier negated value that is bigger than the later negated value. The count of inversions in the negated list is the answer you want. Python integers are exact, so no special type is needed for the count.

If you want to check your work first, write the two nested loops that compare every pair. They are O(n squared), which is fine for n = 1000 for this assignment. Then write the merge version and check that both give the same answer on your test inputs.

Show the hint for putting it together

Write one function per section, and call them in order from a main function. Keep the input reading in main, and pass the lists to each function. Do not print inside the counting functions. Return the values and print them in main, so you can check each part separately. Start with the ranking and the input reading, run it on example 1, and only then add the next part.

Stretch task (optional)

After the report works, add a fifth line at the end of the output: Top score gap: followed by the difference between the highest and the second-highest distinct score. For example input 1, the distinct scores are 91, 72, 60 and 45, so the gap is 19. If only one distinct score exists, print Top score gap: 0. Write this with one pass over the sorted scores, not a new sort.

Reference solution

Try the whole assignment before you open this. The solution below is one correct way to write it. It is not the only correct way, and yours can look different and still earn full marks.

Show the reference solution

from dataclasses import dataclass
 
 
@dataclass
class Student:
    name: str
    score: int
 
 
def count_inversions(a, lo, hi, tmp):
    """Sort a[lo:hi] and return the number of pairs i < j with a[i] > a[j]."""
    if hi - lo < 2:
        return 0
    mid = lo + (hi - lo) // 2
    inv = count_inversions(a, lo, mid, tmp) + count_inversions(a, mid, hi, tmp)
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            tmp[k] = a[i]
            i += 1
        else:
            inv += mid - i
            tmp[k] = a[j]
            j += 1
        k += 1
    while i < mid:
        tmp[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        tmp[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = tmp[lo:hi]
    return inv
 
 
def print_ranking(students):
    """Print each student with a competition rank: ties share a rank, then the rank skips."""
    ranked = sorted(students, key=lambda s: (-s.score, s.name))
    rank = 1
    for i, s in enumerate(ranked):
        if i > 0 and s.score != ranked[i - 1].score:
            rank = i + 1
        print(rank, s.name, s.score)
 
 
def lower_median(scores):
    """The value at index (n - 1) // 2 of the sorted scores."""
    ordered = sorted(scores)
    return ordered[(len(ordered) - 1) // 2]
 
 
def print_histogram(scores):
    """Print six score bands, from 90-100 down to 0-49, including empty bands."""
    band = [0] * 6
    for s in scores:
        if s >= 90:
            band[0] += 1
        elif s >= 80:
            band[1] += 1
        elif s >= 70:
            band[2] += 1
        elif s >= 60:
            band[3] += 1
        elif s >= 50:
            band[4] += 1
        else:
            band[5] += 1
    labels = ["90-100", "80-89", "70-79", "60-69", "50-59", "0-49"]
    for label, count in zip(labels, band):
        print(label, count)
 
 
def count_upward_pairs(scores):
    """Count pairs in input order where the earlier score is smaller than the later one."""
    negated = [-s for s in scores]
    return count_inversions(negated, 0, len(negated), [0] * len(negated))
 
 
def main():
    n = int(input())
    students = []
    for _ in range(n):
        name, score = input().split()
        students.append(Student(name, int(score)))
    scores = [s.score for s in students]
 
    print_ranking(students)
    print("Median:", lower_median(scores))
    print_histogram(scores)
    print("Upward pairs:", count_upward_pairs(scores))
 
 
if __name__ == "__main__":
    main()

The line if __name__ == "__main__": runs main() only when you run the file directly. It does not run when another file imports the functions, which is useful when you test one function at a time.

Submitting

Save your program as main.py, type example input 1 when it waits for input, and run it with python3 main.py. Compare the output with the expected output above, line by line. Then type example input 2 and check again. Finally, type the input for one student, and then a class of two students with equal scores, and check the output by hand.

When all three match, your work is done. If an output differs, go back to the hint for that section and trace it on paper before you change the code.

What you now know

A report of several parts is easier to build as one function per part, each tested on its own.
A key of (-score, name) gives the ranking. Shared ranks come from a single walk over the sorted list.
The lower median is the value at index (n - 1) // 2 of the sorted scores, and that index works for one student.
Counting into fixed bands is counting sort in a small form, and every band must be printed, even when it is empty.
The upward pairs are inversions of negated scores, counted by the merge step in O(n log n) time. Python integers do not overflow, so the count is always exact.
Test the edge cases first: one student, all scores equal, and ties in the ranking.