SlR26 - Algorithms

Merge sort steps

1. Repeatedly divide list in half until each item is in own list

2. Take two lists & start with first item in each

3. Compare two items

4. Insert lowest item into new list, move to next item in list it was taken from

5. Repeat steps 3 & 4 until all items from one of the list are in the new list

6. Append all the items from that list that still contains items to the new list

7. Replace two adjacent lists with new list

8. Repeat from step 2 until all adjacent lists have been compared

9. Repeat from step 2 until only one list remains

Quick sort

• More efficient than merge sort - less memory

• Better for larger data sets & ideal for parallel processing where divide & conquer can be used

Quick sort steps

1. Set pointer to first & last item in list

2. While first pointer ≠ second pointer:

   • If item at pointers in wrong order, swap order & pointer

   • Move first pointer on item towards second pointer

3. Repeat from step 1 on list of items to left of pointer

4. Repeat from step 1 on list of items to right of pointer

Dijkstra

• Finds shortest path between one node & all other nodes on weighted graph

• Type of breadth-first search

• Doesn’t work on edges with negative weight values

Dijkstra steps

1. Set initial distance from starting values for all nodes

2. For each node in graph

   • Find node with shortest distance from start that has not been visited

   • For each connected node that has not been visited

     • Calc distance from start

     • If distance from start is lower that current recorded distance from start

       1. Set shortest distance too start of connected node to newly calculated distance

       2. Set previous node to be current node

3. Mark node as visited

4. Start from goal node

5. Add previous node to start of list

6. Repeat from step 5 until node reached

7. Output list

Admissible

Used to describe a heuristic that is sensible

A* steps

1. Set initial g & f values ( g: from start, f: g + h) for all nodes in graph

2. Until goal node visited:

   • Find node with lowest f value that has not been visited

   • For each connected node

     • Calc relative distance from start by adding edge value & heuristic

     • If distance from start + heuristic is lower than current recorded f value

       1. Set f value of connected node to newly calculated distance

       2. Set previous node to be current node

   • Set previous node as visited

3. Start from goal node

4. Add previous node to start of list

5. Repeat from step 3 until start node reached

6. Output list

Time & memory complexity

• How time scales as data size increases

• How memory used scales as data size increases

Big O notation

1. Remove all terms except one with largest factor order

2. Remove any constants

Search algorithm complexity

Sorting algorithm complexity