Programozás‎ > ‎Rendezések‎ > ‎

Beillesztéses rendezés

Gondolat

A tömbre úgy gondolunk, mintha két részből állna: az első i elem már rendezett résztömböt alkot, a többi elemet pedig még nem vizsgáltuk. Most következik az (i+1)-dik elem. Őt szeretnénk beilleszteni az első i közé úgy, hogy most már az első i+1 elemből álló résztömb is rendezett legyen. Ez ahhoz hasonló, mint amikor a kártyás kézben sorba teszi lapjait: balról indul és a következő lapot mindig beszúrja a helyére az addig rendezett lapok közé.

A beszúrás úgy történik, hogy amíg a vizsgált elem kisebb, mint a tőle balra álló, addig felcseréljük vele. Figyelni kell arra is, hogy nem értünk-e ki a tömb bal szélére, mert ott leáll a cserélgetés.

Algoritmus

Ciklus i:= (E+1)-től U-ig
    j := i - 1
    Ciklus amíg j >= E és a[j] > a[j+1]
        Csere(j, j+1)
         j := j - 1
    Ciklus vége
Ciklus vége