CISC 121 Lecture Notes - Lecture 7: Linear Search, Bubble Sort, Selection Sort

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Margaret Lamb

Document Summary

Return the index of the value in the list (or none if element not present) Number of comparisons for sequential search is proporional to the size of the list. Binary search: list must be in order basic algorithm: If value is bigger, repeat with larger half of list. If value is smaller, repeat with smaller half of list. Logarithmic algorithm (this is why its so much faster for bigger list) Bubble sort: simple and easy to program but slow. Basically search to find smallest element and put it in the smallest spot. Worst case: o(n^2) - can happen when the list is sorted or almost sorted already.