We look with the kids at what sorting
is, what it is for, by what criteria can one sort things, and
different sorting algorithms (selection, insertion and bubble sort)
Preparation
1. Have several sets of objects that
can be sorted by various criteria. Each object should be on a
separate card. For example:  Numbers
 Dots representing numbers
 Squares with different degree of
redness (whitepink > bright red)
 Shapes with different degrees of
roundness (flat oval > perfect circle)
 Smileys (angry > happy)
At the end of this document there are attachments that you can print and distribute among kids
2. Have several sets of pictures (one
set on one sheet of paper), to show kids examples of how to sort by
various criteria, for example:  Tiger, mouse, cat
 Sun, earth, moon
 Grapefruit, orange, lemon
 Motorcycle, car, bus, plain, boat
 Piano,
drum fluite
 Lamp,
candle, fire, sun
 Chair,
Sofa, Carseat
 Pictures of somebody waking up, brushing teeth, having breakfast
3. Be clear about various sorting
algorithms:
 Selection sort: find the
biggest, put first in the resulting list, find the second biggest,
put next in the resulting list, etc.
 Insertion sort: take the
first element from the list, put it in the resulting sorted list.
Take the next element and insert it into the right place in the
resulting list. Continue for every element from the original list.
 Bubble sort: swap adjucent
elements if the larger element is on the right to the smaller
element. The big numbers “bubble up” to the head of the list,
hence bubble sort.
For older (elementary school and up)
kids try other sorting algorithms:
 Merge sort.
Split into smaller groups, sort each group, then merge the sorted
groups.
 Bucket sort. If numbers 1N are sorted, create placeholders for every number. In this case sorting is just running to the placeholder where you belong. This is a good sorting algorithm if there are duplicate numbers.
Resources Bring  a timer  to time different ways of sorting
 a visual display with sticks of different height, to demonstrate different sorting ways to the kids.
 sets of pictures (see above)
 sets of cards  numbers, dots, ovals, red shades, smileys (see above)
Presentation
1.
Why does computer care about sorting?
Computer
likes things in order. If everything is in order, it's easy to find
them.
Aks
kids if they keep their toys in order, and vice versa, if they
misplace a toy, how hard is it to find it?
+++ In addition you may talk about why people sort. Here are some examples:  To find fast (page on a book, person in an ordered list)
 To find the best match (what size of the bus is good to transport 20 kids)
 To know which elements are near each other (whose birthday is next, which birthdays are adjacent, what activity to do next)
 To know the first and the last elements (most favorite toy to play with, least favorite toy to give away)
