2.1.3-Searching and Sorting Algorithms

How does a binary search algorithm work?

1). find middle item in the ordered list

2). if this is the item you're looking for, search stops

3). if not, compare the item you're looking for to the middle item. if it comes before the middle, get rid of the second half. if it comes after the middle, get rid of the first half

\- repeat these steps on the new list made until the desired value is found

How does a linear search algorithm work?

1). look at first item in unordered list

2). if this is equal to the desired value stop search

3). is not, move onto next item in the list

4). repeat steps until you've found desires item or gone through all items

binary search vs linear search

* linear is simpler than binary
* linear does not require an ordered list
* binary is more efficient than linear
* binary is more suitable for larger lists than linear

How does a bubble sort work?

1. look at the first two items in the list
2. If they are in the right order, you don’t have to do anything. If they are in the incorrect order, swap them.
3. Move onto the next pair of items (2nd and 3rd) and repeat previous step.
4. repeat step 3 until you reach the end of the list. This is one complete pass. The last item will be in the correct place, so it isn’t included in the next pass.
5. Repeat steps 1-4 until there are no swaps in a pass.

Advantages of Bubble Sorts

* simple algorithm
* efficient way to check if a list is already in order
* doesn’t use very much memory as sorting is done using original list

Disadvantages of Bubble Sorts

* inefficient way to sort the list
* does not cope well with large list of items due to inefficiency

How does a merge sort algorithm work?

1. Split the list in half (smaller lists=sub-lists)
2. keep repeating step 1). on each sub-list until all lists only contain 1 item
3. merge pairs of sub-lists so each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the correct order.
4. Repeat step 3). until all sub-lists have been merged together.

Advantages of Merge Sorts

* more efficient and quicker than bubble sort and insertion sorts for larger lists
* consistent running time

Disadvantages of Merge Sorts

* Slower than other algorithms for small lists
* splitting and merging happens regardless of whether list is already sorted or not
* uses more memory than other sorting algorithms in order to create separate lists

How does an insertion sort work?

1). Set the first element as 'sorted'. 

2). Take the second element and compare it with all the elements in 'sorted'. Once it reaches the correct place, add it to the 'sorted' list.  

3). Repeat this with all of the values in the unsorted list, comparing it with all elements in the sorted list and adding it to the list in the correct place.  

4). Once all elements are in the correct place, the list should be fully sorted. 

Advantages of insertion sorts

* intuitive way of sorting
* copes very well with smaller lists
* doesn’t require much additional memory
* quick to add items to an already ordered list
* quick at checking if a list is already sorted

disadvantages of insertion sort

* doesn’t cope well with very large lists