Beszúrási sort - studopediya
Válogató betétek (Beillesztés rendezés) - egyszerű válogatás algoritmus, mely egy másik elem is hozzáadódik mindig a lista végén, majd továbbmegy a lista tetején, amíg ez kisebb, mint az előző elem.
Így hivatalosan, ez egy megfelelő helyre beilleszteni (például válogatás kártyák a könyvtárban). Ez az algoritmus lesz a következő lépések.
1. Az inicializálási lépésben. Array elem már rendezve szerint növekvő, és ez szolgál a kezdeti lista.
2. lépés iteráció. Minden további eleme a második, hogy n -1, a következő elem i összehasonlítjuk az összes korábbi eleme 0 (i-1), míg az aktuális elem i kisebb vagy egyenlő, mint az előzőt. Miután ez megvan helyzetben beszúrni, vagy elérik a lista tetején. Ezt követően, az elem be van helyezve a talált helyzetben.
Tegyük fel, hogy adottak a következő tömböt:
Az elemzés a számítási komplexitás azt mutatja, hogy minden esetben szükség van, hogy készítsen (n-1) lépés. Minden ilyen részeket a legjobb esetben, ha a tömb rendezve növekvő sorrendben, egy összehasonlítás van szükség. Ebben az esetben a permutációs nem, és a számítási költség lesz
.
A legrosszabb esetben, ha a tömb van rendezve csökkenő sorrendben az egyes (n -1) i halad required összehasonlítást a korábbi elemek. A számítási komplexitás arányos. Átlagosan minden menetben lesz szükség kevesebb mint a fele. Ezért átlagosan. A számítási bonyolultsága továbbra is arányos.
A tömbvázlata rendezési algoritmus betétek formájában van:

Végrehajtja ezt az algoritmust C ++ az alábbiak szerint:
void InsertSort (T * A, const int n)