What's the most practical and efficient way to sort exams on paper?

Question

There are a lot of sorting algorithms to sort a list on a computer, and a lot of theory about them. However, my problem is not how to sort a list under the quite well defined conditions of a computer, but to sort alphabetically a pile of exams (made on paper) after grading them.

I must admit that I'll never amortise the effort of optimising a task that just takes a fraction of an hour a few times a year, but that fraction of an hour is boring and I can't avoid thinking about the problem of optimising the task while I'm at it, and getting interested in that problem. I hope the question is in topic here - more than in ComputerScience.SE or even LifeHacks.SE - and I think I'm more likely to find here users with related experience and expertise.

The question, formatted in a general way, is what's the most efficient and practical way to sort a set of papers. If details matter, we can assume we are ordering one hundred to a few hundreds of papers, and that we have a table but not a very large one - we can't put all the papers on the table to see all of them at the same time. However, the order key is in the top of the paper (we can assume the top inch), so we can pile a few papers and still be able to see the key. In any way, the conditions are different than those for a computer algorithm and they are less well defined.

This problem has two variants:

• The order key is the student's name - that is, given any two exams, there can be more exams that must be placed between them.
• The order key is a natural number - that is, if we find exams with successive numbers, we can be sure that no other exam will go between them.

So far, I think the most efficient way I use is to order small batches of exams - small enough that I can hold them in my hand or put them on the table while being able to see all order keys or to find them quickly - and then join batches pairwise until I get a single batch.

A different approach I've used is to bin the exams in small batches according to initial letter or by another way of making similar sized intervals, and then order every batch.

Answer 1

An eminently pragmatic question about sorting! :)

When I was dealing with 150+ papers, on a not-too-large table-top, after various experiments, I found that subsets of 10 or 12 I could visually sort fairly easily. Then, with 10-ish stacks of already-ordered papers, it was feasable for me to visually choose things in alpha order, to merge them/

That is, a two-stage (is it "merge"?) sort is pretty fairly human executable, for 100-ish things. :)

EDIT: in particular, after the first sorting of the smaller piles, those smaller piles do not have to have all the names visible, since the "merge" step only needs to know about the top item in each sub-collection. So, in the merge step, it does not matter where on the page the students' names are, nor is there any need for delicate physical configuration.

Answer 2

For hundreds of exams, I'm a fan of your second proposed approach, specifically, break up the alphabet into $n$ intervals where $n$ is the number of piles you can reach simultaneously without moving, such that the number of students who fall into each interval is roughly even, then sort each pile. Depending on the situation, you may be able to get students to hand in their exams into different piles by first letter of their name.

For slightly smaller piles of exams (30-70), I prefer to simultaneously enter grades into my spreadsheet and sort. At each stage of the sorting process, every alphabetically consecutive group of exams should form a pile with each exam stacked directly on top of the next. I stack these piles fanning vertically so that for each pile I can see the name on the exam on top of the pile. When I enter the grade for a new exam into my spreadsheet, I branch:

• If I haven't yet entered the score for the student before or after this one into my grade book, I make a note of the next student's name whose grade I have already entered, and start a new pile between the pile with that student's name on top and the previous pile (I also check whose name should be on top of that pile to make sure I haven't made any mistakes).

• If I have entered the next student's score, but not the previous student's score, the exam goes directly on top of the pile that the next student's exam is currently on top of.

• If I have entered the previous students' score, but not the next student's score, the exam goes on the bottom of a consecutive pile: look back through the spreadsheet for the first student in the consecutive group you just added to, then find the pile with their exam on top.

• If I have entered both the previous and next students' scores, it joins two consecutive intervals of students within the spreadsheet. I place the exam between the two piles and merge them together.

The amount of physical space this takes up depends on the maximum amount of piles necessary at any one time during the process. If there are $N$ students, what is the expected maximum number of piles necessary?

Answer 3

Frame Challenge: Don't bother.

For the last five or six years, I have been using GradeScope for all of my grading. Before that, I used CrowdMark. Both of these services allow you to upload unsorted exams, then grade them through their system.

The trick is that each copy of the written exam (printed on paper) has a small QR code in the corner of each page (the software helps you to do this). On the font page of each exam, we placed areas for students to write their names and student IDs (rows of boxes with one letter or number per box). After the exam, we used a heavy duty paper cutter to remove the staples from exams, then a top-loading scanner to scan the exams into a .pdf. The file(s) produced in this manner can then be uploaded to the grading service, and are automatically grouped (using the QR codes) into per-student exams, and automatically associated with a student using the identification regions on the front page. For students whose handwriting cannot be recognized by the OCR system (typically less than 3% of exams), the association can be done manually.

In addition to "sorting" exams, these systems make it very easy to work with TAs (you can assign TAs to grade certain parts of each exam, for example), and students get much more immediate feedback (as soon as you are done grading, you can publish the scores, and students can see your grading and feedback). You also have more control over students altering exams after being graded, in that they can't.

The major downsides I see are that these services are proprietary (though they work with universities to maintain FERPA compliance and the like, and they do integrate with most LMSes, you lose some control over the raw files), and the free versions suppress a lot of features and can't be used by very many people at a single institution.

A couple of anecdotes about my own experience:

• While in graduate school, I worked closely with one of the faculty teaching precalculus. Most semesters, he was assigned three sections of 3-400 students each (for a total of around 1000 students). Creating the exams for printing takes maybe an extra 10-15 minutes over the usual prep time, and we could usually get all of the exams de-stapled, scanned, and uploaded in about an hour.

