Searching ans Sorting Flashcards
Search algorithms Bisection Search Bogo Sort Bubble Sort Merge Sort
Search Algorithms
- method for finding an item or group of items
- Collections could be implicit
- Collections could be explicit
Linear Search
- brute force search
- list does not have to be sorted
- O(n) - where n is len(L)
Bisection/binary search
divide and conquer
- list MUST be sorted to give correct answer
Linear search
on a SORTED list
- must only look until reach a number greater than e
- O(n) - where n is len(L)
Bisection search
- break into smaller version of problems
- answer to smaller version is answer to original problem
Searching a sorted list
n is len(L)
- linear search => O(n)
- binary search => O(log n)
(assumes the list is sorted!)
When to sort first then search?
- sort + O(log n) < O(n) ->
sort < O(n) - O(log n) - when sorting is less than O(n) -> never true!
Amortized cost
n is len(L)
- why bother sorting first
- in some cases, may sort list once -> then many searches
- AMORTIZE cost of the sort over many searches
- SORT + KO(log n) < KO(n) -> for large K, SORT time becomes irrelevant
Monkey Sort
aka bogosort - stupid sort - slowsort - permutation sort - shotgun sort
is a random sort, every time through the list get randomly sorted and if lucky it is ordered!
Monkey Sort - complexity
Best case:
O(n) where n is len(L)
Worst case:
O(?) is unbound if really unlucky
Bubble Sort
- Compare consecutive pairs of elements
- Swap elements such that smaller is first
- Start over when reach end of list
- No more swaps = stop
Bubble Sort - complexity
- inner for loop is doing comparisons
- out while loop is doing multiple passes until no more swaps
O(n2) where n is len(L)
Selection Sort
1. First step
- extract min. element
- swap it with element at index 0
Selection Sort
2. Subsequent step
- in remaining sub-list extract min. element
- swap it with the element at index 1
Selection Sort
3. Keep the left portion of the list sorted
- at ith step, first i element in list are sorted
- all other elements are bigger than first i elements
Selection Sort - complexity
O(n2) where n is len(L)
Merge Sort
Use a divide-and-conquer approach
- if list of lenght 0 is 1 - already sorted
- if list has more than one element, split into two lists and sort each
- merge sorted sublists
- look at first element of each, move smaller to wend of result
- when one list empty, just copy rest of other list
Merge Sort - complexity
overview
- go through two lists, only one pass
- compare only smallest elements in each sublist
- O(len(left) + len(right) copied elements
- O(len(longer list)) comparisons
- linear lenght of the lists
Merge Sort - recursevely
- divide list successively into halves
- depth-first such that conquer smallest pieces down one branch first before moving to larger pieces
Merge Sort - complexity
1. at first recursion level
- n/2 elements in each list
- O(n) + O(n) where n is len(L)
Merge Sort - complexity
2. at second recursion level
- n/4 elements in each list
- two merges -> O(n) where n is len(L)
Each recursion level is O(n) where n is len(L)
Merge Sort - complexity
3. dividing list in half
with each recursive call:
O(log(n)) where n is len(L)
Merge Sort - complexity
O(n log (n)) where n is len(L)
Sorting Summary
n is len(L)
bogo sort - randomness, unbound O() bubble sort - O(n2) selection sort - O(n2) - guaranteed the first i elements were sorted merge sort - O(n log(n)) O(n log(n)) is the fastest a sort can be
Algorithms Summary
Selection Sort Bubble Sort Insertion Sort Merge Sort --------------------------- Linear Search Binary Search
Selection Sort
- fin the smallest unsorted element in an array
- swap it with the first unsorted element of that array
Big Oh: Best => O(n^2)
Worst => O(n^2)
Bubble Sort
- swap adjacent pairs of elements if they are out of order
- “bubbling” larger elements to the right and smaller one to the left
Big Oh: Best => O(n)
Worst => O(n^2)
Insertion Sort
- proceed once through the array from left to right
2. shifting elements as necessary to insert each element into its correct place.
Merge Sort
- split the full array into sub arrays
- then merge those sub arrays back together in the correct order.
Big Oh: Best => O(n log n)
Worst => O(n log n)
Linear Search
- Iterate across the array from left to right
- trying to find the target element
Big Oh: Best => O(1)
Worst => O(n)
Binary Search
Given a SORTED array!
1. divide and conquer by systematically eliminating half of the remaining elements in the search for the target elements.
Big Oh: Best => O(1)
Worst => (log n)
Binary Search
Sudocode
Repeat until (sub)array is of size 0
- calculate the middle point of the current (sub)array
- if the target is at the middle - stop
- otherwise if the target is less than the middle, repeat, changing the end point to be just to the left of the middle
- otherwise if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle
