import functools
%run boaz_utils.ipynb

More Sorting¶

L = [4,1,3,2]
print(sorted(L))

[1, 2, 3, 4]

def make_comparator(key):
    def compare(x,y):
        if x[key] < y[key]:
            return -1
        elif x[key] > y[key]:
            return 1
        else:
            return 0
    return compare

runners = [
    {'firstname':'Shelly-Ann', 'lastname':'Fraser-Pryce', 'country':'JAM', 'time':10.67},
    {'firstname':'Shericka', 'lastname':'Jackson', 'country':'JAM', 'time':10.73},
    {'firstname':'Elaine', 'lastname':'Thompson-Herah', 'country':'JAM', 'time':10.81},
    {'firstname':'Dina', 'lastname':'Asher-Smith', 'country':'GBR', 'time':10.83},
    {'firstname':'Mujinga', 'lastname':'Kambundji', 'country':'SUI', 'time':10.91},
    {'firstname':'Aleia', 'lastname':'Hobbs', 'country':'USA', 'time':10.92},
    {'firstname':'Marie Josée', 'lastname':'Ta Lou', 'country':'CIV', 'time':10.93},
    {'firstname':'Melissa', 'lastname':'Jefferson', 'country':'USA', 'time':11.03},

]

def print_runners(L):
    for x in L:
        print(x['firstname'].ljust(15) + ' ' + (x['lastname'].upper() + ',').ljust(20) + ' ' + x['country'].ljust(3) + ', ' + str(x['time']))

print_runners(sorted(runners, key=functools.cmp_to_key(make_comparator('time'))))

Shelly-Ann      FRASER-PRYCE,        JAM, 10.67
Shericka        JACKSON,             JAM, 10.73
Elaine          THOMPSON-HERAH,      JAM, 10.81
Dina            ASHER-SMITH,         GBR, 10.83
Mujinga         KAMBUNDJI,           SUI, 10.91
Aleia           HOBBS,               USA, 10.92
Marie Josée     TA LOU,              CIV, 10.93
Melissa         JEFFERSON,           USA, 11.03

What is a good way to sort?

Simple algorithm: find smallest item and move to position 0, then the next smallest to position 1, etc...

Recursive implementation¶

# return the index of the minimum element of the list
def find_min_index(L):
    if len(L) == 0: # hmmm...
        return -1
    elif len(L) == 1:
        return 0
    else:
        i = find_min_index(L[1:]) + 1
        if L[i] < L[0]:
            return i
        else:
            return 0

print(find_min_index([5,6,7]))

print(find_min_index([6,5,8]))

print(find_min_index([6,7,5]))

0
1
2

def selection_sort(L):
    if len(L) == 0:
        return L[:] # why do we return L[:] instead of L?
    else:
        idx = find_min_index(L)
        return [L[idx]] + selection_sort(L[:idx] + L[idx+1:])

selection_sort([5,4,3,2,1])

[1, 2, 3, 4, 5]

Iterative implementation¶

def iterative_selection_sort(L):
    A = L[:]
    for i in range(len(A)):
        # try to find index idx of the min element in L[i:],
        # then move it to L[i]
        idx = i
        for j in range(i+1, len(A)):
            if A[j] < A[idx]:
                idx = j
        
        # swap contents of A[i] and A[idx]
        tmp = A[i]
        A[i] = A[idx]
        A[idx] = tmp
    return A

L = [3,2,1]
iterative_selection_sort(L)

[1, 2, 3]

Roughly how many steps do these algorithms take?¶

Recursive implementation¶

Let $T (n)$ be the number of steps the algorithm takes on input lists of length $n$ .

Then

