Segítsen a webhely fejlesztésében, megosztva a cikket a barátokkal!

A C++ QuickSort bemutatása

A következő cikk a C++ QuickSort vázlatát tartalmazza. A programozási nyelvben mindig szükségünk van algoritmusra, hogy hatékonyan működjön, és ezek közé tartozik a Quicksort. Ahogy a neve is sugallja, az elemek rendezésére szolgál. Ehhez néhány lépést kell követnie. Ez az algoritmus kiválaszt egy elemet a listából, amelyet „pivotnak” neveznek, és a listát két részre osztja a hatékony rendezés érdekében.

A C++ QuickSort szintaxisa

Mivel ez egy algoritmus, így nincs szintaxisa, de meghatároz néhány lépést, amelyet követni kell a gyors rendezés végrehajtása során bármely nyelven.

  • A lépés: Válasszon ki egy elemet a listából pivotként.
  • B lépés: Válasszon ki két elemet bal és jobb oldalként.
  • C lépés: A bal oldali elem alacsony indexet jelent.
  • D lépés: A jobb oldali elem magas indexet jelent.
  • E. lépés: Ha a bal oldali érték kisebb, mozgassa jobbra.
  • F lépés: Ha a jobb oldali érték nagyobb, mozgassa balra.

Ezt a lépést addig hajtjuk végre, amíg a kisebb és nagyobb elemek áthaladnak egymáson.

Tehát a fenti lépések követésével megvalósíthatjuk ezt a kódunkat C++ nyelven. De az alapötlet ennek hátterében minden nyelv esetében ugyanaz.

A QuickSort működése C++-ban az algoritmussal

Ma már tudjuk, hogy a QuickSort funkciót az elemek hatékony rendezésére használják. Ez egy algoritmus, amely meghatároz néhány követendő lépést, hogy ezt kódban implementálja.Ez az algoritmus alapvetően pivot elemmel működik, kivesz egy elemet a listából pivotként, és a teljes listát két allistára osztja, és rendezi őket.

A pivot elemet többféleképpen is kiválaszthatjuk, amelyeket alább definiálunk:

  • Az utolsó elemet vehetjük pivot elemnek.
  • A középső elemet vehetjük pivot elemnek.
  • Az első elemet vehetjük pivot elemnek.
  • Tetszőleges véletlenszerű elemet vehetünk pivot elemnek.

Bármelyik megközelítést követhetjük, amely tovább osztja elemlistánkat két különböző allistára. A többi elemet balra és jobbra mozgatjuk a tömbbe vagy listába a rendezés érdekében.

Az alábbiakban egy egyszerű algoritmust láthatunk, amely a QuickSort meghatározására szolgál C++ nyelven.

Algoritmus:

quickSorAlgo(tömb, kevesebb, több)

//algologika indítása

begin

Itt egy tömböt határozunk meg, amelyet rendezni kell

kevesebb=első elem;

további=utolsó elem;

pivot

if(kevesebb

//rendezési logika indítása

begin

pivot=partíciólista (tömb, kevesebb, több);

quickSorAlgo(Array,less,pivot-1)

quickSorAlgo(tömb,pivot+1,több)

//itt a vége

Vége

//algo véget ér

vége

Megértjük az algoritmust részletesen:

50, 25, 15, 20, 60, 30.

Vegyük fontolóra a fenti tömböt, amely különböző elemeket tartalmaz. Itt a pivot elemet választjuk ki utolsó elemnek, és ennek megfelelően a tömb első elemét alacsonynak, a tömb utolsó elemét magasnak jelöltük. Most megismételjük mutatóinkat a megfelelő pozíciókra, de ehhez egy szabályt követünk az elemek összehasonlítására.

Ha a magasan megjelölt elem kisebb, mint a kiválasztott pivot elemünk, és az alacsonyan jelölt elem nagyobb, mint a pivot elemünk, akkor az elem bájitaljait kicseréljük egymással, és növelni fogjuk az elem pozícióit. megfelelő elemeket, valamint azt, ahová mutatniuk kell. Addig folytatjuk ezt az iterációt, amíg az alacsony és magas elemünk keresztezi egymást, és a pivot elem a megfelelő pozícióba kerül, ahol lennie kell, ez a tömböt vagy listát két allistára osztja, ez a két lista a QuickSort segítségével rendezhető algoritmus függetlenül.

15, 20, 25, 30, 50, 60

Tehát a fenti rendezési algoritmus végső kimenete ez lenne. Egyszerűen és hatékonyan rendezhetjük tömbjeinket a QuickSort algoritmus használatával C++ nyelven.

A QuickSort használatakor emlékezni kell:

  • Először is ki kell választanunk a pivot elemeket a tömbből, ez bármi lehet, például az első, utolsó, véletlenszerű vagy középső elem az elemek tömbjéből.
  • Különböző összetettségű, amelyeket alább említünk:

Legrosszabb eset: O (n 2 )

Átlagos kis- és nagybetű: O (n log n)

Legjobb esetben: O (n log n)

  • Használatával gyorsabban rendezhetjük tömbelemeinket, ami a teljesítményt is javítja.

Példa a C++ QuickSort-ra

Ebben a példában a tömbelemeket gyorsrendezéssel rendezzük, figyelembe véve a pivot elemet a tömb utolsó elemeként.

Kód:

tartalmazza
névtér használatával std;
void elementsSwap(int ele1, int ele2)
{
int temp=ele1;
ele1=ele2;
ele2=hőmérséklet;
}
int elemPartíció (int array(), int kevesebb, int több)
{
int pivotelement=tömb(tovább);
int indexKisebb=(kevesebb - 1);
for (int qs=kevesebb; qs <=more - 1; qs++)
{
if (tömb(qs) {
indexSmaller++;
elementSwap(&tömb(indexKisebb), &tömb(qs));
}
}
elementSwap(&tömb(indexKisebb + 1), &tömb(továbbiak));
visszatérés (indexKisebb + 1);
}
void demoquickSort(int array(), int kisebb, int nagyobb)
{
if (kevesebb {
int parInd=elemPartition(tömb, kisebb, nagyobb);
demoquickSort(tömb, kevesebb, parInd - 1);
demoquickSort(tömb, parInd + 1, nagyobb);
}
}
int main()
{
cout <<"Sorting array elemnts using quick sort in C++ :: ";
int array()={35, 15, 90, 26, 87, 12, 5, 44, 23, 1};
int arrsize=sizeof(array) / sizeof(array(0));
cout <<"Before sort array is : ";
int z;
for (z=0; z cout <cout <demoquickSort(tömb, 0, arrsize - 1);
cout <<"After sorted array is : ";
int i;
for (i=0; i cout <cout <return 0;
}

Kimenet:

Következtetés

A QuickSort algoritmus használatával hatékonyan rendezhetjük tömblista elemeinket. Csak ki kell választanunk a pivot elemet, hogy továbbléphessünk. Ez két részre osztja a tömböt vagy listát, majd rekurzívan végrehajthatjuk a QuickSort algoritmust, hogy megkapjuk a rendezett elemek listáját.

Segítsen a webhely fejlesztésében, megosztva a cikket a barátokkal!

Kategória:

Programozási nyelvek