Exercise: Sort the Leaderboard

A racing game's board of 10,000 players falls behind when every late score sorts it all again: slide each late score into place instead, write both of the chapter's sorts for a race's results, and let the tests check them, ties and a busy evening included.

Apprentice · Data Structures · Updated

By

Here's the ticket from the racing game's lead developer:

The time-trial board has 10,000 players, and a late score arrives every few seconds. Today the server adds it to the end and sorts the whole board again, and on a busy evening the board falls minutes behind.

  1. A late score goes straight into its place on the board that's already sorted, most points first. A tie goes after the players already on that score: they got there first.
  2. 1,000 late scores on a board of 10,000 are placed in under 2 seconds.
  3. We still sort a whole race's results when it ends, in finishing order to start with. We want two hand-written ways to compare, without the built-in sort: the "find the best, swap it to the front" way the old board used, and the "slide each one into place" way.
  4. Nobody's list is changed under them: every function gives back a new list.

You've met both of the chapter's sorts, and the move that keeps a board sorted. The tests check six players' results, 500 players, ties, and then the ticket's busy evening: 1,000 late scores on a board of 10,000, in under 2 seconds.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-sort-leaderboard, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-sort-leaderboard.git

Git makes a folder, exercise-ds-sort-leaderboard, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • your code: one file with three functions to finish (the repository's README.md names the file for each language);
  • a player: a name and their points, as a Player record in C# and Java, a Player dataclass in Python, and an object like { name: "PixelPilot", points: 2400 } in JavaScript and TypeScript;
  • the tests that check your functions. You don't need to change them;
  • a demo program that tries your functions on the six players' results.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

Every function is already there, with its parameters, and returns an empty list for now. The comment above each one says what it should return, with an example. Write the sorts yourself: don't call your language's built-in sort. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):

def selection_sort(players):
    """
    Sort the players by points, highest first, with selection sort:
    find the player with the most points in the unsorted part, swap
    them to the front of that part, and repeat. Work on a COPY, so the
    list you were given keeps its own order.

    selection_sort([PixelPilot 2400, NovaByte 3150, QuietStorm 1980])
      -> [NovaByte 3150, PixelPilot 2400, QuietStorm 1980]

    Growth rate: (write it here)
    """
    return []
  1. A late score. Finish addToBoard (add_to_board in Python, AddToBoard in C#): a new board with one player slid into place in a board that's already sorted. A tie goes after the players already there.
  2. The old board's sort. Finish selectionSort: a sorted copy of a race's results, most points first, found best-first and swapped to the front.
  3. The sliding sort. Finish insertionSort, with the same answer: slide each player left past every player with fewer points.
  4. Name the growth rates. On each function's Growth rate: line, write its Big-O and a few words on why. For insertion sort, say what changes when the board is almost sorted.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project Leaderboard
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 9 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: MintyFresh ties NovaByte on 3150, so goes after NovaByte, who got there first.

<details> <summary>Stuck?</summary>

  • Where to look: the "find the best, swap it to the front" sort is Putting the Leaderboard in Order: Selection Sort; the "slide each one into place" sort is One New Score on a Sorted Leaderboard: Insertion Sort.
  • addToBoard is one insertion-sort pass: add the newcomer to the end of a copy of the board, then slide them left. Don't sort the whole board again: the busy-evening test stops after 2 seconds.
  • Sort a copy. Make a new list from the one you're given, then sort and return that. One test checks that the results keep the order the players finished in.
  • Most points first turns the lessons' comparisons around: selection sort looks for the most points left, and insertion sort slides a player past every player with fewer points.
  • Compare points, not players. Each comparison reads the two players' points: board[i].Points in C#, board.get(i).points() in Java, board[i].points in Python, JavaScript and TypeScript.
  • A tie stays behind: slide only past players with fewer points, not the same number.

</details>

When you're done

Every test is green, and the demo prints the same four lines in every language:

Results: PixelPilot 2400, NovaByte 3150, QuietStorm 1980, LemonDash 2875, RetroFox 3400, ByteKnight 2210
Selection sort: RetroFox 3400, NovaByte 3150, LemonDash 2875, PixelPilot 2400, ByteKnight 2210, QuietStorm 1980
Insertion sort: RetroFox 3400, NovaByte 3150, LemonDash 2875, PixelPilot 2400, ByteKnight 2210, QuietStorm 1980
EchoWave scores 2600: RetroFox 3400, NovaByte 3150, LemonDash 2875, EchoWave 2600, PixelPilot 2400, ByteKnight 2210, QuietStorm 1980

Now look at the last line, and at the busy-evening test. Why did one slide beat sorting the whole board again, and why would sorting again with insertion sort, rather than selection sort, have passed the test too?

<details> <summary>Why Should I Choose This?</summary>

On the busy evening, 1,000 late scores arrive on a board of 10,000. Adding each one and sorting again with selection sort costs about 50 million comparisons a score, 50 billion for the evening; measured, the 2 seconds ran out with only 1 of the 1,000 scores placed in Python, 6 in C# and about 30 in Java, JavaScript and TypeScript. Sorting only when the board is opened pays the same, later. Sliding each score into place is at most 11,000 steps, and the whole evening took a fraction of a second. Insertion sort on a sorted board with one new score at the end does exactly that slide, which is why it's the sort to keep for data that's almost in order. What it gives up: the slide is still O(n), so a board of millions with scores pouring in needs the trees and heaps of Module 6.

</details>

Where else does this shape show up?

You've used "slide the new one into its place among the ones already in order". Before you open the answers, think of three other places, at work or in daily life, where something new goes into a list that's already sorted.

<details> <summary>Some answers</summary>

  • Filing a new folder in a drawer kept A to Z: you find its place and push the others along.
  • A librarian reshelving a returned book between its neighbors on the shelf.
  • A calendar adding a meeting among the day's other meetings, in time order.
  • Your inbox, sorted by date, when a delayed email arrives with an older time on it.
  • A hand of cards, one card dealt at a time.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-sort-leaderboard), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-sort-leaderboard.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-sort-leaderboard, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

So what

You've sorted the same board two ways and kept it sorted with one slide, the move that turned 50 million comparisons a score into a few thousand. Both sorts are O(n²) on a jumbled list, which is fine for six players and painful for a million songs. The next chapter's sorts split the work in half and get it down to O(n log n).

Key terms

Related