# Algorithms Flashcards

binary search precondition

the list needs to be sorted

Insertion sort

works by dividing a list into two groups: sorted and unsorted. Elements are inserted one by one into their correct position in the sorted section.

linear search

starts at the beginning of a list and checks each item in turn until the desired item is found

Binary search

divides a list in two each time until the item being searched for is found

Four sorting algorithms

Bubble, Insertion, Quick, Merge

Insertion sort words

Make the first item in the list the sorted list. The remaining items are the unsorted list.

While there are items in the unsorted list take the first item of the unsorted list.

While there is an item to the left of it which is smaller than itself swap with that item. End while.

The sorted list is now one item bigger.

End while

Merge sort

splits a list of size n into n lists of size 1. Each pair of lists are merged together in order until there is only one list of size n.

Why does merge split down into unit lists

because a list of length one is sorted

Merge algorithm

- If the sub-list is 1 in length, then that sub-list has been fully sorted
- If the list is more than 1 in length, then divide the unsorted list into roughly two parts. (An odd numbered length list can’t be divided equally in two)
- Keep dividing the sub-lists until each one is only 1 item in length.
- Now merge the sub-lists back into a list twice their size, at the same time sorting each items into order
- Keep merging the sub-lists until the full list is complete once again.

Quick sort algorithm

REPEAT:

1. Pick a pivot

2. sort the items either side of the pivot

3. make the items either side of the pivot a sublist

Until length of sublist= 1

Quick sort

The basic idea is to keep splitting a list into two smaller lists, sort those lists using the same quick-sort rules, then split the sub-lists and sort again, until there are only lists of 1 item or less left.

Where can the pivot be applied

The pivot can be applied to any item in the unsorted list.

advantages bubble

- simple

disadvantages bubble

- long time to run

advantages insertion

- Simple to code
- Good performance with small lists
- memory efficient
- good with sequential data

disadvantages insertion

- poor performance with larger lists

- not as quick as merge/quick sort

disadvantages quick

- difficult to implement
- if a bad pivot is picked the runtime is slow
- worst case efficiency is bad