5.9. Medián, minimális, maximális, i-dik legnagyobb elem

A sorozat minimális illetve a maximális elemének meghatározásához végig kell lépdelnünk az összes elemen, s megvizsgálni, hogy az adott elem kisebb-e/nagyobb- e mint az eddig talált minimum/maximum. Ezért a minimum/maximum meghatározása lineáris feladat. Az i-dik elem meghatározására a feltételektől függően más és más módszert érdemes használni.

– Ha viszonylag kis számú kulcs fordul elő, akkor a leszámláló rendezésben ismertett módszerrel a C tömbből könnyedén meghatározható az i. legnagyobb/legkisebb szám.

– Ha i kicsi n-hez képest, akkor a kupacrendezés elvét használva, a kupacból i számot törölve megkapjuk az i. legnagyobb/legkisebb számot.

– A gyorsrendezés az alsorozat elemeit két részre osztotta: a kijelölt elemnél kisebb elemek és annál nagyobbak sorozatára. Eme sorozatok hossza alapján dönthetünk, hogy mely sorozatban található a keresett elem. Ezt a módszert követve átlagosan lineáris időben kereshetjük meg az i. elemet.