• At my current institution, a lot of the instruction I do is remote (we have classrooms at nine locations spread across our service area; it is not uncommon for me to have students in four or five different classrooms, all at the same time). When I proctor exams, I have my students upload the work themselves (which also ensures that exams are correctly associated with students). Granted, my current classes are much smaller (typically 10–20 students per section make it to the final), but the remote nature of instruction makes these online services invaluable (the alternative is that they are mailed to me via the campus mail system, or students email me exams).

---

NB: I know this answer looks spammy, but I genuinely do not work for either organization, nor have I been paid to advertise either. I have used both systems, and really like not having to work with paper exams anymore.

Answer 4

About four times per year, after correcting them, we had to sort 600+ exams by student numbers, which was a 6 digit number given consecutively to all students at enrolment, so kind of the worst case, since it is not equidistributed in the first digits, and also has unpredictable gaps. Still I think over time we got quite good at it.

For me it has always been practical to first do a bin sort (e.g. by first and possibly second digit) until the individual bins are down to <20 exams and then sort the individual stacks by insertion sort. This has the advantage that both steps can be distributed to multiple people (just remember to combine multiple stacks belonging to the same bin before doing the insertion part).

One important thing though is that the sort key should be clearly visible at the margin, so the insertion step can be done while only slightly fanning the stack.

Answer 5

I suggest starting with a small table and a large floor area. Sort by the first letter of the name into piles on the floor, grouping rare letters (so at least Q in with P and WXYZ together for typical British surnames, which are what I know best). You can reach a larger area on the floor than at any typical table anyway.

This is an intuitive way to divide them into bins.

Then each pile should be quite easily sortable by whatever method you choose.

---

Applying a little Python and curiosity to the problem, and using this list of the top 500 surnames in England and Wales (which accounts for just under 40% of people's surnames) I suggest grouping DE, KL, NO, PQ, TUV, and XYZ for a manageable total of 18 piles, adding up to 0.2--4.2% of surnames based on that list.

Making the massive assumption that the long tail of surnames has the same distribution of first letters, you would have something like 0.5 (XYZ)--10.5%(W) of your scripts in each pile. W, B, H, and S are then your biggest piles, in that order. These may need further sorting in a big cohort, noting that the distribution of second letters is far more restricted (e.g. anything other than a vowel, H, or R is highly unlikely after W with similar patterns for the other common first letters, so this 2nd pass would result in less than 10 extra piles at a time).

You could then insertion sort each pile before stacking them in order. In a small cohort (or for rare letters in a larger one) you may get away with no further sorting, and rely on searching a small disordered set as required. This latter approach is sometimes taken in bookshops, where a full author-alphabetical sort is too time-consuming; it's only moderately annoying to those browsing.

Answer 6

I use a set of folders (like this):

https://www.amazon.com/Expanding-Multi-Color-Accordion-Organizer-Expandable/dp/B075F1N2DM/ (Can kludge your own also...a milk crate works OK. Or use a filing drawer, that is low enough).

I find myself able to file papers alpha within each letter folder as I file by letter. But you could go back later if you prefer. This is helped if you have the name field, printed in a prominent location (and last name, first name ordered prompts).

Answer 7

I think that Quicksort is very suitable for working by hand. It's reasonably expensive in space (you need a largeish table), but takes only $O(n\log n)$ comparisons on average, which is pretty good.

1. Put an arbitrary paper (eg, the top one) in the middle of the table (the ‘pivot’), and form a pile on the left of all those ordered before that one, and on the right a pile of all those ordered after.
2. Recurse.
3. When you end up with a pile containing only a few papers to sort – say half-a-dozen – sort them in-hand.
4. When you have two sorted piles separated by a pivot, combine them into a single one by stacking left-pile above pivot above right-pile. You now have a larger sorted pile.

It's significantly easier to do than to explain. It's also highly parallelisable, in the sense that, while one person is working on left-pile, someone else can be working the same process completely independently on right-pile.

Just don't anyone sneeze....

Answer 8

For the case when the order key is a natural number: use a jig and a hole punch to punch each paper's key into the top of the paper in binary. Encode a 1 by punching a single hole a short distance from the top edge of the paper, and a 0 by making two overlapping punches so that the "hole" extends to the top edge. The punches for each bit position should be in the same place on each paper, and the next step will probably be easier if they're all generally towards the top-middle.

Then, stack the papers up and put a needle through the least-significant bit hole. Lift the needle up so that the papers with a 1 in the LSB come with it, and the papers with a 0 are left behind. Slide the "1" papers off of the needle and stack them neatly behind the "0" papers, then repeat with the next-more-significant bit.

After you've done this for the most-significant bit, the papers will be in order. This is, of course, radix sort.

The hole-punching phase is O(n log m) operations, where n is the number of papers and m is the number of possible keys. The select-and-restack phase is O(log m) operations.

In the case where the papers are numbered sequentially 1 to n, this simplifies to O(n log n) for the first phase and O(log n) for the second phase.

In the case where the keys are arbitrary and non-sequential, but they're drawn from some finite set that can be considered a priori fixed, then this simplifies to O(n) for the first phase and O(1) for the second phase.

Answer 9

I find it best to sit on the floor in my living room, where there is plenty of space. Then I distribute the scripts into about 20 piles in a circle around me according to the initial digits of the registration number. Then I sort the piles individually and finally combine them. I think it would be significantly slower and less convenient to use a table.

Answer 10

Consider radix sort when you have a numerical student ID.

Answer 11

I don't sort my exam papers manually. Instead, I use GradeScope.

Before the exam, I design the papers so that students know exactly where to write their answers, by providing designated boxes for them. After the exam, I scan all the papers and upload them to GradeScope.

This method has several advantages. One of the most significant benefits is the ability to hire someone to help grade the exams remotely. It makes the process much easier, especially for grading objective questions like multiple choice or numerical answer questions. Further more, I can synchronize the grades to Canvas so I don't have to manually input them.