Module assignment: Divide and conquer in Python

Why this assignment exists

This assignment asks you to use everything in the module in one program. You will sort with merge sort, search with binary search, pick the k-th value with quick select, count inversions with the merge step, and find an id in a rotated list. Each part is a function you have already written in the lessons. The new skill is combining them into one program that reads commands, handles edge cases, and prints exactly the required output.

Working on a single program with several functions is how real projects look. You will read input, decide which tool fits each question, and check your work against examples. Treat it as a small project, not a quiz. Plan the program before you type, and test each part before you combine it with the others.

Before you start, reread the lesson summaries. Binary search and the lower bound come from lesson 1. Merge sort and its merge step come from lesson 2. Quick sort, the partition step and quick select come from lesson 3. The rotated search and the inversion count come from lesson 4.

The story

A small club runs a leaderboard. Members post scores in the order they arrive, and the club wants a report tool. The organizers ask for five things: the scores in order, how many scores reach a given level, the k-th smallest score, how far the arrival order is from sorted order, and the position of a member's id in a list that was sorted and then rotated.

The club keeps the data in two lists. The first is the list of scores in arrival order. The second is a list of member ids, which was sorted and then rotated. Your program reads both lists and then answers a sequence of commands. Each command is one line.

Your job is to write the program. The organizers do not care how you wrote it, as long as it prints the right answer for each command and handles the edge cases.

The input format

The input has five parts, in this order.

1. A line with one number n, the number of scores. n is between 1 and 800.
2. A line with n scores, separated by spaces. Each score is a whole number from 0 to 1000. Scores may repeat. The order is arrival order, so it is not sorted.
3. A line with one number m, the number of ids in the rotated list. m is between 1 and 800.
4. A line with m ids, separated by spaces. The ids are different from each other. The list was sorted in increasing order and then rotated, so its smallest value may sit in the middle.
5. A line with one number q, the number of commands, from 0 to 50. Then q lines follow, one command per line.

There are five kinds of command.

• sorted prints all the scores in increasing order, separated by single spaces.
• atleast X prints how many scores are greater than or equal to X.
• kth K prints the K-th smallest score. Here K counts from 1, so kth 1 is the smallest score.
• disorder prints the number of out-of-order pairs in the arrival order. A pair is out of order when the earlier score is bigger than the later score. Equal scores are not out of order.
• where X prints the position of id X in the rotated list, counting from 0, or -1 if it is not there.

The output has one line for each command, in the same order as the commands. A sorted command prints one line of numbers. Every other command prints one number.

The sample

Here is a complete sample. Type it into the Input box, one line at a time, to test your program.

6
70 40 90 40 60 10
5
50 60 10 20 30
5
sorted
atleast 40
kth 3
disorder
where 20

The correct output is:

10 40 40 60 70 90
5
40
10
3

Check each line by hand before you trust your program. The sorted scores are 10 40 40 60 70 90. Five scores are at least 40: the two 40s, the 60, the 70 and the 90. The third smallest is 40, because the two smallest are 10 and 40. The number of out-of-order pairs is 10, which is easiest to check by listing, for each score, how many later scores are smaller. The id 20 sits at position 3 of the rotated list 50 60 10 20 30.

Two more tests to try

Good testing means trying inputs that the sample does not cover. Use these two. Run them yourself, and check the answers before you read the next paragraph.

1
5
2
50 10
3
sorted
atleast 6
where 10

The expected output is 5, then 0, then 1. The list has one score, so the sorted list is just 5. No score is at least 6. The id 10 sits at position 1 of the rotated list.

4
3 3 3 1
2
4 2
3
disorder
kth 4
where 7

The expected output is 3, then 3, then -1. The arrival order 3 3 3 1 has three out-of-order pairs, one for each 3 that comes before the 1. The fourth smallest value is 3. The id 7 is not in the list 4 2, so the answer is -1.

The first of these tests covers the smallest possible input, one score. The second covers duplicates, which is where many counting and searching methods fail. Keep both in your test set. A program that passes only the sample is not finished.

Checkpoints: test each part before you combine them

Each command uses one method from the module. The five programs below test one function each on fixed data, so you can check that each function works before you put them together. Run each one and compare its output with the output shown under it. Do not skip this step, because a combined program is much harder to debug than five small ones.

Checkpoint 1 tests merge sort on the sample scores. It is the function behind the sorted command, and it must keep equal scores in order. This version returns a new list and leaves the list it receives unchanged. The last line prints the original list to show that it did not change.

The output is:

sorted: [10, 40, 40, 60, 70, 90]
original: [70, 40, 90, 40, 60, 10]

