Next: Třídy ekvivalence
Up: Sorting - třídění
Previous: Quicksort
Pole indexů Index[i] nám určuje místo, na kterém je -tý
prvek podle velikosti. Pole pořadí Pořadí[i] určuje kolikátý
je podle velikosti -tý prvek. Pole indexů hledáme tímto postupem:
- Přiřadíme Index[j] := j.
- Porovnáváme prvky, ale místo arr[j] používáme
arr[Index[j]].
- Přehazujeme prvky v poli Index[j].
Prvky pole pořadí hledáme pomocí pole indexů podle vztahu
Pořadí[Index[j]] := j.
Pořadí v poli |
Původní pole |
Pole indexů |
Pole pořadí |
Uspořádané pole
|
|
|
|
|
|
|
|
V této tabulce tedy první prvek pole indexů číslo 5 znamená, že pátý
prvek původního pole je nejmenší. Dále čtvrtý prvek je druhý
v pořadí a třetí prvek je největší. První prvek pole pořadí říká, že
na prvním místě původního pole je čtvrtý prvek podle velikosti,
druhý prvek je třetí podle velikosti a poslední prvek je podle
velikosti pátý.
Next: Třídy ekvivalence
Up: Sorting - třídění
Previous: Quicksort
Jiri Limpouch
2000-03-29