KnowledgeMadeFun, home

Lesson · Grade 6 · Applied Design, Skills and Technologies

Sorting and Searching: Selection Sort and Binary Search

  • Grade 6
  • Applied Design, Skills and Technologies
  • 1 min 24 s
  • British Columbia
  • BC6-AD-03

Seven mixed-up cards, each as tall as its number, are sorted with selection sort: each round, the smallest card left moves to the next place in a sorted row. Binary search then finds the card 57 in only 3 checks by always checking the middle and dropping the side that can't hold it, compared with 5 checks going one by one, and the video shows that this only works because the list is sorted.

Concept: Sorting and searching: two classic algorithms

Anyone can watch two lessons on the website without an account. Signing in is free, no payment and no card, and opens three a day; Plus has no limit.

Loading

Share to Google Classroom

In one sentence

The question this lesson answers

How can we sort these cards, and then find one card fast?

Two classic algorithms help: first selection sort, then binary search.

Transcript

What the lesson says

How can we sort these cards, and then find one card fast?

Two classic algorithms help: first selection sort, then binary search.

Selection sort looks at every card to find the smallest one.

It moves that card to the first place in a new sorted row.

Then it repeats with the cards that are left, one card at a time.

Now every card is sorted, from smallest to largest.

Now let's find the card with 57 on it.

Binary search checks the middle card first.

42 is less than 57, so we drop 42 and the cards on its left.

The middle of the cards that are left is 64.

64 is more than 57, so we drop 64 and the card on its right.

We check the last card left, and it is 57: found in just 3 checks.

Checking one by one from the left would take 5 checks.

Binary search only works on a sorted list.

Sort first, then search by checking the middle each time.

Curriculum

Where this fits

British Columbia, Grade 6

Applied Design, Skills and Technologies, Computational thinking: simple algorithms that reflect computational thinkingBC6-AD-03

Previous: Secret codes: the Caesar shift cipherNext: Flow Charts: Drawing the Steps of a Plan

The outcomes and strands follow the British Columbia curriculum.

Keep going

More on this topic