Search/sort Algorithms

Search/sort Algorithms

1. Binary search

   • The list must be ordered.
     • First the middle item must be found"(n+1)/2"
       • If middle item is not the search item, Then compare the search item to the middle number
       • If middle item is less than search item then discard first half and vice versa.
       • Repeat steps until middle number is the search item

2. Linear search

   • Works on unordered list
     • Start with first item
       • Then move onto next
         • Repeat until search item is found

3. Bubble sort

   • Compares lists of items
     • Most effective for checking if lists are in order
     • Simple algorithm
     • Little memory used
   • Inneficient way of sortig
     • Struggles with longer lists
   • Ciompare first two numbers- if wrong swap if not leave them
     • Move onto next pair (2,3) repeat last step
       • Repeat step until end of list (pass)
         • Repeat until there is no swaps in a pass

4. Merge

   • Most efficient
   • Does not matter how ordered the list is
   • Slower for small lists
     • Uses most memory
   • Split list in half until each identity is separated
   • Merge the sub lists ( put identities into pairs then order and do the same with each pair)
     • Repeat until all sub lists are joined