#!/usr/bin/env python
# coding: utf-8

# # Week 3 Lecture 2a: Computational efficiency, more on sorting

# In[ ]:


get_ipython().run_line_magic('run', '"boaz_utils.ipynb"')


# # Analyzing how fast algorithms run

# We always care about how fast an algorithm runs.
# 
# **O notation** focuses on how the time **scales** when inuput work. We focus on **worst case complexity**

# In[ ]:


def star():
    print("*",end="")
n= 20


# ## O(1)

# In[ ]:


#assigning a variable
L= list(range(1000))
L[0]=5 #doesn't matter how big L is
L[10]=10


# In[ ]:


star()


# ## O(n) linear time 
# 

# In[66]:


def find_star(L,s):
    for i in range(len(L)):
        star()
        if L[i]==s: return i
    return -1

L = range(200)
find_star(L,114)


# ## O(n${^2}$) quadratic time

# In[67]:


def intersection_star(L1,L2):
    intersection = []
    for i in L1:
        for j in L2:
            star()
            if i==j: intersection += [i]
    return intersection

L1= range(0,50,3) 
L2= range(0,50,2) 
intersection_star(L1,L2)


# ## O(n${^3}$) cubic time

# In[69]:


def intersect3_star(L1,L2,L3):
    intersection =[]
    for i in L1:
        for j in L2:
            for k in L3:
                star()
                if i==j==k: intersection +=[i]
    return intersection
L1 = range(0,50,2) 
L2 = range(0,50,3)
L3 = range(0,50,5)
intersect3_star(L1,L2,L3)


# ## O (log(n))

# In[70]:


def binsearch_star(L,s):
    start = 0
    end   = len(L)
    while start<end:
        star()
        mid = int((start+end)/2)
        if s<L[mid]: end = mid
        if s>L[mid]: start = mid+1
        if s==L[mid]: return mid
    return -1

L = range(1000)
binsearch_star(L,783)


# ## O (n*log(n))
# 

# $n < n\log n < n^2$.
# 
# $n\log n$ is closer to $n$ than to $n^2$. 
# 
# We will see an example (__Merge Sort__) in the afternoon.

# In[71]:


plotfunctions(lambda n:log(n), r'$\log n$', lambda n:n, r'$n$', lambda n:n*log(n), r'$n\log n$',
    lambda n:n*n, r'$n^2$', lambda n:n*n*n, r'$n^3$', n= 100)


# In[72]:


plotfunctions( lambda n:log(n), r'$\log n$', lambda n:n, r'$n$',
    lambda n:n*log(n), r'$n\log n$', lambda n:n*n, r'$n^2$', n= 100)


# In[73]:


# n vs log n
plotfunctions(  lambda n:log(n), r'$\log n$', lambda n:n, r'$n$',     n= 100)


# Comparing them for $n=10^9$

# In[74]:


n=10**9

print(f"log n  \t= {log(n):,}  (nanoseconds)")
print(f"n \t= {n:,} (seconds)")
print(f"n log n\t= {n*log(n):,} (minutes)")
print(f"n^2 \t= {n*n:,} (years)")
print(f"n^3 \t= {n*n*n:,} (billions of years)")


# ## Extended Example

# __Exercise:__ Given list `L` and and value `x`,  partition `L` so that values from `0` to `i-1` are smaller than `x` and value from `i` onwards are equal or larger to `x`. Return `i`

# __Solution 1:__  Use selection sort to sort L then scan to find the first position where the value is at least `x`

# In[ ]:


def find_min_index(L):
    currmin = 0
    for i in range(1,len(L)):
        if L[i]<L[currmin]: currmin=i
    return currmin


# In[ ]:


def selection_sort(L):
    if len(L)<=1: return L
    for i in range(len(L)-1):
        j = i + find_min_index(L[i:])
        L[i],L[j] = L[j],L[i]
    return L


# In[ ]:


selection_sort([12,456,324,435,65])


# In[75]:


def partition(L,x):
    selection_sort(L)
    for j in range(len(L)):
        if L[j]>= x: return j
    return len(L)


# In[81]:


L = [random.randint(1,100) for i in range(10)]
print(f"Before: {L}")
i = partition(L,50)
print(f"After: {L}")
print(f"i={i}, L[i-1]={L[i-1]}, L[i]={L[i]}")


# ## Is this the most efficient version?

# __Steps in construction of algorithms:__ <br>
# 1) Understand __what__ is the problem to solve. <br>
# 2) Find __how__ to solve the problem, first  _high level_/_pseudocode_ and then _code_.<br>
# 3) Analyze __why__ algorithm solves the problem.<br>
# 4) Analyze __how fast__ it runs.

# __Reorder:__ Input `L` of length `n`, value `x`:<br>
# Set `i=0`, `j=n-1` <br>
# Increase `i` and decrease `j` until we find "mismatched pair": `L[i]>=x` and `L[j]<x` <br>
# Switch such pairs and continue until `i>=j`

# In[ ]:


def partition2(L,x):
    i = 0; j = len(L)-1
    while i<j:
        if L[i]<x: i+= 1
        elif L[j]>= x: j -= 1
        else: L[i],L[j]=L[j],L[i]
    return j


# In[84]:


L = [random.randint(1,100) for i in range(6)]
print(f"Before: {L}")
i = partition2(L,50)
print(f"After: {L}")
print(f"i={i}, L[i-1]={L[i-1]}, L[i]={L[i]}")


# __Analysis:__ (on board)
#     
# 1. __Why__ it is correct
# 
# 2. __How fast__ why does it run in $O(n)$ time
# 

# In[ ]:


inputs = [([random.randint(1,n) for i in range(n)],int(n/2)) for n in range(10,600,60)]
inputs1 = [list(a) for a in inputs]
inputs2 = [list(a) for a in inputs]


# In[85]:


compare_times(partition,partition2,inputs)


# In[87]:


timer(partition,inputs1);


# In[86]:


timer(partition2,inputs2);