Næsti algorithmi sem ég tek fyrir heitir Insertion Sort. Þetta er álíka einfalt og Bubble Sort, en mun hraðvirkari.

En áður en ég útskýri hann, þá ætla ég að benda á tvær leiðir til að gera Bubble Sort hraðvirkari. Ef við skoðum aðeins kódann, þá sjáum við að við erum kannski að fara í sumum tilfellum of oft í gegnum array-inn. Það er náttúrulega lítið mál að breyta því með því að setja inn boolean breytu sem segir okkur hvort við höfum breytt array-inum eitthvað. Ef hann hefur ekkert breyst, þá er tilgangslaust að halda áfram þar sem við erum búin að sortera öll gögnin. Tökum dæmi:

For (int i = 0; i < 10; i++)
{
    // Búum til bool breytuna.
    bool bFlipped = false;
    for (int j = 0; j < 10 – 1; j++)
    {
   &nbs p;    if (iarrTolur[j] > iarrTolur[j + 1])
        {
             int iTmp = iarrTolur[j];
      &nbs p;     iarrTolur[j] = iarrTolur[j +1];
        & nbsp;   iarrTolur[j + 1] = iTmp;
             // Látum vita að við breyttum.
       &n bsp;    bFlipped = true;
         }
    }
    / / Ef ekkert breyttist, þá bara hætta.
    if (bFlipped) break;
}

Þetta getur munað þó nokkuð ef um stærri array-a er um að ræða, en það er hægt að gera eitt enn sem heitri Bidirectional Bubble Sort, það er að segja að sortera gögnin í báðar áttir í einu. Að sortera t.d. 10.000 random integer tölur tekur helmingi styttri tíma með þessari aðferð. Hún lítur svona út:

For (int i = 0; i < 10; i++)
{
    bool bFlipped = false;
    // Færa stærri tölur aftar
    for (int j = 0; j < 10 – 1; j++)
    {
   &nbs p;    if (iarrTolur[j] > iarrTolur[j + 1])
        {
             int iTmp = iarrTolur[j];
      &nbs p;     iarrTolur[j] = iarrTolur[j + 1];
        &n bsp;   iarrTolur[j + 1] = iTmp;
             bFlipped = true;
         }
    }

   &nbsp ;// Færa svo minni tölur framar, og byrjum aftast auðvitað
    for (int j = 10 – 1; j > 0; j–)
    {
   &nbs p;    if (iarrTolur[j] < iarrTolur[j – 1])
        {
             int iTmp = iarrTolur[j];
      &nbs p;     iarrTolur[j] = iarrTolur[j – 1];
        &n bsp;   iarrTolur[j – 1] = iTmp;
             bFlipped = true;
         }
    }
    i f (bFlipped) break;
}

En hey, þetta er náttúrulega bara rugl, þetta er orðinn alltof mikill kóði fyrir hægvirka sortun þannig að verið ekkert að nota þetta, Insertion Sort er töluvert skárri. Þessi algorithmi byggist upp á að hafa vinstri hlutann af array-inum alltaf sorteraðann. Tökum dæmi um array með fimm tölum:

3 7 6 8 9

Núna í staðinn fyrir að bera saman 3 og 7 og láta skipta um sæti, og næst 7 og 6 og svo framvegis, þá tökum við 7 og athugum hvort sú tala eigi að vera framar. Ef svo er, þá færum við hana, annars förum við á næstu tölu, sem er 6, við sjáum að hún á að fara framar og því setjum við hana fyrir framan 7 og höldum svona áfram í gegnum allann array-inn.

Kóða dæmi með 10 integer gildum í array sem heitir iarrTolur:

// Förum í gegnum allar tölurnar
For (int i = 1; i < 10; i++)
{
    // Búum til breytu til að geta talið niður frá upphafsgildi
    int j = i;
    // Tökum gildið úr array-inum, notað til að bera saman.
    int iNum = iarrTolur;

    // Færum núna allar tölur sem eru stærri en iNum til
    while ((j > 0) && (iarrTolur[j – 1] > iNum))
    {
   &n bsp;    iarrTolur[j] = iarrTolur[j -1];
        j –;
    }
   &nbsp ;// Nú ætti j að vísa í það sæti sem talan okkar á heima í.
    iarrTolur[j] = iNum;
}

Eins og við sjáum er einnig ansi fljótlegt að henda þessum kóða upp til að sortera gögn, þó aðferðin sé kannski örlítið flóknari en í bubble sort, en samt ekki, það er bara allt einfalt ef maður skilur það.

Til smá samanburðar, að sortera 5000 random integer tölur tók 911 ms á minni tölvu með Bubble Sort aðferðinni, 541 ms með Bidirectional Bubble sort og 180 ms með Insertion sort. Þannig að við sjáum að þetta er töluvert betri aðferð.