In [42]:

```
def linear_search(L, e):
found = False
for i in range(len(L)):
if e == L[i]:
found = True
return found
```

In [43]:

```
linear_search([1,2,6,867,123,99],6)
```

Out[43]:

In [44]:

```
linear_search([1,2,6,867,123,99],76)
```

Out[44]:

- must look through all elements to decide it’s not there
- overall
**complexity is O(n)**– where n is len(L)

In [65]:

```
def search(L, e):
for i in range(len(L)):
if L[i] == e:
return True
if L[i] > e:
return False
return False
```

In [66]:

```
search([1,2,6,867,1234],6)
```

Out[66]:

In [67]:

```
search([1,2,6,867,1234],99)
```

Out[67]:

In [68]:

```
search([1,2,157,6,867,1234,0,17891],0) # list is not sorted hence False
```

Out[68]:

- must only look until reach a number greater than e
- O(len(L)) for the loop * O(1) to test if e == L[i]
- overall
**complexity is O(n)**–where n is len(L)

- finish looking through list when
`- 1 = n/2^i - so i= log n`

**complexity is O(log n)**–where n is len(L)

In [71]:

```
#BISECTION SEARCH IMPLEMENTATION 1
def bisect_search1(L, e):
if L == []:
return False
elif len(L) == 1:
return L[0] == e
else:
half = len(L)//2
if L[half] > e:
return bisect_search1( L[:half], e)
else:
return bisect_search1( L[half:], e)
```

In [72]:

```
#BISECTION SEARCH IMPLEMENTATION 2
def bisect_search2(L, e):
def bisect_search_helper(L, e, low, high):
if high == low:
return L[low] == e
mid = (low + high)//2
if L[mid] == e:
return True
elif L[mid] > e:
if low == mid: #nothing left to search
return False
else:
return bisect_search_helper(L, e, low, mid -1)
else:
return bisect_search_helper(L, e, mid + 1, high)
if len(L) == 0:
return False
else:
return bisect_search_helper(L, e, 0, len(L) -1)
```

Implementation 1 –bisect_search1

- O(log n) bisection search calls
- O(n) for each bisection search call to copy list
**O(n log n)**- O(n) for a tighter bound because length of list is halved each recursive call

Implementation 2 –bisect_search2 and its helper

- pass list and indices as parameters
- list never copied, just re-passed
**O(log n)**

- using
**linear search**, search for an element is**O(n)** - using
**binary search**, can search for an element in**O(logn)**- assumes the list is
**sorted**!

- assumes the list is

**best case**:**O(n)**where n is len(L) to check if sorted**worst case**:**O(?)**it is**unbounded**if really unlucky

In [76]:

```
def bogo_sort(L):
while not is_sorted(L):
random.shuffle(L)
```

- compare consecutive pairs of elements
- swap elements in pair such that smaller is first
- when reach end of list, start over again
- stop when no more swaps have been made

In [79]:

```
def bubble_sort(L):
swap = False
while not swap:
swap = True
for j in range(1, len(L)):
if L[j-1] > L[j]:
swap = False
temp = L[j]
L[j] = L[j-1]
L[j-1] = temp
```

**O(n^2) where n is len(L)**

first step

- extract minimum element
- swap it with element at index 0

subsequent step

- in remaining sublist, extract minimum element
- swap it with the element at index 1

keep the left portion of the list sorted

- at ith step, first ielements in list are sorted
- all other elements are bigger than first ielements

In [80]:

```
def selection_sort(L):
suffixSt= 0
while suffixSt!= len(L):
for i in range(suffixSt, len(L)):
if L[i] < L[suffixSt]:
L[suffixSt], L[i] = L[i], L[suffixSt]
suffixSt+= 1
```

- outer loop executes len(L) times
- inner loop executes len(L) –i times
**complexity of selection sort is O(n^2)**where n is len(L)

use a divide-and-conquer approach:

- if list is of length 0 or 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 end of the result
- when one list empty, just copy rest of other list

In [110]:

```
def merge(left, right):
result = []
i,j= 0, 0
while i< len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i+= 1
else:
result.append(right[j])
j += 1
#print(result,'result')
while (i< len(left)):
result.append(left[i])
i+= 1
while (j < len(right)):
result.append(right[j])
j += 1
return result
def merge_sort(L):
if len(L) < 2:
return L[:]
else:
middle = len(L)//2
#print(middle,'middle')
#print(L[:middle],'ll')
#print(L[middle:],'rl')
left = merge_sort(L[:middle])
#print(left,'left')
right = merge_sort(L[middle:])
#print(right,'right')
return merge(left, right)
```

In [111]:

```
merge_sort([0,1,5,6,3,7,4])
```

Out[111]:

- 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 in length of the lists

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

at first recursion level

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

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)

- dividing list in half with each recursive call
- O(log(n)) where n is len(L)
- overall complexity is
**O(n log(n))**where n is len(L)

**bogosort**

- randomness, unbounded 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

Reference

- edX course offered by MIT
- 6.00.1x Introduction to Computer Science and Programming Using Python