A maximum kiválasztásos rendezés alapötlete az, hogy a legnagyobb elemnek a tömb végén van a helye, a rendezés szerint. Ezért kiválasztjuk a tömb maximális elemét, majd kicseréljük a rendezetlen résztömb utolsó elemével. Ezt ismételgetve egy rendezett tömböt kapunk.

A maximum kiválasztásos rendezés nem stabil rendezés, azaz az azonos kulcsú elemek egymáshoz viszonyított sorrendjét nem feltétlenül őrzi meg. Például, ha van kettő 32-es, akkor nem biztos, hogy ugyanabban a sorrendben lesznek a rendezés végén, mint rendezés előtt voltak. Viszont könnyen stabillá tehető, ha a maximum és a rendezetlen résztömb utolsó elemének cseréje helyett, a maxtól jobbra levő rendezetlen elemeket balra csúsztatnánk, és a maxot a rendezetlen résztömb végén keletkező üres helyre szúrnánk be. Ezzel az adatmozgatások várható és maximális száma is $\Theta(n^2)$ lenne, így minden előnyét elvesztené az algoritmus.

A rendezendő számokat kulcsoknak is szokás nevezni. A bemenő kulcsokat helyben rendezi, tehát a számokat az $A$ tömbön belül rakja a helyes sorrendbe és legfeljebb csak állandó számú elem tárolódik a tömbön kívül.

Az algoritmus az összehasonlító rendezések közé tartozik, azaz az elemek sorrendjét azok összehasonlításával állapítja meg.

Működése:

A bemenet számok $n$ elemű $(a_1, a_2, ..., a_n)$ sorozata, a kimenet pedig az $a_1, a_2, ..., a_n$ számok egy olyan $(a_1', a_2', ..., a_n')$ átrendezése, ahol $a_1' \leq a_2' \leq ... \leq a_n'$.

A tömböt két résztömbként kezeljük, a még nem rendezettek résztömbje és a már rendezettek résztömbje. Mindig kiválasztjuk a legnagyobb elemet a még nem rendezettek résztömbjéből és a résztömbünk végén lévő elemmel megcseréljük. Ezzel ez az elem már a rendezettek résztömbjéhez fog tartozni.

Lehetséges olyan eset, amikor a maximális elem és a rendezetlen résztömb utolsó eleme ugyanaz, ilyenkor az elemet „önmagával cseréljük meg”.

Műveletigény:

A maximumkiválasztó rendezés egyik hátránya, hogy nem tudja kihasználni a bemenet tulajdonságait, ahhoz, hogy kicsit gyorsabban fusson. Nagy előnye viszont, hogy csak $3(n-1)$ mozgatást végez. (Egy csere 3 mozgatásnak számít, innen jön a 3-as szorzó).

• $MT(n) \in \Theta(n^2)$
• $AT(n) \in \Theta(n^2)$
• $mT(n) \in \Theta(n^2)$

Gyakorlati alkalmazása:

Az egyik legkönnyebben implementálható rendező algoritmus, ezért ha valakinek kevés elemet kell rendeznie és nem számít a hatékonyság, általában ezt fogja használni.