Programming with
Data Structures and Algorithms

• Welcome
• README
• Assignments
• Readings
• Software
• Contact
• Credits

Supp 5: Sortacle

When you are testing complex functions, or perhaps even relations (as in the case of this assignment), you will need to put time and effort into building testing oracles. In this assignment, you will develop oracles to test purported sorting algorithms. Countries by medal count, companies by income, students by GPA, the list goes on and on.

The Assignment

Being confident that your software is correct involves more than just writing code you think is right. However, almost no software complex enough to be useful can be proved correct by hand in a reasonable amount of time. Naturally, a computer scientist's solution to this problem is to write automated testing. Your job, in this assignment, is to build an automated testing oracle for a solution to the sorting problem.

Your oracle's job is to generate and feed test inputs to this solution and test the correctness of the output. In the past, you did this by comparing the output to a precomputed correct answer. This assumes two things: that there is only one right answer, and that it is easy for you to find it. In the real world, either or both of these can be false.

Using the following struct where name is a string and age is a number, you will build an oracle for a function sorting lists of people by non-decreasing age.

(define-struct person (name age))

Use the "sort" function in the language to make a correct version called age-sort that takes in a list of people and returns the sorted list. Our sorting functions will use the same contract.

age-sort : (listof person) -> (listof person)

We will be feeding your oracle a multitude of interesting functions, some that are legitimate sorting algorithms, some that are not. Your oracle should only return true for functions that pass all tests.

Input-Output Specification

Each purported solution will return the list of people in a new order; your oracle must determine the functions that consistently return the list sorted by age in a strictly non-decreasing order (eg. 1, 13, 25, 25, 41).

Your assignment has three tasks:

• Write a function named generate-input that (surprise, surprise!) generates input. This function should take an integer length, and return a list of randomly aged people of that length. (You may assume an upper age limit of 150).
  

  generate-input : number -> (listof person)

• Write a function that determines whether the second input is a sorted version of the first.
  

  valid? : (listof person) (listof person) -> boolean

• Using valid? and generate-input (along with any other edge cases you think to include), write a function named oracle that tests whether an algorithm is a valid sorter.
  

  oracle : ((listof: person) -> (listof person)) -> boolean

Remember, an algorithm may sometimes produce a correct solution even if it is an incorrect algorithm. Therefore, your oracle should only return true if an algorithm always sorts correctly (it is up to you to determine the magnitude of "always").

To do well on this assignment, you will want to spend time considering all the different ways that output could be either invalid or inconsistent with the original problem statement. Be thorough! That's the name of the game when testing.

What to turn in:

• A Racket file, sortacle.rkt, containing your implementation.