Search And Sort Algorithims.

Question 1

What is a binary search?

Answer 1

-1) Find middle item in ordered list.
2) If this is the item your looking for stop if not compare the item your looking for with the middle item and if it comes before the middle item discard the left, and if it comes after the item then discard the right.
Repeat until you find the item.
TO BE USED IN AN ORDERED LIST.

Question 2

What is a linear search?

Answer 2

• Used on an unordered list.
• Checks each item in turn to see if it is the correct one.
• Stops when it has find the item it was looking for or has checked everything.

Question 3

What can be compared between an binary search and an linear search?

Answer 3

• Linear Search= Simpler but not as efficient.
• Linear can be used on any type of list, doesn’t have to be ordered.
• Linear searches are often used on small lists as its inefficent.
• Binary searches are more suitable for longer and large lists of items.

Question 4

What is a Bubble sort?

Answer 4

• Sort an unordered list of items.
• Simple but takes a while.
  Steps:
  1) Look at first two items in a list.
  2) If they are in right order don’t do anything, if they are in the wrong order swap them.
  3) Move onto the next pair of items.
  4) repeat until you get to the end of the list- this is called a pass and the last item will be in the correct place so don’t include it in next pass.
  Repeat until there are no swaps in pass.

Question 5

What are the advantages and disadvantages of a bubble sort?

Answer 5

Pros:

• Simple Algorithm + Can be easily implemented
• Not much memory used as sorting is used on original list.

Cons:

• Inefficient.
• Not suitable for long list of items.

Question 6

What is a Merge sort?

Answer 6

• Splits the list apart.
• Merges it back together.
• Small lists are easier to sort than large lists.
• Easier to merge to ordered list than two unordered list.
  Steps:
  1) Split the list in half. (Smaller lists= sub-lists). 2nd sub list should start with the middle item.
  2) Keep splitting the sub-lists until all lists contain only one item.
  3) Merge pairs of sub-lists and each time you merge sort the items in right order.
  4) Repeat until you’ve merged all sub-lists together.

Question 7

What are the pros and cons of a merge list?

Answer 7

Pros:

• More efficient and quicker than a bubble sort.
• More efficient than insertion sort for large lists of items/
• Consistent running time no matter how ordered the original list is.

Cons:

• Slow at small lists.
• Even if the list is ordered, it goes through the whole process still
• Uses a lot of memory for the split process.

Question 8

What is an insertion sort?

Answer 8

• Simplest.
  1) Look at the 2nd item in a list.
  2) Compare to all items before it and insert the number in right place.
  3) Repeat step 2, until last number in the list has been inserted into the correct place.