$T (n) = {\begin{cases} 1, & if len(L) == 0 \\ T (n - 1) + C n, & otherwise \end{cases}$

So then $\dots$ ¶

$T (n) = T (n - 1) + C n$

$T (n) = T (n - 2) + C n + C (n - 1)$

$T (n) = T (n - 3) + C n + C (n - 1) + C (n - 2)$

$\dots$

$T (n) \leq C (n + n - 1 + n - 2 + \dots + 1)$

same thing as saying

$T (n) \leq C (1 + 2 + \dots + n)$

Also

$T (n) \geq 1 + 2 + \dots + n$

Have you seen this sum before?¶

$\begin{aligned} 1 + 2 + \dots + n & = (1 + n) + (2 + (n - 1)) + (3 + (n - 2)) + \dots \\ = (n + 1) + (n + 1) + (n + 1) + \dots \end{aligned}$

which is ${\begin{cases} (n + 1) \cdot \frac{n}{2}, & if n is even \\ (n + 1) \cdot \frac{n - 1}{2} + \frac{n + 1}{2}, & if n is odd \end{cases}$

(and you can check that $(n + 1) \cdot \frac{n - 1}{2} + \frac{n + 1}{2} = (n + 1) \cdot \frac{n}{2}$ )

In any case, the sum is $\approx \frac{n^{2}}{2}$ , so we say the runtime is "proportional to $n^{2}$ " (some constant factor times $n^{2}$ ), which we also write as " $Θ (n^{2})$ ".

Some computer science jargon $\dots$ ¶

Say $f (n)$ is the worst-case runtime of some algorithm on inputs of size $n$

and $g (n)$ is the worst-case runtime of some other algorithm on inputs of size $n$

Then the notation means that once $n$ is larger than some threshold $\dots$

$f (n) = O (g (n))$ : $f (n) \leq C g (n)$ for some constant $C$

$f (n) = Ω (g (n))$ : $f (n) \geq C g (n)$ for some constant $C$

$f (n) = Θ (g (n))$ : $f (n) = O (g (n))$ and $f (n) = Ω (g (n))$

$n = O (3 n)$ and $n = O (7 n^{2} + 2 n + \cos (n))$ , but $n$ is not $Θ (7 n^{2})$ (because it is not $Ω (7 n^{2})$ )

Back to selection_sort¶

Easier way to see that $1 + 2 + \dots + n = Θ (n^{2})$ $\dots$

$\begin{aligned} 1 + 2 + \dots + n & \leq n \cdot n = n^{2} \\ 1 + 2 + \dots + n & \geq \frac{n}{2} + (\frac{n}{2} + 1) + \dots + n \approx \frac{n^{2}}{2} \end{aligned}$

So running time of the algorithm is at least $\frac{n^{2}}{2}$ and at most $n^{2}$ , so it is $Θ (n^{2})$

c , *_ = timer(selection_sort,genintlist(1000))

/home/minilek/.local/lib/python3.8/site-packages/sklearn/linear_model/_base.py:133: FutureWarning: The default of 'normalize' will be set to False in version 1.2 and deprecated in version 1.4.
If you wish to scale the data, use Pipeline with a StandardScaler in a preprocessing stage. To reproduce the previous behavior:

from sklearn.pipeline import make_pipeline

model = make_pipeline(StandardScaler(with_mean=False), LassoLars())

If you wish to pass a sample_weight parameter, you need to pass it as a fit parameter to each step of the pipeline as follows:

kwargs = {s[0] + '__sample_weight': sample_weight for s in model.steps}
model.fit(X, y, **kwargs)

Set parameter alpha to: original_alpha * np.sqrt(n_samples). 
  warnings.warn(

c(10**9)

3333229102056.811

print(f'{int(c(10**9)/ (24*3600*365)):,} years!')

105,696 years!

Can we sort faster?¶

def merge(A, B):
    C = []
    Aidx,Bidx = 0,0
    for i in range(len(A) + len(B)):
        if Aidx == len(A):
            C += B[Bidx:]
            break
        elif Bidx == len(B):
            C += A[Aidx:]
            break
        elif A[Aidx] < B[Bidx]:
            C += [A[Aidx]]
            Aidx += 1
        else:
            C += [B[Bidx]]
            Bidx += 1
    return C
        

def merge_sort(L):
    if len(L) <= 1:
        return L[:]
    else:
        A = merge_sort(L[:len(L)//2])
        B = merge_sort(L[len(L)//2:])
        return merge(A,B)

# can also use a recursive implementation of merge
def recursive_merge(A, B):
    if len(A) == 0:
        return B[:]
    elif len(B) == 0:
        return A[:]
    elif A[0] < B[0]:
        return [A[0]] + merge(A[1:], B)
    else:
        return [B[0]] + merge(A, B[1:])

merge_sort([5,4,3,2,1])

[1, 2, 3, 4, 5]

print(list(range(10,0,-1)))

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

big_list = list(range(20000,0,-1))

merge_sort(big_list)
'done'

'done'

iterative_repeated_min_sort(big_list)
'done'

'done'

Now let's analyze the running time of MergeSort on the board ...¶

c , *_ = timer(merge_sort,genintlist(1000))

/home/minilek/.local/lib/python3.8/site-packages/sklearn/linear_model/_base.py:133: FutureWarning: The default of 'normalize' will be set to False in version 1.2 and deprecated in version 1.4.
If you wish to scale the data, use Pipeline with a StandardScaler in a preprocessing stage. To reproduce the previous behavior:

from sklearn.pipeline import make_pipeline

model = make_pipeline(StandardScaler(with_mean=False), LassoLars())

If you wish to pass a sample_weight parameter, you need to pass it as a fit parameter to each step of the pipeline as follows:

kwargs = {s[0] + '__sample_weight': sample_weight for s in model.steps}
model.fit(X, y, **kwargs)

Set parameter alpha to: original_alpha * np.sqrt(n_samples). 
  warnings.warn(

c(10**9)

37506.54340083344

print(f'{int(c(10**9)/ 3600):,} hours!')

10 hours!

JamCoders

More Sorting¶

Recursive implementation¶

Iterative implementation¶

Roughly how many steps do these algorithms take?¶

Recursive implementation¶

So then ……¶

Have you seen this sum before?¶

Some computer science jargon ……¶

Back to selection_sort¶

Can we sort faster?¶

Now let's analyze the running time of MergeSort on the board ...¶

So then $\dots$ ¶

Some computer science jargon $\dots$ ¶