human representation of a sorting algorithm

[jwpaine]

I'm going to be having to give a presentation in of my classes on career opportunities in math along with it's applications in computer science (what I am most interested in).

An idea I had was to have 16 participants from the class come down, each person picking up digit printed on pieces of paper; 1 to 16 and then having them perform a human-representation of a sorting algorithm, and in the end having all students end up in the correctly sorted order.

I'm trying to decide on an algorithm to use which will require the students to be more involved in the activity. I was thinking a single file line of students preforming a bubble sort as a lead into me describing how mathematics plays a crucial roll in the development of more efficient algorithms.

I was once a participant of a mergesort demonstration but it's been a number of years and I can't seem to think of an easy way to do it without me performing all the logic myself. I may just end up doing a bubble sort because it's easy and would require every two participants (elements) to perform their own logic.

 

[daon]

Hey,

I'm going to be having to give a presentation in of my classes
on career opportunities in math along with it's applications in computer science (what I am most interested in).

An idea I had was to have 16 participants from the class come down, each
person picking up digit printed on pieces of paper; 1 to 16 and then having them perform a human-representation of a sorting algorithm, and in the end having all
students end up in the correctly sorted order.

I'm trying to decide on an algorithm to use which will require the
students to be more involved in the activity. I was thinking a single
file line of students preforming a bubble sort as a lead into me
describing how mathematics plays a crucial roll in the development of
more efficient algorithms.

I was once a participant of a mergesort demonstration but
it's been a number of years and I can't seem to think of an easy way
to do it without me performing all the logic myself. I may just
end up doing a bubble sort because it's easy and would require every
two participants (elements) to perform their own logic.

Sounds like a speech I shouldn't miss. I have no idea what I'm doing with my life and graduation isn't far off... lol. Anyway...

Personally, I always liked writing partitioning/recursive sorts, but that might cause some headaches for newbie audience members. What you could do is perform a standard n^2 sort using something like "on ith try find biggest in last n-i elements, swap with ith position" and then show how a more efficient algorithm like bubblesort can improve things. Kind of shows how a little mathematics/analysis can save time and money in the computing industry.

 

[jwpaine]

What do you mean by a standard sort? Are you referring to something like a basic Selection Sort?

Like: scan an array of size n elements, find the biggest element and move it to the n - i^th position in the array, where the first scan is the i = 0, the second scan is i = 1

so if we have an array containing 6 integers: {1,2,5,3,9,4} the first pass will identify 9 as the biggest element and move it to the (6 - 0)th place:

the second scan will identify 5 as the largest element, and move it to the (6 - 1)th place so that it is before the 9

That 'sort' of thing?

 

[daon]

Yep, thats exactly what I meant. Bubblesort can be as inefficient as selection sort so it might not be a good idea unless you choose the numbers right. On such a small list Bubble sort should do fine with a random shuffle but its a 50/50 chance to get better or worse than average.

With 16 numbers they should definetly see that something like merge sort is faster than a selection sort. Merge sort is really your best bet to emphasize efficiency since its worst-case is NlogN. The first will be around 132 iterations the second around 64 with an O(NlogN) sort (less with mergesort unless its the worst-case). There are several more but they are less known and might be a pain for the observers and participants.

 

[jwpaine]

Yeah but with a mergesort, I'm going to be having to perform all the logic myself - that's the thing: with a bubblesort the participants (elements) are able to stand in a single file line (array) and turn around to the participent in back of them and then perform their own logic whether or not to switch places -

a mergesort might emphasize efficiency, but it makes me do all the work

 

[daon]

No biggie, Bubblesort can be very efficient too. Just pick a 'realistic' set of numbers if you want. In other words, the 'worst case' scenario with 16 randomly selected integers will happen less than 1% of the time. You might as well tell them to shuffle themselves into any order they'd like. You'd have really bad luck for your participants to assemble into the worst case of {16,15,...,1}. If that happens tell them they're not 'shuffled enough' and to try again .

 

[Denis]

To sort a 16 array in some order takes 120 iterations.
Or n(n - 1) / 2 : n = array size

In Basic (sorting in ascending order):

FOR j = 1 TO n-1
FOR k = j+1 TO n
IF a(j) > a(k) THEN SWAP a(j),a(k)
NEXT k
NEXT j

Hoping that's useful :idea: