Photo AI
An insertion sort is used to put the following words into ascending alphabetical order - OCR - GCSE Computer Science - Question 2 - 2021 - Paper 1
Question 2
An insertion sort is used to put the following words into ascending alphabetical order. pumpkin flour wall house wall (a) Tick (✓) one box in each row to identify ... show full transcript
Worked Solution & Example Answer:An insertion sort is used to put the following words into ascending alphabetical order - OCR - GCSE Computer Science - Question 2 - 2021 - Paper 1
Step 1
Tick (✓) one box in each row to identify whether each statement about the insertion sort is true or false.
Answer
- The list of words is initially split into a sorted set and an unsorted set. False
- The insertion sort uses a divide stage and then a conquer stage. False
- The list of words must be in order before the insertion sort can start. False
- Each word is inserted into the correct place in the array, one by one. True
- The insertion sort will not work because the word "wall" appears twice. False
Step 2
Explain how a binary search would be used to try to find whether the word "house" appears in this list.
Answer
To perform a binary search for the word "house" in the sorted list, follow these steps:
-
Initial Setup: Start with two indices:
lowset to 0 (the first index) andhighset to 4 (the last index). -
Middle Element: Calculate the middle index using the formula:
which results in
mid= 2. -
Comparison: Compare the middle element with "house". The middle element is "pumpkin". Since "pumpkin" is greater than "house", update
hightomid - 1, makinghigh= 1. -
Repeat: Calculate the new
mid: nowmid= 0. The element at index 0 is "flour", which is also less than "house". Updatelowtomid + 1, makinglow= 1. -
Final Comparison: Now,
lowequalshigh, which meanslow= 1. The element at index 1 is "house". Since it matches, the search confirms that "house" is present in the list.