TD4 : Tri rapide, Diviser pour régner

É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{aligned} & T(n) &= \sum\limits_{1 ≤ k ≤ n} \frac 1 n (T(k) + T(n-k) + n-1) \\ & &= \frac 1 n \sum\limits_{1 ≤ k ≤ n} (T(k) + T(n-k)) + n-1 \\ & &= \frac 2 n \sum\limits_{1 ≤ k ≤ n} T(k) + n-1 \\ ⟹& n T(n) &= 2 \sum\limits_{1 ≤ k ≤ n} T(k) + n(n-1) \\ ⟹& n T(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{aligned}\)

Or,

\[\begin{align*} T(n) &= \sum\limits_{𝜎 ∈ 𝕾_n} P(𝜎) T(𝜎) \\ &= \sum\limits_{1 ≤ i ≤ n} \sum\limits_{𝜎_i} P(𝜎) T(𝜎) &&\text{où $𝜎_i$ est une permutation de 1er élément $i$} \\ &= \sum\limits_{1 ≤ i ≤ n} \sum\limits_{𝜎_i} \underbrace{P(𝜎)}_{= P(i \text{ pivot}) P(𝜎 \vert i \text{ pivot})} T(𝜎) \\ &= \sum\limits_{1 ≤ i ≤ n} \sum\limits_{𝜎_i}\frac 1 n P(𝜎_i \vert i \text{ pivot}) T(𝜎_i) \\ &= \frac 1 n \sum\limits_{1 ≤ i ≤ n} \underbrace{\sum\limits_{𝜎_i} P(𝜎_i \vert i \text{ pivot}) T(𝜎_i)}_{ \overset{?}{ = } T(i) + T(n-i) + n-1}\\ \end{align*}\]

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 \leq n$

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