SORTS AND SEARCHES

Question 1

merge sort?

Answer 1

merge sort:

1. split the list in half (sub-list)
2. keep repeating on each sub-list until the lists only have 1 item
3. merge the pairs of sub-lists together sorting the items in the correct order
4. repeat step 3 until all sub-lists are merged together

Question 2

bubble sort

Answer 2

1. look at the first 2 items in the list
2. if they are in the wrong order swap them
3. move to the next pair (2nd and 3rd item) and repeat
4. repeat until you get to the end of the list.
5. repeat all steps until there are no swaps left.

Question 3

Insertion sort

Answer 3

1. the first item is take from the unsorted list and compared to the sorted one. It cant be moved as its the first one.
2. the 2nd item is compared to the sorted list, if they’re in the wrong order they’re swapped
3. the next is compared and moved into the correct position.
4. the next is compared to the sorted list and moved into the right position etc.

https://www.youtube.com/watch?v=jmdP4Y-x0Hc

helpful if still not get (40 secs in)

Question 4

Linear search

Answer 4

1. look at the first item.
2. if this is the right item then stop as you’ve found what you’re looking for.
3. look at the next item in the list.
4. repeat until the item is found.

Question 5

binary search

Answer 5

1. sort the list in order.
2. find the middle item in the ordered list
3. if this is the item then stop
4. if not compare the item to the middle one. If it comes before (is less) than the middle item then get rid of the right side of the list. If it comes after (more than) the middle item get rid of the left side of the list.
5. repeat until item is found