Triedenie ? Rank sort

• pre kazdý prvok z y vypocítame pocet prvkov menších alebo rovných v y ? táto hodnota je poradové císlo (pozícia) tohoto prvku v usporiadanom y

• Program P6

  declare r: array[1 .. N] of integer
  
  always
  ? || i: 1 ? i ? N:: r[i] = ? +j: 1 ? j ? N ? x[j] ? x[i] :: 1? ?
  ? ? || i: 1 ? i ? N:: y[r[i]] = x[i] ?

end{P6}

• Dôkaz: treba ukázat nasledujúce tri vlastnosti programu P6:

1. rovnosti sú proper

2. y je permutácia x

3. y je usporiadané

• Výraz ? +j: 1 ? j ? N ? x[j] ? x[i] :: 1? mozno vypocítat v case O(log N) s O(N) procesormi.

• Takze všetky r[i] mozno vypocítat v case O(log N) s O(N2) procesormi.

• Alebo v case O(N) s O(N) procesormi, ak jeden procesor ráta r[i], a to v case O(N).

Previous slide

Next slide

Back to first slide

View graphic version