Beszúrásos rendezés

Beszúrásos rendezés
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	${\displaystyle O(n^{2})}$
Legjobb időbonyolultság	${\displaystyle \Omega (n),O(1)}$ csere
Átlagos idő bonyolultság	${\displaystyle O(n^{2})}$ összehasonlítás, csere
Legrosszabb tár bonyolultság	${\displaystyle O(n)}$ teljes, ${\displaystyle O(1)}$ kiegészítő

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.

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.

• Algoritmusok animációi
• Rendezési algoritmusok C++ kódjai
• ↑ Knuth: Knuth, Donald E.. The Art of Computer Programing II. kiadás. Addison Wesley. 020189685 (1997) 

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

• Koktélrendezés
• Buborékrendezés
• Gyorsrendezés
• Kupacrendezés

Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!