# 2.1.3 - Searching and Sorting Algorithms Flashcards

1
Q

Types of searching algorithms

A

Linear search and Binary Search

2
Q

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

A

It can be either

3
Q

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

A

It has to be ordered

4
Q

How does a linear search work? (3 steps)

A
• 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

5
Q

Hows does a binary search work? (4 steps)

A
• 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

6
Q

Types of sorting algorithms

A
• Bubble sort - temp + swaps
• merge sort - sublists
• insertion sort - inserts into correct place
7
Q

A
• Easy to understand
• However, very slow and inefficient
8
Q

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

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

Similarities of a bubble sort and an insertion sort

A
• 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
11
Q

Difference between a bubble an insertion sort

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

Steps in a merge sort

DIVIDE AND CONQUER

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

Steps in a bubble sort

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

Tips to identify the different sorting algos

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

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

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