#### LINEAR SEARCH ON UNSORTED LIST¶

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

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

Out:
True
In :
linear_search([1,2,6,867,123,99],76)

Out:
False
• must look through all elements to decide it’s not there
• overall complexity is O(n) – where n is len(L)

#### LINEAR SEARCH ON SORTED LIST¶

In :
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 :
search([1,2,6,867,1234],6)

Out:
True
In :
search([1,2,6,867,1234],99)

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

Out:
False
• 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 :
#BISECTION SEARCH IMPLEMENTATION 1

def bisect_search1(L, e):
if L == []:
return False
elif len(L) == 1:
return L == e
else:
half = len(L)//2
if L[half] > e:
return bisect_search1( L[:half], e)
else:
return bisect_search1( L[half:], e)

In :
#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)


#### COMPLEXITY OF THE TWO BISECTION SEARCHES¶

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!

#### BOGO SORT¶

• best case: O(n) where n is len(L) to check if sorted
• worst case: O(?) it is unbounded if really unlucky
In :
def bogo_sort(L):
while not is_sorted(L):
random.shuffle(L)


#### BUBBLE SORT¶

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

#### SELECTION SORT¶

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

#### MERGE SORT¶

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 :
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 :
merge_sort([0,1,5,6,3,7,4])

Out:
[0, 1, 3, 4, 5, 6, 7]

#### COMPLEXITY OF MERGING SUBLISTS STEP¶

• 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

#### COMPLEXITY OF MERGE SORT¶

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)

#### SORTING SUMMARY--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