2.1.3 Searching and Sorting Algorithms

Question 1

Standard Algorithm

Answer 1

Pre loaded to perform a basic task

Sorting and Searching algorithm

Question 2

Examples of Sorting algorithms

Answer 2

Sorting - Bubble sort, Merge sort, Insertion sort

Question 3

What is Bubble sort?

Answer 3

Each item in a list is compared to the next item. If a swap is needed they will swap. Continue to end of list for a pass

Question 4

Example of Bubble Sort

Data = 5,3,4,7,6,9

Answer 4

Data = (5,3,4,7,6,9)
3,5,4,7,6,9
3,4,5,7,6,9
3,4,5,6,7,9
Pass 1

Question 5

Example of Bubble sort with 2 passes

Data = Dan,Ben,Bob,Tom,Sam,Liz

Answer 5

Data = (Dan,Ben,Bob,Tom,Sam,Liz)
Ben, Dan, Bob, Tom, Sam, Liz

Ben, Bob, Dan, Tom, Sam, Liz

Ben, Bob, Dan, Sam, Tom, Liz

Ben, Bob, Dan, Sam, Liz, Tom

Pass 1

Ben, Bob, Dan, Liz, Sam, Tom

Pass 2

Question 6

What is a merge sort?

Answer 6

The data is broken down, broken down again until single values. Values will be merged into pairs while sorting

Question 7

Example of Merge sort
Data = 10,1,13,24,7,5,36,25

Answer 7

Data = 10,1,13,24,7,5,36,25
10,1,13,24 7,5,36,25
10,1 13,24 7,5 36,25
10 1 13 24 7 5 36 25
1,10 13,24 5,7 25,36
1,10,13,24 5,7,25,36
1,5,7,10,13,24,25,36

Question 8

What is an Insertion algorithm?

Answer 8

Value will be removed from an unsorted list and placed in the correct location in a sorted list

Question 9

Example of Insertion sort

Data = 15,12,13,10,9,14

Answer 9

Data = (15,12,13,10,9,14)
Sorted: (15) 12,13,10,9,14
(12,15) 13,10,9,14
(12,13,15) 10,9,14
(10,12,13,15) 9,14
(9,10,12,13,15) 14
(9,10,12,13,14,15)

Question 10

Examples of Searching algorithms

Answer 10

Searching - Linear search and Binary search

Question 11

What is a Linear Search?

Answer 11

Starting from the beginning of the list, compare a search value to the first item in the list, continue comparing in order until item is found or not found

Question 12

Example of Linear search

Data = Ben,Bob,Tom,Sam,Dan,Ali

Answer 12

Data = (Ben,Bob,Tom,Sam,Dan,Ali)
Search Value = Tom

Compare Tom to Ben (Index 0) No Match

Compare Tom to Bob (Index 1) No Match

Compare Tom to Tom (Index 2) Found

Question 13

Example of Linear search

Data = 5,3,4

Answer 13

Data = (5,3,4)
Search Value = 10

Compare 10 to 5 (Index 0) No Match

Compare 10 to 3 (Index 1) No Match

Compare 10 to 4 (Index 2) No Match

Item not found

Question 14

What is Binary Search?

Answer 14

• Data has to be sorted
• Set a middle boundary
• Compare search value to middle boundary
• If it’s a match - found
• If less than, Discard the upper side and left
• If more than, Discard the lower side and right
• Repeat the process

Number of values div 2 = Index of MB

Question 15

Example of Binary search

Data = 1,2,3,4,5,6,7,8,9,10,11

Answer 15

Data = (1,2,3,4,5,6,7,8,910,11)

Question 16

What is Div and Mod?

Answer 16

Div: Integer division eg. 15 div 3 (//)

Mod: Modulus, remainder (%)

Question 17

Examples of Mod and Div

Answer 17

12 div 4 = 3
12 mod 4 = 0

10 div 7 = 1
10 mod 7 = 3

12 div 8 = 1
12 mod 8 = 4

13 div 7 = 1
13 mod 7 = 6

15 div 4 = 3
15 mod 4 = 3