Checkpoint 2 tests the lower bound, which answers the atleast command. The list must already be sorted, and the function returns the first position whose value is not less than x. The count of scores at least x is then the length of the list minus that position. The last line checks the same answer with bisect, the standard library module that has this search built in.

The output is:

at least 40: 5
at least 95: 0
bisect check: 5

Checkpoint 3 tests quick select on the same scores. It is the function behind the kth command. Index 2 is the third smallest value, counting from 0 inside the function, and the program asks for the smallest value too.

The output is:

third smallest: 40
smallest: 10

Notice that each call receives a copy of the list, because select rearranges the values it is given. The [:] makes the copy. This is slicing, which takes a part of a list between two positions. Leaving out both positions takes the whole list, so the result is a new list with the same values.

Checkpoint 4 tests the inversion count on the sample scores. It is the function behind the disorder command. The function returns two things, the count and a sorted copy of the list. The count is the only part the disorder command needs. The last two lines check the rule that equal scores are not out of order.

The output is:

inversions: 10
equal scores: 3
all equal: 0

The _ in count, _ = ... is a name for a value you do not need. The underscore is a normal name in Python, and the convention is that it means "unused".

Checkpoint 5 tests the rotated search, which answers the where command. The list 50 60 10 20 30 is the sorted list 10 20 30 50 60 rotated, so the search must work without the list being fully sorted. The conditions use chained comparisons. In Python, values[lo] <= target < values[mid] means values[lo] <= target and target < values[mid] at the same time.

The output is:

where 20: index 3
where 99: index -1

Requirements checklist

Before you submit, go through this list. Each item is a requirement, and a task you can check off.

• The program reads the five parts of the input in the right order, including the case where q is 0.
• The sorted command prints the scores in increasing order, with single spaces and no trailing space.
• The sorted command uses merge sort, or another method you can explain, and it does not change the original scores list.
• The atleast command uses a lower bound on a sorted copy, and it prints the count as one number.
• The kth command prints the K-th smallest score, counting from 1, and it works when scores repeat.
• The disorder command prints the number of out-of-order pairs, and the code comments say why the count needs no size limit.
• The where command uses the rotated search, and it prints -1 when the id is missing.
• The program handles a list with one score, and a list where every score is the same.
• Each command is a separate function or a clearly separated block, so a reader can find it.
• A comment near the top states the time and space cost of each command in your own words.
• You ran the sample and both extra tests, and every output line matched.

Grading rubric

The grade depends on what the program does, not how long it is.

60 percent: a working core. The program runs and reads the input. The sorted and atleast commands print the right output on the sample. Other commands may be wrong or missing. A program at this level shows that you can read input and use two of the methods correctly.

80 percent: most commands correct. All five commands print the right output on the sample. They also work on the two extra tests in this assignment. The where command may still be missing the case when the id is absent. A program at this level shows that you can combine the methods and test them.

100 percent: correct and explained. All five commands are correct on the sample and on the two extra tests. The program also handles the case where q is 0, the case where all scores are equal, and the case where an id is missing. The code comments explain why the disorder count needs no wider type, and they state the time and space cost of each command. The functions are named and separated so a reader can find each one. A program at this level could be handed to a teammate who understands divide and conquer.

A program that prints the wrong format, such as extra spaces, a missing line, or a label that was not asked for, loses points even if the numbers are right. The output must match the examples exactly, because a judging tool compares text, not meaning.

Hints

Try to finish without the hints. If you get stuck, open one hint at a time. Each one gives you a step, not the full answer.

Hint 1: reading the input

Read all of the input at once with sys.stdin.read(), then split it into words with split(). Wrap the words in iter(), so that next() hands out one word at a time in order. Read n with int(next(tokens)), then n scores with a list comprehension. Read m, then m ids. Read q, and loop q times. In each loop, read the command word with next(tokens). Only read the extra number, such as X or K, for the commands that have one. Reading a word that is not there will stop the program with an error. Because the words are read in order, line breaks do not matter.

Hint 2: the sorted command

merge_sort returns a new list, so scores stays in arrival order for the disorder command. Print the sorted list with " ".join(str(value) for value in ...). The str(value) part turns each number into text, and " ".join puts a single space between the pieces.

Hint 3: the atleast command

Sort a copy of the scores, as in hint 2. Then call bisect.bisect_left with the sorted list and the value X. It returns the same position as your lower bound, which is the number of scores below X. Subtract it from n. Check your answer with a score equal to X on the sample.

Hint 4: the kth command