2.
How do we sort?
Put
several sticks of various height in front of the kids.
In
order to sort we need to compare two things.
Using
selection sort arrange sticks in order  Find the largest stick, move
it away, then put next to it the second largest, etc. Talk through
the whole process.
3.
Ordering by various criteria
Now,
ordering by size / length is not the only way to order things. We can
order by ... Redness!
Have
the cards ready with various shades of red. This time choose a group
of kids and give a card to each kid. Sort the kids using insertion
sort, by picking the first kid and moving her away – she will make
up the sorting list, then pick the next kid and have her “insert”
herself into the ordered line based on her card. Once the kids are
done have them raise their cards so that everybody see them ordered.
Now,
let's order by ... Roundness!
Do
the same with a different group of kids and the cards of different
roundness (flat oval till perfect circle). Sort the kids using bubble
sort – have the kids with the rounder circle swap if they are out
of order.
You
see, the rounder shape bubbles up, like a balloon, and the flatter
shape goes down.
Again,
have the kids raise their cards so that everybody sees that they are
sorted
But
wait, you can even order by ... happiness!
Distribute
a set of smileys – from angry to happy and have the last group of
kids sort them using selection sort – have the last child approach
every other child and whoever has happier face continues to go
through the kids, while the “angrier” one stays in the place of
the happy one. Once the happiest is found, place him on the side and
have the kids find the “happiest” among those left.
At
this point all kids should try sorting, have them seated.
4.
Show example of ordering by various criteria, as well as ordering the
same things differently.
Tiger, mouse, cat (order by size) Sun, earth, moon (order by size, or by closeness to the
Earth) Grapefruit, orange, lemon (order by size or by sourness) Motorcycle, car, bus, plain, boat (order
by number of wheels, or by number of people that can be transported) Piano,
drum fluite (Order
by loudness) Lamp,
candle, fire, sun (Order
by brightness) Chair,
Sofa, Carseat (Order
by size, or softness)
Wake up, brush teeth, eath breakfast (Order by time)
5.
What can't you sort?
This
is a surprisingly hard question, because kids can come up with
sorting everything.
I
tried
And
they sorted by “scariness”
But
the idea is, in order to sort, you need to compare, and if the things
can not be compared they can not be sorted.
+++ You can bring up that one can't compare apples and oranges, but the kids may come up with dozens of ways to compare apples and oranges (roundess, sweetness, orangeness, etc), so it's a slippery slope
6.
Sorting competition.
(You'll
need teacher assistance with this one)
It
is very important to sort fast. Now we are going to play a game.
Split
kids into two groups. One groups gets unsorted set of numbers, the
other group – dots representing numbers.
We
have two groups. Let's see which group will sort faster.
Create
a sence of urgency. Start counting down and have the kids sort
themselves. Initially, if the size of the group is large, the kids
are likely to get confused. Some of them will not show initiative and
would stand there expecting others to sort them.
Don't
help the kids right away, let them realize that selfsorting is not
such an easy thing to do.
You
see, it' is important to agree on a sorting algorithm before you
sort, this will avoid the confusion. Explain
the kids the rules of a sorting algorithm you picked and have them
sorting by following the rules. Help the kids if they are young or if
the group is large (over 67 people)
+++ If kids are old enough to get a handle of it themselves and learn to sort themselves efficiently, time different sorting algorithms. Discuss advantages of "parallel sorting"  for example, in Bubble Sort, kids can swap in parallel Celebrate
a friendly tie. Switch cards – have the group that had the numbers
have the dots and vice versa.
7. Finish with the story.
I have a dentist. His name is John Solomon, like salmon. He is a really really good dentist, he has been dentist for 20 years. Once I was sitting in his dentist chair while he looked at my teeth and he told me this story. When John Solomon was very young and just started being a dentist he had very few patients. As you may know every patient has a folder where the dentist keeps information about his teeth. So John had a folder for every patient and put these folders on top of each other. Whenever a patient came, John had to look through all these folders to find the folder with the patient's name. This was okay as long as John had a few patients, but as John Solomon started having more and more patients his stack of folders went higher and higher. It was so high at some point that John had to use a ladder to look on top of the stack! And of course it would take John Solomon longer and longer to find the right folder. Once it was late at night and John was about to go home and a man came, one of his patients. The man had terrible terrible tooth ache. "Do something fast!" the man yelled. But before doing anything John had to find the patient's folder, to know about his teeth. "Just one minute" John said as he was going through the stack that went up the ceiling. One minute went by, then another, than 10 more minutes. "I am in such a pain, help me please, doctor!" The pain was such that the patient was crying like a baby. John really wanted to help him but he couldn't find the folder, he went over only half of his stack. At some point the patient grew so impatient that he got up and ran away. John felt SOOOO bad, for not being able to help his patient because he had to look for his folder for so long, that he decided to do something about it. And this is what he did: He created shelves with letters of alphabet. And inside each shelf he would put the folders with the names starting with this letter. Since then it takes John less than a minute to find the right folder and no other patient ever left him again.

Updating...
Misha Leder, Feb 3, 2010, 6:52 PM
Misha Leder, Feb 3, 2010, 6:52 PM
Misha Leder, Feb 3, 2010, 6:53 PM
Misha Leder, Feb 3, 2010, 6:53 PM
Misha Leder, Feb 3, 2010, 8:31 PM
