Searching & Sorting

Question 1

What is Linear Search?
Advantages: simple to understand, easy to code
Disadvantages: Can take a long time if the list is long (or if item is at the end or not in the list)

Answer 1

Linear Search uses a FOR loop to compare each item in a list to the target number until the target number is found or it reaches the end of the list.
The numbers do not need to be sorted.

Question 2

What is Binary Search?
Advantages: Much quicker than Linear Search
Disadvantages: List has to be sorted.

Answer 2

Binary Search finds a number in a SORTED array by repeatedly decreasing the search range. It selects the middle item of the list and compares it to the target number. If the target number is higher than the middle item, than all smaller numbers are removed. If the target number is lower than the middle item, than all larger numbers are removed. This continues until the number is found or the search range is empty.

Question 3

What is Bubble Sort?
Advantages: Doesn’t create new lists, uses less memory, easier to code than Merge Sort
Disadvantages: Inefficent & slow because only two numbers are being compared at a time.

Answer 3

Bubble Sort compares the two consecutive items in the list. If the 1st one is greater they swap, if the 2nd one is greater, they stay the same. This continues with all elements until the last element, where the last swapped number is “put away” and will not be compared anymore.
These rounds continue until there is one round where no swaps take place.

Question 4

What is Merge Sort?
Advantages: Faster because works in parallel
Disadvantages: Takes up a lot of memory, harder to code

Answer 4

Merge Sort splits the list into halves until the list is in only pairs or solo items. Then you recombine the numbers by comparing them and swapping them if the number on the left is greater. This continues until the list is recombined. It is quicker than Bubble sort because it can be split and recombined in parallel.
https://www.youtube.com/watch?v=5Z9dn2WTg9o