Közvetlen beszúrásos rendezés (algoritmus)

A közvetlen beszúrásos rendezés egy egyszerű, négyzetes időben futó rendezési algoritmus. Az elgondolás alapja az, hogy egy rendezett tömbbe lineáris idő alatt be lehet szúrni egy új elemet a következő algoritmussal:

   procedure beszur(tömb, új_elem)
   begin
      // feltesszük, hogy a tömb utolsó eleme felülírható
      i := len(tömb);   // az i tartalmazza az új elem leendő indexét
      while i>1 and tömb[i-1]>új_elem do
         tömb[i] := tömb[i-1];
         i := i-1;
      end;
      tömb[i] := új_elem;
   end;

A beszúrandó elemet addig "toljuk" balra a tömbben, amíg a tőle balra álló elem nagyobb nála. Ha a tőle balra álló elem kisebb vagy egyenlő, akkor az összes balra levő elem kisebb vagy egyenlő lesz, hiszen a tömb többi eleme már rendezve van. A cserék száma egyenlő azon elemek számával, amelyek nagyobbak az új elemnél.

A rendezés kiindul egy egy elemű tömbből (a bemenő tömb első eleméből), majd egyesével beszúrja ebbe a tömbbe a bemenő tömb elemeit. Az egy elemű tömb mindig rendezett, a beszúrások pedig megtartják a rendezettséget, így a végeredményként kapott tömb is rendezett lesz. A rendezés helyben végezhető, ha a bemenő tömb elejét használjuk az új tömb tárolására. Ennek a pszeudokódja:

   for i in 2..len(tömb) do
      beszúr(tömb[1..i],tömb[i]); // a tömb egy részét átadjuk a fenti algoritmusnak
   end;

Az algoritmus egyik előnye, hogy "majdnem rendezett" tömbökre jóval gyorsabban fut, mint teljesen rendezetlenekre. (Teljesen rendezett tömb esetén n darab összehasonlítás után, tehát lineáris időben lefut.) A legrosszabb eset a fordítottan rendezett tömb; ekkor a kiválasztásos rendezéshez hasonlóan n*(n-1)/2 összehasonlítást végez az algoritmus.

További előny, hogy nem kell a teljes adathalmaznak rendelkezésre állnia a rendezés elkezdéséhez, hiszen egyszerre mindig csak egyetlen új elemmel dolgozunk. A később érkező adatokat hatékonyan be tudjuk szúrni a már meglevő rendezett tömbünkbe.