Searching and sorting algorthms

How does binary search work

1)Find the middle item in the order list(n+1/2)

2)Check if middle number matches target

3)If number is greater or smaller than target discard the left or right side

4)Repeat until number is found

What is the pre-requisite of binary search

The list must be in order

How does linear search work

1)Start with first value

2)Check all the values one by one in order to

3)Until the value you are looking for is find

What’s the pros and cons of linear search

Pros:-Doesn’t require data to be in order-Works on any type of list-it’s efficient for small data sets

Cons-Very inefficient for large data sets

How does bubble sort work

1)Look at first two items in list

2)If right order you don’t do anything but if they aren’t you swap them

3)Move onto next pair of items and repeat

4)Repeat until you get to the end of list-this is called one pass. Last item will no be in correct place so don’t picked in next pass

5)Repeat until there’s no swaps in a pass

What are Pros and Cons of bubble sort

Pros:-Doesn’t use very much memory-It’s an efficient way to check is list is already in order

Cons:-It’s inefficient for large list of items

How does merge sort work

1)Split the list in half starting at middle item

2)Keep repeating until all lists only contain one item

3)Merge Pairs of sub lists so that each sub list has twice as many items sprung the items in correct order

4)Repeat until you’ve merged all sub lists together

What’s the Pros and cons of merge sort

Pros:-More efficient and quicker than bubble sort and for large lists

Cons:-It’s slower than other algorithms for small lists-It uses more memory than other sorting algorithms

How does insertion sort work

1)Look at second item in a list

2)Compare it to all times before it and insert the number into right place

3)Repeat step 2 for next times until the last number in the list has been inserted into correct place

What’s the pros and cons

Pros:-quick at checking if list is already sorted-quick to add items to list already sorted-Copes very well with small lists

Cons:Doesn’t cope well with large lists