Searching ans Sorting

• method for finding an item or group of items • Collections could be implicit • Collections could be explicit

• brute force search • list does not have to be sorted • O(n) - where n is len(L)

• list MUST be sorted to give correct answer

• must only look until reach a number greater than e - O(n) - where n is len(L)

• break into smaller version of problems - answer to smaller version is answer to original problem

• linear search => O(n) • binary search => O(log n) (assumes the list is sorted!)

• sort + O(log n) < O(n) -> sort < O(n) - O(log n) • when sorting is less than O(n) -> never true!

• 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

is a random sort, every time through the list get randomly sorted and if lucky it is ordered!

Best case: O(n) where n is len(L) Worst case: O(?) is unbound if really unlucky

• Compare consecutive pairs of elements • Swap elements such that smaller is first • Start over when reach end of list • No more swaps = stop

• inner for loop is doing comparisons • out while loop is doing multiple passes until no more swaps O(n2) where n is len(L)

• extract min. element - swap it with element at index 0

• in remaining sub-list extract min. element - swap it with the element at index 1

• at ith step, first i element in list are sorted - all other elements are bigger than first i elements

O(n2) where n is len(L)

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

• 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

• divide list successively into halves - depth-first such that conquer smallest pieces down one branch first before moving to larger pieces

• n/2 elements in each list - O(n) + O(n) where n is len(L)

• 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)

with each recursive call: O(log(n)) where n is len(L)

O(n log (n)) where 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