[Edu-sig] What to teach: sorting algorithms vs OOP?

[Tobias Kohn]

  Hi Jurgis,

As I had very similar problems in my high school teaching often  
enough, let me add my two cents' worth here.  In contrast to Wes' and  
Kirby's reply, I am focusing much more on the idea of algorithms than  
on the software/programming side, and would advocate to give sorting  
algorithms a fair try ^_^.

I think the first question is really what your curriculum's objective  
is.  If we are talking about computer science, then doing the sorting  
algorithms is probably the right choice.  If it really is about  
programming, then OOP might be an acceptable alternative to consider.   
The tricky part is that programming often comes as part of general  
computer science education, so the disctinction between the two is not  
always that easy.  And if we are talking about computer science as a  
(more or less) mandatory subject for everyone, then please keep in  
mind that you are not training future software engineers, and not  
everyone is becoming a programmer.

Anyway, before teaching sorting algorithms, it might be a good idea to  
think about the reasons for teaching it.  As you have pointed out,  
sorting is available as a builtin function in nearly every programming  
system, and CPython has a very sophisticated implementation, indeed,  
which will almost always be better than what you can do with  
students.  Hence, teaching sorting algorithms can obviously not be  
just about the sorting.

However, one thing you will have used over and over again as a  
programmer is, of course, optimisation.  As programmers, whenever  
possible, we want to come up with an elegant, fast, and efficient  
solution.  I strongly believe, it is this process of optimisation, of  
finding more efficient, and clever solutions, that we should be  
teaching to K-12 students.  And one of the best examples to  
demonstrate this process is through sorting.  Why?  Because the  
students can relate to the task in the first place (the understand the  
problem easily enough), and because we can easily achieve impressive  
speedups with approachable algorithms.

What I want to say is, that directly teaching something like Quicksort  
to K-12 students has no positive effect, whatsoever.  It is just a  
dead piece of code, probably something to be learned for the next  
test, and forgotten just as quickly.  But, if we manage to rather  
focus on the process of starting with a really dumb sorting algorithm,  
and then discuss various approaches, and their limitations, of how we  
can improve it, and make it more efficient, then we get to truly  
engaging lessons.  Hence, teaching sorting is not about sorting,  
really, but about how you can improve the efficiency of a program.

For this reason, I usually start with sorting early on.  Perhaps  
something as simple as taking two values, and returning them in  
ascending order (i. e., `min, max`).  Once you enhance this basic idea  
to three values, the function quickly gets much more complicated, and  
my students tend to write long series of `if`-`elif`-chains, something  
like:
def sort_three(a, b, c):
    if a <= b <= c:
        return a, b, c
    elif a <= c <= b:
        return a, c, b
    elif b <= a <= c:
        return b, a, c
    ...
    
Once you arrive at four values, things turn quickly nasty.  Even with  
the three values above, it becomes hard to reason about the  
reliability of the function.  Have we covered all the cases?  Does it  
return the correct order for every conceivable corner-case?  Which is  
the right branch to be taken if all three values are equal, and where  
(in the code) do we actually test for that?

At this point, the idea of Minsort to the rescue!  Instead of trying  
to cover every case, we try to think of a different approach, where we  
first identify the smallest element.  This might, for instance, look  
as follows.
def sort_three(a, b, c):
    if a <= b and a <= c:
        x = a
        y, z = sort_two(b, c)
    elif b <= a and b <= c:
        x = b
        y, z = sort_two(a, c)
    elif c <= a and c <= b:
        x = c
        y, z = sort_two(a, b)
    return x, y, z

Note that at this point, we have already started to bring in the idea  
of recursion, without actually doing proper recursion.  But  
demonstrating this basic idea in different settings will help us later  
on.

As a next step, we can then go to do the same thing with lists (the  
actual implementation here will vary, depending on what you have  
discussed so far with your students).
def sort(input_list):
    output_list = []
    while len(input_list) > 0:
        x = min(input_list)
        input_list.remove(x)
        output_list.append(x)
    return output_list

One problem that occurs with this implementation is that the original  
list is being destroyed.  So, again, this gives rise to discuss  
several implementation issues.

Finally, depending on what situation you are actually in, you can  
really do both, and cover sorting algorithms, as well as OOP (as Wes  
and Kirby have already pointed out).
 From my experience: in an elective class for 12th graders (who  
already knew the basics of Python programming), I implemented a very  
simple 3D-engine.  To that end, the graphical objects need to be build  
from triangles, and what is more natural than representing these  
triangles as objects?  But, once we start to rotate the camera, so as  
to give a real 3D-impression, we need to make sure that the triangles  
are painted in the correct order: we need to sort them according to  
their depth.  So, sorting does not only come in as quite natural a  
requirement, it is also evident that the sorting needs to be fast,  
because we want to repaint the scene several times every second.
Unfortunately, it took me about half a year to cover this entire  
programme with about two hours each week.  This included, of course, a  
treatment of various projections, matrices, and all the other fun  
stuff.  But it might still give you yet another idea of how to  
approach the subject.

I hope you will find a nice solution to your dilemma.

Cheers,
Tobias

Quoting Jurgis Pralgauskis <jurgis.pralgauskis at gmail.com>:

> Hi,       
>    The dillema I have when teaching:
>     our k12 curricullum of programming is more based on algorithms  
> (math ideas), 
>    but when working as programmer, I see the bigger need of SW  
> architecture knowledge.. 
>     
>     OOP is one big topic, which could replace sorting alg stuff  
> (that I never applied (directly) in this century...). The topics  
> could be integrated in making mini game engine :) 
>     
>    I'd still leave classics of sum, min search, and search in sorted  
> vs non array to get the idea of algorithms.
>
> What are your approaches, if you have programming classes in K12?
>     --
> Jurgis Pralgauskis
> tel: 8-616 77613
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20180815/792f0a1d/attachment.html>