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

Answer 15

Data = (1,2,3,4,5(MB),6,7,8,9)
Search Value = 8
Compare 8 to 5 (MB) Not a Match
8>5 so discard the lower side
go to the upper side
Compare 8 to 8(MB) Match item found

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

Question 18

What are the advantages of a binary search?

Answer 18

• More efficient because half of the data set is discarded after each pass/search
• Works better with a big data set as less comparisons will be needed

Question 19

What are the disadvantages of a binary search?

Answer 19

• Data has to be sorted
• Inefficient when searching for the first item

Question 20

What are the advantages of a linear search?

Answer 20

• Works well on sorted data set
• Efficient when search item is at the front of the list

Question 21

What are the disadvantages of a linear search?

Answer 21

• Not efficient with a large data set