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@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