9.1 Python and Searching & Sorting Flashcards
Algorithm
Step by step instructions to solve a problem
Searching
Finding a specific value / item within a list of data
Sorting
Arranging a set of data in a certain order
Linear Search
Searching through a set of data by looking at each item one by one.
Binary Search
A searching algorithm which only works if data is sorted in order. It works by repeatedly ignoring half of the data until it homes in on the value it’s looking for.
Bubble Sort
A sorting algorithm that goes through a list of data, swapping values where necessary, until each value is in order
Insertion Sort
A sorting algorithm that creates two lists, and ordered and unordered one. It then inserts the unordered list into the order list one item at a time until the unordered list is empty.
Merge Sort
A sorting algorithm that splits an unordered list into single items then sorts them into groups of two items. It repeats sorting two lists together until there is a single sorted list.
Computational Thinking
Using logical problem solving skills to solve problems
Which is the simplest searching algorithm?
Linear Search
What does the list have to be in order for binary search to work?
In order
Which searching algorithm starts in the middle of the list?
Binary Search
Where does a linear search start?
At the start
When performing a linear search, what would be the worst case scenario for a list that has 100 items in it?
100
Which sorting algorithm starts by comparing the first two items?
Bubble Sort
Which sorting algorithm starts by splitting the list into individual lists?
Merge sort
Which sorting algorithm starts by creating a sorted and unsorted list?
Insertion Sort
What command word is used in Python to display text on the screen?
In Python, what number does a list start at?
0
As well as IF, what else can you have?
if, elif, else
You always need a colon at the end of an IF statement.
True
How does Binary Search work?
List must be in order
1. Find middle value
2. Is num = to target
-yes: target found
3. -No: Is your target greater than the middle num?
-Yes: discard left
-No: discard right
How does Linear Search Work?
- Check number
- Is it = to target
-yes: target found - -No: Are there any nums left
-Yes: Check nums again
-No: Target not in list
