Comparing Students

Recall that, in Week 4, we implemented a student in C with:

typedef struct
{
    char *name;
    char *dorm;
}
student;

And recall that, in Week 6, we implemented a student in Python with:

class Student:
    def __init__(self, name, dorm):
        self.name = name
        self.dorm = dorm

Sorting an array of students' names in C or a list of students' names in Python is relatively easy, assuming the names are just strings. But how do you sort an array of student structures in C or a list of Student objects in Python by students' names? Let’s find out.

It turns out that C has support for "function pointers," which are just that, pointers to functions, which means that you can pass one function to another by way of its address in memory. In fact, per http://en.cppreference.com/w/c/algorithm/qsort, C has a function called qsort, declared in stdlib.h, that can sort arrays whose elements have any type, including student. It just needs to know how to order those elements. How? Well, you simply pass to it a "comparison" function whose arguments, a and b, are pointers to two elements of the array. That function must return a negative int if *a should precede *b, a positive int if *a should come after *b, or 0 if *a and *b are equivalent. The arguments to that comparison function have type const void *, wherein const means that the function cannot change their values, and void * means that the arguments themselves can have any type.

While Python doesn’t have pointers, one function can still be passed to another by way of its name. In fact, per https://docs.python.org/3/library/functions.html#sorted, Python has a function called sorted that can sort lists whose elements have any types, including Student. It, too, just needs to be told how to order those elements. How? Well, per https://wiki.python.org/moin/HowTo/Sorting#Key_Functions, you simply pass to it a named parameter called key, the value of which is a "function to be called on each list element prior to making comparisons" that "returns a key to use for sorting purposes." For instance, given a list and a value of str.lower for key, sorted would call str.lower on each element in that list and compare the (lowercase) return values to determine their order.

Similarly in JavaScript can you pass one function to another by way of its name. Per https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort, arrays in JavaScript have a method called sort via which they can be sorted. That method accepts an argument, compareFunction, much like qsort in C.

Answer the below in students.md, students.c, students.py, and students.js.

Questions

1.1 (1 point)

In the prototype for qsort at http://en.cppreference.com/w/c/algorithm/qsort, what does

int (*comp)(const void *, const void *)

represent?

1.2 (2 points)

In the Example at http://en.cppreference.com/w/c/algorithm/qsort#Example, why must a and b be typecast from const void * to const int *?

1.3 (3 points)

Complete the implementation of cmp in students.c in such a way that it sorts the course’s heads by name using strcmp in ASCIIbetical order, per the TODO therein.

1.4 (2 points)

Much like JavaScript, Python has support for anonymous functions, otherwise known as lambda functions, per https://docs.python.org/3/tutorial/controlflow.html#lambda-expressions. Complete the implementation of main in students.py in such a way that it sorts, using a lambda function, the course’s heads by name in ASCIIbetical order, per the TODO therein.

1.5 (3 points)

It turns out that JavaScript can be executed not only client-side (as in browser) but also server-side at a command-line (as in CS50 IDE) thanks to Node.js, a "JavaScript runtime" that can compile and execute JavaScript on a server. For instance, try saving

console.log("hello, world");

in a file called hello.js in CS50 IDE. Then compile and execute it (all at once) by executing

node hello.js

in a terminal window (in the same directory in which you saved the file). You should see a familiar greeting!

Complete the implementation of students.js in such a way that it sorts the course’s heads by name in ASCIIbetical, per the TODO therein.

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long, in minutes, did you spend on this problem’s questions?