Nú er komið algoritma sem er líklega sá besti “overall” sorting algorithmi sem er þekktur. Jamm… við erum að tala um Quick Sort. Þetta er löng grein þannig að drífðu þig að sækja kaffibolla og starta forritunarumhverfinu þínu.

Þessi algorithmi byggist upp á að skipta array-inum í tvo búta, einum með lægri tölunum í array-inum og hinn búturinn á þá að hafa hærri tölurnar. Þessum bútum er svo aftur skipt í eins tvo búta og svo framvegis þar til array-inn er sorteraður.

Þetta er óskaplega einfalt concept, en það kannski vefst fyrir sumum að útfæra þetta í kóða, þannig að við skulum demba okkur í það sem snöggvast.

Fyrst, þar sem við þurfum “recursive” köll þá verður þetta að vera function, hana skilgreinum við svona:

void QuickSort(int* iarrTolur, int iLo, int iHi)
{

Þessi function tekur við þremur breytum, fyrst er það array-inn sem á að sortera, svo lægri indexinn, það er segja indexinn sem vísar í fyrstu færslu sem við eigum að vinna með. Síðasta breytan er svo hærri indexinn, það er að segja vísum í síðustu færsluna sem við eigum að vinna með.

Næst skilgreinum við tvær breytur til að muna hærri og lægri index gildin.

int iLo0 = iLo;
int iHi0 = iHi;

Svo kemur smá check um hvort við þurfum að skipta array-inum, eða hvort búið sé að sortera hann. Þetta tékk er auðvitað best að hafa fremst í function-inu.

if (iLo > iHi) return;

Þar sem ef lægri indexinn er hærri en hærri indexinn, þá hlýtur að vera búið að sortera allt.

Þá kemur kannski erfiðasti parturinn, það er að finna út svokallaða pivot tölu, það er þessi tala sem ákvarðar hvort aðrar tölur í array-inum teljist til lægri talnanna eða hærri talnanna. Það eru margar mismunandi útfærslur á að finna út þessa tölu, t.d. nota bara töluna sem er í fyrsta stakinu í array-inum, í miðjunni, endatala, random tala eða nota einhverja algorithma til að reyna að finna út miðgildi í array-inum sem myndi deila sem næst jafn mörgum tölum í hvorn bút. Við notum bara töluna sem er í fyrsta stakinu en ég mæli eiginlega ekki með því.

int iPivot = iarrTolur[iLo];

Svo er komið að því að færa allar tölur sem eru lægri en pivot talan fremst í listann, og allar tölur sem eru hærri en pivot talan aftast í listann.

do
{
   do
   {
      iLo0++;
   }
   while (iarrTolur[iLo0] < iPivot)
   do
   {
      iHi0–;
   }
   while (iarrTolur[iHi0] > iPivot;

Þarna einfaldlega lækkum við og hækkum þessa tvo indexa þar til við erum komnir með index á tölu sem er hærri en pivot talan, og tölu sem er lægri. Þið sjáið að báðar do lykkjurnar eru inni í einni annari sem við eigum enn eftir að loka, það er vegna þess að við þurfum að gera þangað til að við erum búin að raða öllum tölunum.

Ef lægri indexinn verður stærri, eða jafn og hærri indexinn þá þurfum við ekkert að aðhafast frekar og break-um út úr móður do lúppunni.

   if (iLo0 >= iHi0) break;

Ef svo var ekki, þá þurfum við að swappa tölunum.

   int iTmp = iarrTolur[iLo0];
   iarrTolur[iLo0] = iarrTolur[iHi0];
   iarrTolur[iHi0] = iTmp;

Þá er allt búið sem á að vera inni í móður lúppunni, þannig að við lokum henni

}
while (0 == 0);

Þarna sjáum við að þetta er í raun “endalaus” lúppa, hún er semsagt keyrandi þangað til að skilyrðið iLo0 >= iHi0 verður = true, þá fyrst viljum við stoppa.

Svo setjum við gildið í hærri indexinum í gildið hjá lægri indexinum.

iarrTolur[iLo0] = iarrTolur[iHi0];

Og setjum svo pivot tölum í hærri indexinn

iarrTolur[iHi0] = iPivot;

Þá er ekkert eftir en að kalla í fallið með nýjum indexum, okkar fall kallar semsagt aftur í sjálft sig, það heitir recursive.

Fyrst með þann hluta sem innihelur lægri tölurnar

QuickSort(iarrTolur, iLo0, iHi0 – 1);

Og svo þann sem hefur hærri tölurnar

QuickSort(iarrTolur, iHi0 + 1, iHi);
}

Og fallið okkar er tilbúið.

Jæja, nú er ég búinn að kynna ykkur 3 mismunandi leiðir til að sortera gögn. En hvaða leið er best? Best er að byrja á að benda á að Bubble Sort er sú aðferð sem skal helst forðast, þó að Bubble Sort verði sambærilegri við Insertion Sort með því að nota Bidirectional Bubble Sort og boolean breytuna, þá er það bara of mikill kóði fyrir sort aðferð sem er samt hægvirkari en Insertion Sort. Það er samt hugsanlegt að uppfæra forrit sem eru þegar til og nota Bubble Sort með Bidirectional Bubble Sort til að gera það aðeins hraðvirkara.

Þannig að eftirstendur valið á milli Insertion Sort og Quick Sort, Insertion Sort er hraðvirkari á array sem er þegar nokkurn veginn sorteraður, en Quick Sort er langtum hraðvirkari á ósortuð gögn. Þannig að þetta er svo sem spurning um hverju þú ert að raða. Í flestum tilvikum aftur á móti hentar Quick Sort betur.

Til eru fleiri sort algorithmar en þessir 3, til dæmis Comb 11 Sort, Heap Sort, Selection Sort (sem er drasl reyndar), Shell sort, Shaker Sort og þannig má endalaust halda áfram. Flestir þessir algorithmar eru mjög líkir og í raun oft bara aðferð til að reyna að bæta aðra sort algorithma, eins og Comb Sort er í raun Bubble Sort sem er búið að breyta þannig að lágar tölur færast hraðar niður arrayinn, sem er helsti gallinn við Bubble Sort. Ykkur er auðvitað frjálst að skoða þessar aðferðir, en ég fer ekkert nánar út í þær.

Að lokum, gæti hugsast að ég sé fyrstur á huga til að eiga 5 nýjustu greinarnar á einu áhugamáli? Skrifið nú eitthvað, annars þarf að breyta nafninu á þessu áhugamáli í “abh”.