7.3 Searching and sorting algorithms

Question 1

Searching algorithms

Answer 1

Searching algorithms are precise step-by-step instructions that a computer can follow to e fficiently locate speci fic data in massive datasets
Two common searching algorithms are:
Binary search
Linear search

Question 2

Binary search

Answer 2

A binary search keeps halving a dataset by comparing the target value with the middle value, going left if smaller, right if bigger, until it finds the value or realises it’s not there.
To perform a binary search the data must be in order.
A binary search can be performed on datasets containing number or words.
Searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet instead of numerical size.

Question 3

Linear search

Answer 3

A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked.
A linear search can be performed even if the values are not in order.

Question 4

Advantages and disadvantages of a binary search

Answer 4

Advantages - Fast for large datasets.
E fficient for repeated searches.

Disadvantages - Dataset must be in order.
More complex to implement.

Question 5

Advantages and disadvantages of a linear search

Answer 5

Advantages - Works on unsorted datasets.
Faster (than binary) on very small datasets.
Simple to understand and implement.

Disadvantages - slow for large datasets.
Inefficient, starts at the beginning each time.

Question 6

Sorting algorithms

Answer 6

Sorting algorithms are precise step-by-step instructions that a computer can follow to sort data in massive datasets e fficiently.
Three common sorting algorithms are:
Bubb
le sort
Merge sort
Insertion sort

Question 7

Bubble sort

Answer 7

A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in pairs and swaps them if they are not in the correct order.
One full run of comparisons from beginning to end is called a pass, a bubble sort may require multiple passes to sort the dataset.
The algorithm is finished when there are no more swaps to make.

Question 8

Merge sort

Answer 8

A merge sort is a sorting algorithm that uses the divide and conquer strategy of dividing a dataset into a smaller sub-datasets and merging them back together the correct order.

Question 9

Insertion sort

Answer 9

The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list.
This process repeats until all items are in the correct position.
Values in the dataset can move as many places as they need.