2.1 Algorithms Flashcards
Define linear search
A sequence that checks every item in a list 1 by 1 until it finds the desired item.
Define binary search
A sequence that finds the desired item of a list according to the midpoints.
What happens if the midpoint is greater than the desired item?
It scraps the midpoint and the data to its left and checks again.
What happens if the midpoint is smaller than the desired item?
It scraps the midpoint and the data to its right.
Define bubble sort
Bubble sort makes multiple passes through a list. It compares items and changes those that are out of order. Each pass through the list places the next largest value in its proper place.
How are numbers sorted in bubble sort?
Compares 1st 2 items and swaps them if necessary.
Define pass
A full cycle of swapping (doesn’t mean list is sorted).
Define insertion sort
A more efficient version of bubble sort. Each pass would insert each number into its correct place.
How are numbers sorted in insertion sort?
Compares 1st 2 items and inserts the necessary item into its complete correct position rather than swapping them. Has 2 lists, unsorted and sorted.
Where is insertion sort very efficient?
A small data set or where data is mostly sorted.
E.g. a pack of cards.
What is merge sort?
An efficient sequence that divides an unsorted list into sublists with 1 item each and merges the lists together until it has a complete sorted list.
Define computational thinking
Use of computers to solve problems.
Define abstraction
Representing “real world” problems in a computer using variables and symbols and removing unnecessary elements from the problem.
Define decomposition
Breaking down a large problems into smaller sub-problems.
Define algorithmic thinking
Identifying the steps involved in solving a problem.