Use quick select with a copy of the scores, written scores[:]. The command gives K counting from 1, but the select function counts from 0, so pass K - 1. Test kth 1 and kth n. Both should match the smallest and the largest score.

Hint 5: the disorder command

count_inversions returns a pair, the count and a sorted list. Take the count with [0]. If your answer on 3 3 3 1 is not 3, check that equal scores are not counted. The <= in the merge is what keeps equal values in order, and it is why equal values are not counted.

Hint 6: the where command

Run the rotated search on the ring list. It returns -1 when the id is not present, so print that value as it is. If it fails on the sample, trace the search for id 20 by hand on the list 50 60 10 20 30, and check which half is sorted at each step. Remember that values[lo] <= target < values[mid] is two checks joined together.

Stretch extension

If you finish early, extend the program with a median command. It prints the middle score when there are an odd number of scores, and the average of the two middle scores, rounded down, when there are an even number. Use // for the rounding down, so (3 + 4) // 2 is 3. Use quick select for the middle positions, and check it with a list of one score and a list of two scores. Think about why the two-score case needs two quick selects, or one select followed by a search for the next largest value below it.

Reference solution

Try the assignment first. This solution is for checking your work after you have tested your own version.

import sys
 
 
def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
def merge_sort(values):
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return merge(left, right)
 
 
def lower_bound(values, x):
    low = 0
    high = len(values)
    while low < high:
        mid = low + (high - low) // 2
        if values[mid] < x:
            low = mid + 1
        else:
            high = mid
    return low
 
 
def swap(values, x, y):
    values[x], values[y] = values[y], values[x]
 
 
def partition(values, lo, hi):
    pivot = values[hi]
    i = lo - 1
    for j in range(lo, hi):
        if values[j] < pivot:
            i += 1
            swap(values, i, j)
    swap(values, i + 1, hi)
    return i + 1
 
 
def select(values, lo, hi, k):
    while True:
        if lo == hi:
            return values[lo]
        p = partition(values, lo, hi)
        if k == p:
            return values[p]
        if k < p:
            hi = p - 1
        else:
            lo = p + 1
 
 
def count_inversions(values):
    if len(values) <= 1:
        return 0, list(values)
    mid = len(values) // 2
    left_count, left = count_inversions(values[:mid])
    right_count, right = count_inversions(values[mid:])
    count = left_count + right_count
    merged = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            count += len(left) - i
    merged.extend(left[i:])
    merged.extend(right[j:])
    return count, merged
 
 
def search_rotated(values, target):
    lo = 0
    hi = len(values) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if values[mid] == target:
            return mid
        if values[lo] <= values[mid]:
            if values[lo] <= target < values[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if values[mid] < target <= values[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
 
 
def main():
    tokens = iter(sys.stdin.read().split())
    n = int(next(tokens))
    scores = [int(next(tokens)) for _ in range(n)]
    m = int(next(tokens))
    ring = [int(next(tokens)) for _ in range(m)]
    q = int(next(tokens))
    for _ in range(q):
        command = next(tokens)
        if command == "sorted":
            print(" ".join(str(value) for value in merge_sort(scores)))
        elif command == "atleast":
            x = int(next(tokens))
            print(n - lower_bound(merge_sort(scores), x))
        elif command == "kth":
            k = int(next(tokens))
            print(select(scores[:], 0, n - 1, k - 1))
        elif command == "disorder":
            print(count_inversions(scores)[0])
        elif command == "where":
            x = int(next(tokens))
            print(search_rotated(ring, x))
 
 
if __name__ == "__main__":
    main()

The recursion in merge sort and in the inversion count goes only as deep as log2 of the list length. For 800 scores that is about 10 levels. Python stops a program that recurses more than 1000 levels by default, so this code is far below the limit.

Cost of each command

Write these in your own words in the comment at the top of your program. The reference answers are given so you can check your wording.

• sorted takes O(n log n) time and O(n) extra space, from merge sort and the new list it builds.
• atleast takes O(n log n) time for the sort and O(log n) for each lower bound, and O(n) extra space for the copy.
• kth takes O(n) time on average, because each partition keeps only one side, and O(n) extra space for the copy.
• disorder takes O(n log n) time and O(n) extra space, from the merge count.
• where takes O(log n) time and O(1) extra space for each command.

What you now know

• You can combine merge sort, binary search, quick select, inversion counting and rotated search in one program.
• You test each function on its own before you combine them, because a small failing check is faster to fix than a large program.
• You check the output format as well as the numbers, because the output is compared exactly.
• You test edge cases first: one item, repeated values, empty command lists and missing values.