Scribd
Upload
101 views5 pages

Sorting and Searching Algorithms Homework

The document provides instructions for several homework tasks involving sorting and searching algorithms: 1. Perform a merge sort on dog breed data and state the total number of merges and new lists created. 2. Perform a merge sort on word data and show split or merged lists. 3. Show the passes of bubble sort to sort an array from 22,4,13,9,17,1 to 1,4,9,13,17,22. 4. Perform a merge sort on the array [6,3,9,2,7] and show all stages. 5. Identify the search method in pseudocode as linear search, describe its inputs/outputs, and suggest

Uploaded by

Dylan Thornton
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
101 views5 pages

Sorting and Searching Algorithms Homework

The document provides instructions for several homework tasks involving sorting and searching algorithms: 1. Perform a merge sort on dog breed data and state the total number of merges and new lists created. 2. Perform a merge sort on word data and show split or merged lists. 3. Show the passes of bubble sort to sort an array from 22,4,13,9,17,1 to 1,4,9,13,17,22. 4. Perform a merge sort on the array [6,3,9,2,7] and show all stages. 5. Identify the search method in pseudocode as linear search, describe its inputs/outputs, and suggest

Uploaded by

Dylan Thornton
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Homework due on 14th April 2021

Task 1 . Dog breeds


Ayuk has collected data about the different breeds of dog he has seen in his area, for a local animal
charity. A sample of data is shown in Figure 1.

Poodle Bulldog Maltese Pug Sheltie Boxer Husky

Figure 1

Perform a merge sort on the data shown in Figure 1 by filling in the table below. A row should show
each pair of lists that have been merged together.

The first stages of splitting each item into a list of its own has already been done, and the first row of
merges has been completed for you.

Sheltie Bulldog Maltese Pug Poodle Husky Boxer

Bulldog Sheltie Maltese Pug Husky Poodle Boxer

State the total number of merges that took place when executing a merge sort on the data shown in
Figure 1.

State the number of new lists that were created during the merge part of the algorithm.

Page 1
Task 2 . Crossword
Jennifer is developing a program that randomly generates a crossword based on a database of words.
She is currently writing a script to check all the four-letter words. A sample of data is shown in
Figure 2.

Peak Tech Holy Film Seen Neck Pace Bulk Moon

Figure 2

Perform a merge sort on the data shown in Figure 2 by filling in the table below. A row should either
show each list that has been split in half, or each pair of lists that has been merged together.

Peak Tech Holy Film Seen Neck Pace Bulk Moon

Page 2
Task 3 . Sort
Show the different passes when the bubble sort is applied to sort this simple array from:

22 4 13 9 17 1
to
1 4 9 13 17 22

Perform a merge sort using the data array [6, 3, 9, 2, 7], ensuring that you show all the stages in the
process.

Page 3
Task 4 . Search
Samira is writing a simple program to allow a user to enter a name to be searched in an array. Here is
the pseudocode for the algorithm she wants to use

SET arr TO [‘Jonny’, ‘Debra’, ‘Adam’, ‘Simon’, ‘Emily’, ‘Kate’]


SUBROUTINE searchStudent(arr)
RECEIVE n FROM (STRING) KEYBOARD
SET found TO FALSE
SET index TO 0
WHILE index < LEN(arr)
IF arr[index]=n THEN
SET found TO TRUE
END IF
SET index TO index + 1
END WHILE
RETURN found
END SUBROUTINE

What type of search is being used?

Describe the algorithm, in terms of its inputs and outputs. What does it do?

The algorithm could be amended to be more efficient. State which line of the algorithm could be
changed and explain how the change will make the algorithm more efficient.

Page 4
Jack has been given homework to write an algorithm to search a variety of small arrays. Which search
method would be most suitable for use with this array, and why?
[2, 6, 9, 12, 23, 41, 76, 84, 92]

Page 5

You might also like