Beszúrásos rendezés

A beszúrásos rendezés a rendezési algoritmusok egy csoportja.[1] Legegyszerűbb formája az egyenes beszúrásos rendezési algoritmus egy tömb elemeinek sorba rendezésére. Az algoritmus k-adik lépése előtt az első k-1 elem már rendezett; a lépés során a k-adik elemet beszúrjuk az első k-1 elem közé az őt nagyság szerint megillető helyre, és a nála nagyobbakat eggyel eltoljuk.

Beszúrásos rendezés
Insertion sort animation.gif
Kategória rendezési algoritmus
Adatstruktúra tömb
Legrosszabb idő bonyolultság
Legjobb idő bonyolultság csere
Átlagos idő bonyolultság összehasonlítás, csere
Legrosszabb tár bonyolultság teljes, kiegészítő
A beszúrásos rendezésre egy példa

Az eljárás hasonlít a kiválasztásos rendezéshez, ahol szintén a k-adik lépés végére az első k elem rendezett; de míg ott az első k helyen a végleges, rendezett sorozat eleje van, addig a beszúrásos rendezésnél a kezdeti, rendezetlen állapot első k eleme, de azok helyes sorrendben.

A beszúrásos rendezés lépésszáma legrosszabb és átlagos esetben is négyzetes, így nagy tömbök esetén nem hatékony. Nagyon kis tömbökre azonban ez a leggyorsabb algoritmus.

JegyzetekSzerkesztés

  1. Knuth  3. kötet 84. oldal

ForrásokSzerkesztés

Kapcsolódó szócikkekSzerkesztés

A Wikimédia Commons tartalmaz Beszúrásos rendezés témájú médiaállományokat.