Bubble Sort - kimschles/schlesinger-knowledge GitHub Wiki

Number of Students: 80 students 15 legislators

Number of Learning Facilitators: 7 Galvanize Instructors: Sarah, Teddi, Mairin, Anna, Dize, Kim and Martha

? Galvanize Staff Members

Computers can’t do anything without you Being a Computer scientists, software engineers, or web developers is a job you could do. Computer science is approachable

Example of a non-CS algorithm: Making a Peanut Butter and Jelly Sandwich Step 1: Assemble the ingredients: bread, peanut butter, jelly Step 2: Get the kitchen items you need: a plate, a knife, a towel Step 3: Get two pieces of bread Etc….

Discussion Question: What are some other step-by-step processes, or algorithms you use?

(Have participants turn and talk to their neighbor. After enough processing time, cold call on 3-4 students to hear different answers)

Discussion Question: Turn and talk to your neighbor, and explain the term algorithm in your own words.

As a software engineer, you will write code that sorts lists. Today, we are going to learn one of many algorithms that can sort a list of numbers from smallest to largest. The sorting algorithm we are learning today is called ‘Bubble Sort.’

Computers are very literal, and we have to tell them every step to take like the PB&J exercise. So, let’s see how each step Bubble Sort works.

Whole Group Demonstration and Think-Aloud: (Five adults will act out the bubble sort: 4 people holding numbers, and 1 acting as the computer program. One instructor will model and ‘think aloud’ each step)

[7,10, 8, 1] (Note, the order matters for the demo to show 3 different passes)

Step 1: Start at the left side of the list, and compare the first and second numbers. If the two numbers are not in order from smallest to largest, switch the numbers. If they are in order, leave the numbers as they are.

Step 2: Move to the second number in the list. Compare the second and third numbers. If the numbers are not in order from smallest to largest, switch the numbers. If they are in order, leave the numbers as they are.

Step 3: Repeat this process until you’ve evaluated every number in the list.

Step 4: Look at the list. Is it sorted correctly? If not yet, do another ‘pass,’ and continue the list is sorted correctly.

Key Term: Pass- when you’ve evaluated every item in the list.

Small Group Problem Solving: The students will break into small groups led by a Galvanize Instructor. Each group will have a set of numbers printed on individual sheets of paper. The instructor should help organize the girls so that they can

Note: The most important part of the small group activity is that each girl has an opportunity to explain the step-by-step process in their own words. Please ensure that you leave enough time for the students to talk this through with one or two other students.

If you have extra time, please have the students think about this question: Why do you think the algorithm is called Bubble Sort?

Answer: The largest numbers eventually ‘bubble up’ to the right of the list.

Step 2: Move to the second number in the list. Compare the second and third numbers. If the numbers are not in order from smallest to largest, switch the numbers. If they are in order, leave the numbers as they are.

Step 3: Repeat this process until you’ve evaluated every number in the list.

Step 4: Look at the list. Is it sorted correctly? If not yet, do another ‘pass,’ and continue the list is sorted correctly.

[1,2,3] [2,3,1] [3,2,1]

Answer: The edge case is if the smallest number is in the last position in the list. In the event this is true, the number of passes is n-1