CIS 22B - Notes for Wed Oct 04

Announcements and Reminders

  • Check attendance sheet
  • Assignment 2 is due Monday
  • You may request exercise (after due date) and assignment solutions (24 hours after due date)

Sorting

  • Bubble Sort

Algorithm

Repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.

Reference Page
Example Code

How can you make this code more efficient?

Video: Easy Programming - Beginner C++ Tutorial - The Bubble Sort  (11 minutes)

  • Selection Sort
Algorithm

Find the minimum value in the list, swap it with the value in the first position.  Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

Reference Page

Example Code

  • Insertion Sort

Algorithm

Each  element is inserted, one at a time, into the sorted list

Reference Page

Example Code


Searching an array

Sequential search

Binary search


A binary search is a search in which the data is repeatedly split in half  until the search key is found it is determined that the the search value is not present.  The data must be sorted on the search key.

The Game: guess a secret number between 1 and 100.

Reference page

The Code

Videos