Triedenie

• Zadanie: x[1..N] of ineteger (navzájom rôzne)

• Úloha: nájst pole y[1..N] také, ze

  y je permutáciou x ? ? ?i: 1 ? i ? N:: y[i] < y[i + 1] ? (1)
  

• Dve základné stratégie:

  • redukcia poctu zle usporiadaných dvojíc
  • utriedenie casti pola

1. Reduckia poctu zle usporiadaných dvojíc

(zatial nešpecifikujeme, kolko dvojíc sa permutuje v kazdom kroku, v akom poradí sa permutujú apod.)

• zavedme metriku

M = ? +i, j: 0 < i < j ? N: y[i] > y[j]:: 1 ?

• stratégia je formálne definovaná nasledujúcim invariantom, FP a progress podmienkou:

invariant y je permutáciou x (2)

FP ? (M = 0) (3)

? ?k: k > 0:: M = k ? M < k ? (4)

• Dôkaz správnosti: stací ukázat, ze platí

(2) ? (3) ? (4) ? true ? FP

a ze (1) platí v kazdom FP.

Previous slide

Next slide

Back to first slide

View graphic version