[Year 12 SofDev] Unit 3 Outcome 1

[Glen Turner]

> One thing you could consider is keeping bubble sort in as a means to 
> perform binary searching.  You could technically modify that module in 
> there for first part of the binary search technique.

Would that would confuse students?

Remember that bubble sort makes a pass through the list, swapping the 
first pair it finds which is out of order. Repeat until list sorted 
(roughly n^2 times).

Binary search works very differently, making a probe into the list at the 
midway point, comparing that value with the target and discarding the 
irrelevant half of the list from further consideration. Repeat until 
target value found or list exhausted.

There is a sort based on the binary search; that is Quicksort. It's usual 
to teach binary search first, as then Quicksort is more comprehensible.  
Quicksort is also a great case for using the system sort() library, since 
it is very easily to make implementation errors (see Sedgewick's 
"Algorithms" for a correct implementation, a very large number of 
textbooks stuff up the algorithm [1]). The average performance is roughly 
n.log(n) with a worst case of roughly n^2.

Best wishes,
glen
(not a teacher, a computer science practitioner)

[1] Section 2.3 "Quicksort" <http://algs4.cs.princeton.edu/23quicksort/>
    in
      Robert Sedgewick, Kevin Wayne
      "Algorthims"
      4th ed

-- 
Glen Turner <http://www.gdt.id.au/~gdt/>