1 of 20

Topic 4

Programming

IB Computer Science

Part 3

The British International School, Istanbul

2 of 20

Intro

  • Searching (Linear Search, Binary Search)
    • Explanation
    • Code
    • Sample IB Question
  • Linear Search vs. Binary Search
  • Sorting (Bubble Sort, Selection Sort)
    • Explanation
    • Code
    • Sample IB Question
  • Bubble Sort vs. Selection Sort
  • Channel Updates

The British International School, Istanbul

3 of 20

What do you need to know for the IB exam?

  • How to explain all 4 algorithms
  • How to code all 4 algorithms (more common on HL exam)
  • Ability to use binary search
  • Linear vs. Binary Search (Similarities and Differences)
  • Bubble Sort vs. Selection Sort (Similarities and Differences)

The British International School, Istanbul

4 of 20

Linear Search

nums = [31, 54, 67, 29, 51, 61, 23, 35]

The British International School, Istanbul

5 of 20

Binary Search (Example 1)

nums = [23, 29, 31, 35, 51, 54, 61, 67]

The British International School, Istanbul

6 of 20

Binary Search (Example 2)

nums = [23, 29, 31, 35, 54, 61, 67]

The British International School, Istanbul

7 of 20

Binary Search (Example 3)

nums = [23, 29, 31, 35, 54, 61, 67, 73, 77, 81, 99]

The British International School, Istanbul

8 of 20

Binary Search (Approaching the Code)

nums = [23, 29, 31, 35, 54, 61, 67]

The British International School, Istanbul

9 of 20

The British International School, Istanbul

10 of 20

Linear Search vs. Binary Search

Feature

Linear Search

Binary Search

Search Direction

Sequential

Divides arrays into halves

Prerequisites

None

Array must be sorted

Practical Usage

Small arrays or unsorted data

Large and sorted

# of Comparisons (Best Case)

1 time

1 time

# of Comparisons (Worst Case)

N, where N is the length of the array

log2(N) where N is the length of the array

The British International School, Istanbul

11 of 20

Bubble Sort

nums = [31, 54, 67, 29, 51, 61, 23, 35]

The British International School, Istanbul

12 of 20

Bubble Sort (Approaching the Code)

nums = [31, 54, 67, 29, 51, 61, 23, 35]

The British International School, Istanbul

13 of 20

Bubble Sort Basic Tasks

  1. Code a bubble sort.
  2. Describe how a bubble sort would be performed.

The British International School, Istanbul

14 of 20

Selection Sort

nums = [31, 54, 67, 29, 51, 61, 23, 35]

The British International School, Istanbul

15 of 20

Selection Sort (Approaching the Code)

nums = [31, 54, 67, 29, 51, 61, 23, 35]

The British International School, Istanbul

16 of 20

Selection Sort Basic Tasks

  1. Code a selection sort.
  2. Describe how a selection sort would be performed.

The British International School, Istanbul

17 of 20

Bubble Sort vs. Selection Sort

Feature

Bubble Sort

Selection Sort

Methodology

Compare adjacent values and swap the bigger with the small or vice-versa; Repeat N times

Divide array into sorted and unsorted portions; find the maximum (or minimum) in unsorted, add to sorted portion and remove from unsorted portion.

# of Swaps

Each pass through an array leads to many swaps (less efficient)

Each pass through an array leads to one swap

The British International School, Istanbul

18 of 20

The British International School, Istanbul

19 of 20

The British International School, Istanbul

20 of 20

The British International School, Istanbul