Topic 4 (Searching and Sorting)

Question 1

Linear Search

Answer 1

Just going through an array in a sequential manner to search for a particular value

Question 2

Perfect IB response in “Outline the steps involved in performing a binary search on an array of ascending number”

Answer 2

• Find the midpoint value between the value of the first index (LOW) and the value of the last index (HI)
• If the array value at midpoint equals the search value, then the search value is found
• If the search value is greater than the array value at midpoint, then the new LOW becomes midpoint + 1
• Else if the search value is less than array value at midpoint, then the new HI becomes midpoint - 1
• Repeat until search value is found

Question 3

Number of comparisons worst case scenario in linear search and binary search

Answer 3

Where N is the length of the array

linear:
N

binary search:
log(base 2)(N)

Question 4

Bubble Sort

Answer 4

In an array, it will check adjacent values and swap if needed. This will bubble up one value to the top (highest or lowest depending on sorting for ascending or descending)

This is one pass. The bubble sort will do more passes until there are no swaps detected.

The values that have been bubbled to the top are ignored for subsequent passes.

Question 5

Selection Sort

Answer 5

For each pass, it goes through the unsorted section of the array to find the minimum value (for ascending order). This minimum value gets swapped with the value at the first unsorted index.

After this swap, the first unsorted index now becomes part of the sorted section of the array. The sorted section grows by one element.

This is one pass, there will be array size - 1 passes.

For subsequent passes, the sorted section of the array is ignored since those elements are already in their correct positions.