Énoncé

TD 4

EX 2

1)

Tri rapide en place :

def quick_sort(L, min = 0, max= -1):
  assert L
  if max >= min:
    if max == -1:
      max = len(L)-1
    p = L[min]
    p, L[max] = L[max], p
    i = 0
    for j in range(max):
      if L[j] <= p:
        L[j], L[i] = L[i], L[j]
        i+=1
    L[i+1], p = p, L[i+1]
    quick_sort(L, min, i)
    quick_sort(L, i+2, max)

2) La proba que le premier élément (pivot) soit le $k$-ième plus petit élément du tableau vaut $1/n$ $\begin{array}{rlr}& T(n)& =\sum _{1\le k\le n}\frac{1}{n}(T(k)+T(n-k)+n-1)\\ & & =\frac{1}{n}\sum _{1\le k\le n}(T(k)+T(n-k))+n-1\\ & & =\frac{2}{n}\sum _{1\le k\le n}T(k)+n-1\\ ⟹& nT(n)& =2\sum _{1\le k\le n}T(k)+n(n-1)\\ ⟹& nT(n)-(n-1)T(n-1)& =2(n-1)+2T(n)\\ ⟹& (n-2)T(n)-2(n-1)& =(n-1)T(n-1)\\ ⟹& \frac{T(n)}{n-1}-\frac{2}{n-1}& =\frac{T(n-1)}{n-2}& & \text{division par }(n-2)(n-1)\\ ⟹& \frac{T(n)}{n-1}-\frac{2}{n-1}& =\frac{T(n-1)}{n-2}\\ ⟹& \frac{T(n)}{n-1}-\frac{T(n-1)}{n-2}& =\frac{2}{n-1}\\ ⟹& \frac{T(n)}{n-1}& \sim 2\log (n-1)\end{array}$

Or,

EX 3

1) Algo naïf en $O(n^2)$ temporel, $O(1)$ spatial.

2) En dehors de cette bande : un cercle de gauche et un cercle de droite ne peuvent pas s’intersecter.

3) $p\le n$

4) On regarde les points par ordre des $y$ croissants : on prend le point $p$ ayant le $y_{min}$