sequential (aka linear) search

• first element, looks through all items one by one, in usually unsorted data
• best case: if element is first
• worst case: element not in array

in common:

• both find values in a list
• best case: 1 comparison

binary search

• requires sorted data. checks middle of data and see if its less than, equal to, or greater; keeps cutting in half
• usually quicker than sequential
• middle index — left + right / 2 (integer division truncates)
• best case: found in the middle of the array
• “divide & conquer”
• find max iterations: 2^x > n
• worst case: usually not a lot of comparisons

selection sort

• select smallest item from current location on to the end of the array and swap it with the value at the current position (takes n-1 passes - last element will be sorted)

starts at index 0

• identify:
  • a nested for loop with outer starting at 0 and ending when index reaches length-1
  • index of smallest value should start at the outer loop index
  • inner loop should start at outer loop index + 1 and loop through whole array
  • if value in array at index of inner loop is less than value at smallest index then set smallest index to the index of the inner loop
  • swap value at outer loop index and the smallest value
• takes the same number of executions despite the data
• search & swap
• best case: ascending?
• swaps correct (values) into place

insertion sort

• worst case is when array is sorted in decreasing order
• moves the list down to insert numbers in front of the list
• starts at index 1
• identify:
  • outer for loop that starts at 1 and loops through

merge sort

• divides list into roughly equal halves, sorts each half (left half, then the right half), and combine the halves into a whole sorted list again
• this is often implemented recursively! and another “divide & conquer” algorithm
• probably the most efficient sorts for now, with all cases being O(logn). however it takes up lots of memory as it creates a temporary array as large as the original one