Beszúrásos rendezés
Beszúrásos rendezés | |
![]() | |
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ő |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/AnimazioneInsertionSort.gif/265px-AnimazioneInsertionSort.gif)
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.
Jegyzetek
Források
- 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)
Kapcsolódó szócikkek
![Commons:Category:Insertion sort](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/50px-Commons-logo.svg.png)
![]() | Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
Informatikai portál • összefoglaló, színes tartalomajánló lap