Chapter 5

Chapter 5

1. Sorting Algorithms

   • Bubble Sort
     • Repeatedly steps through the list to be sorted, compares each pair of items beside each other and swaps them if they are in the wrong order.
   • Insertion Sort
     • Works by dividing the list into two parts: sorted and unsorted
     • Elements are inserted one by one into their correct position in the sorted section
   • Merge Sort
   • Quicksort
     • Steps
       • 1. Take the first item in the list, make it a list one item big and call it the pivot
       • 2. Splits the remainder of the list into two sub-lists: those less than or equal to the pivot and those greater than the pivot
       • 3. Recursively apply step 2 until all sub-lists are pivots
       • 4. The pivots can now be combined to form a sorted list

2. Search Algorithms

   • Linear Search
     • Methodically searches one location after another until the searched-for value is found
   • Binary Search
     • Works by dividing the list in two each time until we find the item being searched for
     • The list must be in order

3. Complexity

   • O(x)
     • X = worst case complexity of the algorithm
   • n = number of data
   • Constant complexity
     • O(1)
       • Takes the same amount of time to run regardless of the size of a data set
   • Linear complexity
     • O(n)
       • Increase at the same rate as the input size increases
   • Polynomial complexity
     • O(n to the power of k) (where k>=0)
   • Exponential complexity
     • O(k to the power on n) (where k>0)
   • Logarithmic complexity
     • O(Log n)

4. Shortest path algorithms

   • Dijkstra's algorithm
     • Finds the shortest path between two points
   • A* search
     • Uses heuristic to find the shortest path between two points