# 2.1.3 - Searching and Sorting Algorithms Flashcards

Types of searching algorithms

Linear search and Binary Search

Does the list in a linear search have to be ordered or unordered

It can be either

Does the list in a binary search have to be ordered or unordered

It has to be ordered

How does a linear search work? (3 steps)

- The length of the list is found
- The program searches through the values in order from the start using a counter
- It stops once the required value has been found or the list ends

LESS EFFECTIVE THAN BINARY

Hows does a binary search work? (4 steps)

- Finds the midpoint of the ordered list
- If the midpoint isn’t the required value then it checks if the required value is lower or higher than the midpoint
- If value is higher, it disregards all smaller numbers and if the value is lower, it disregards all larger numbers
- This repeats until the value is found

MORE EFFECTIVE THAN LINEAR

Types of sorting algorithms

- Bubble sort - temp + swaps
- merge sort - sublists
- insertion sort - inserts into correct place

Advantages and disadvantages of bubble sort

- Easy to understand
- However, very slow and inefficient

Advantages and disadvantages of merge sort

- Very quick comparisons - better for use on large data sets than other sorting methods
- Difficult to understand and needs lots of memory

*

Advantages and disadvantages of insertion sort

- Quicker than a bubble sort
- Good for inserting extra data into already sorted lists
- Not efficient when used on large data sets

Similarities of a bubble sort and an insertion sort

- Both less efficient that a merge sort
- Both produce a sorted list
- Both work from left to right’
- Both swap values
- Both have nested loops

Difference between a bubble an insertion sort

- An insertion sort moves the value into its correct postition
- A bubble sort repeatdely swaps values until it is in the correct position

Steps in a merge sort

DIVIDE AND CONQUER

- The list is split into sublist and this repeats until each element has its own sublist (sublist with a length of 1)
- Each pair of adjacent sublists is compared and combined to form an ordered sublist with length 2
- This process is repeated until there is only one list left and the list will be ordered

Steps in a bubble sort

- Start at the fron of the list and compare the two elements
- If they are in the righ order, don’t swap but if they aren’t swap
- Repeat for next 2 elements and repeat until one full pass has been made
- Repeatedly perform passes until a pass has been done and no swaps have been made

Tips to identify the different sorting algos

- Bubble - look for temp + nested loop
- Insertion - nested loop + i and i-1
- Merge - lots of sublists

Why is the nested loop used in bubble and insertion sorts condition controlled

- Don’t know how many swaps are needed
- Will keep swapping until in correct position