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.pralgaus...@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
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
https://mail.python.org/mailman/listinfo/edu-sig
