[Algorytmy] QuickSort - liczba przestawień a liczba porównań

[matinf]

Cześć.

Kod: Zaznacz cały

zalozenia: {l < r
 a[l], a[l+1], a[l+2],...,a[r] le a[r+1] 
v=a[l]; i=l; j=r+1
}
repeat
     repeat     i = i + 1   until    a[i] >= v
     repeat     j = j -  1   until    a[j] <= v
     if i <= j  then a[i] <--> a[j]
until j <= i
a[l]=a[j]
a[j]=v
//koniec partition
if j - 1 > l then qsort (l, j-1)
if r > j + 1 then qsort (j+1, r)

Pokazać, że w algorytmie Qsort liczba przestawień jest nie większa niż połowa liczby porównań.
No i wydaje mi się, że wystarczy powiedzieć, że zawsze zanim wykonamy (ewentualną, bo wziętą w ifa zamianę) musimy wykonać co najmniej dwa porównania (choć jedno w repeat pierwszym, choć jedno w repeat drugim).

Ale wydaje mi się, że za łatwo. Co o tym sądzicie ?