Presentation 4: Sorting

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 (white-pink -> 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 1-N 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

• • Policeman, pinecone, dream, wheel

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 self-sorting 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 6-7 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.