computational thinking searching and sorting algorithms

Solving problems that can be implemented by a computer system is known as computational thinking.

Abstraction is the process of removing unnecessary details of a problem to focus on the important features to implement in a solution.

Decomposition is the process of breaking down a large problem into a set of smaller problems to make the problem easier to solve.

Algorithmic thinking is the process of creating step-by-step instructions in order to produce a solution to a problem.

True. Algorithmic thinking requires the use of abstraction and decomposition to identify each individual step.

True. Following a recipe is an example of algorithmic thinking, where if the recipe is followed precisely it should lead to the desired outcome.

True. Travellers do not need to know the geographical layout of the routes, only that getting on at stop A will eventually transport you to stop B

True. Algorithmic thinking takes practise, so the more you do, the easier it will become!

The three main principles of computational thinking are:

Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets.

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 the value is not there.

The middle value/midpoint is the value identified in the middle of the dataset that is being searched during a binary search.

To perform a binary search the data must be in order!

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.

Binary search is fast for large datasets.

Linear search works on unsorted datasets.

A disadvantage of binary search is that the dataset must be in order and it is more complex to implement than linear search.

A disadvantage of linear search is that it is slow for large datasets and inefficient, starting at the beginning each time.

17 5, 14, 17, 21, 22, 28 midpoint = lowerbound (0) + upperbound (5) // 2

Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets.

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 in a bubble sort is called a 'pass'.

A bubble sort is finished when there are no more swaps to make.

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

Divide is splitting the dataset into individual datasets by repeatedly splitting the dataset in half during a merge sort.

Conquer is merging pairs of sub-datasets together by comparing the first value in each dataset during a merge sort.

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.

True. In an insertion sort, values in the dataset can move as many places as they need.