streamalism.org

1. Áttekintés

Ebben az oktatóanyagban részletesen feltárjuk a QuickSort algoritmust, különös tekintettel a Java megvalósítására.

Megbeszéljük előnyeit és hátrányait is, majd elemezzük időbeli összetettségét.

2. QuickSort algoritmus

A Quicksort egy rendezési algoritmus, amely a divide-and-conquer elvét használja ki. Átlaga van O (n log n) összetettség, és ez az egyik leggyakrabban használt rendezési algoritmus, különösen a nagy adatmennyiségeknél.

Fontos megjegyezni, hogy a Quicksort nem stabil algoritmus. A stabil rendezési algoritmus olyan algoritmus, ahol az azonos értékű elemek ugyanabban a sorrendben jelennek meg a rendezett kimenetben, mint a bemeneti listában.

A bemeneti listát a pivot nevű elem két allistára osztja; az egyik allista az elemeinél kevesebb, mint a pivot, a másik pedig a pivotnál nagyobb elemekkel. Ez a folyamat minden allistán megismétlődik.

Végül az összes rendezett allista összeolvad a végső kimenet képződéséért.

2.1. Algoritmuslépések

1. Kiválasztunk egy elemet a listából, amelyet pivotnak hívunk. A listát két allistára osztjuk fel.
2. Átrendezzük az összes elemet a forgócsap körül - a kisebb értékűek kerülnek elé, és az összes elem nagyobb, mint az elfordulás az utána. Ezt a lépést követően a csukló végső helyzetben van. Ez a partíció fontos lépése.
3. A fenti lépéseket rekurzívan alkalmazzuk a forgás bal és jobb oldalán található mindkét allistára.

Ahogy látjuk, A quicksort természetesen rekurzív algoritmus, mint minden megosztani és meghódítani megközelítés.

Vegyünk egy egyszerű példát az algoritmus jobb megértése érdekében.

Arr [] = {5, 9, 4, 6, 5, 3}

1. Tegyük fel, hogy az egyszerűség kedvéért az 5-öt választjuk
2. Először az 5-nél kevesebb elemet helyezzük el a tömb első pozíciójában: {3, 4, 5, 6, 5, 9}
3. Ezután megismételjük a bal oldali {3,4} altömbnél, 3-at választva elfordulónak
4. Nincsenek 3-nál kisebb elemek
5. A forgatás jobb oldalán lévő altömbön quicksort alkalmazunk, azaz {4}
6. Ez az altömb csak egy rendezett elemből áll
7. Az eredeti tömb jobb részével, {6, 5, 9} folytatjuk, amíg meg nem kapjuk a végső rendezett tömböt

2.2. Az Optimal Pivot kiválasztása

A QuickSort döntő eleme a legjobb pivot kiválasztása. A középső elem természetesen a legjobb, mivel két egyenlő részlistára osztaná a listát.

De a középső elem megkeresése egy rendezetlen listáról nehéz és időigényes, ezért vesszük pivotként az első elemet, az utolsó elemet, a mediánt vagy bármely más véletlenszerű elemet.

3. Megvalósítás Java-ban

Az első módszer az quickSort () amely paraméterként veszi a rendezendő tömböt, az első és az utolsó indexet. Először ellenőrizzük az indexeket, és csak akkor folytatjuk, ha vannak még elemek, amelyeket rendezni kell.

Megkapjuk a rendezett pivot indexét, és rekurzív híváshoz használjuk partíció () módszer ugyanazokkal a paraméterekkel, mint a quickSort () módszerrel, de különböző indexekkel:

public void quickSort (int arr [], int begin, int end) {if (start <end) {int partitionIndex = partíció (arr, begin, end); quickSort (arr, begin, partitionIndex-1); quickSort (arr, partitionIndex + 1, end); }}

Folytassuk a partíció () módszer. Az egyszerűség kedvéért ez a függvény az utolsó elemet veszi el pivotként. Ezután ellenőrizze az egyes elemeket, és kicserélje azokat az elfordulás előtt, ha az értéke kisebb.

A particionálás végére a csuklónál kevesebb minden elem a bal oldalán van, és a csuklónál nagyobb elem minden tőle jobbra van. Az elfordulás a végső rendezett helyzetben van, és a függvény ezt a pozíciót adja vissza:

privát int partíció (int arr [], int begin, int end) {int pivot = arr [end]; int i = (kezdet-1); mert (int j = kezdődik; j <vége; j ++) {if (arr [j] <= pivot) {i ++; int swapTemp = arr [i]; arr [i] = arr [j]; arr [j] = swapTemp; }} int swapTemp = arr [i + 1]; arr [i + 1] = arr [vég]; arr [end] = swapTemp; visszatér i + 1; }

4. Algoritmuselemzés

4.1. Idő komplexitás

A legjobb esetben az algoritmus két azonos méretű allistára osztja a listát. Tehát, a teljes első iterációja nméretű listára van szükség Tovább). A fennmaradó két allista rendezése a n / 2 elemek vesznek 2 * O (n / 2) minden egyes. Ennek eredményeként a QuickSort algoritmus összetettsége O (n log n).

A legrosszabb esetben az algoritmus minden iterációban csak egy elemet választ ki, tehát O (n) + O (n-1) +… + O (1), ami egyenlő a következővel: O (n2).

A QuickSort átlagosan rendelkezik O (n log n) bonyolultsággal, alkalmassá téve nagy adatmennyiségekre.

4.2. QuickSort vs MergeSort

Beszéljük meg, mely esetekben válasszuk a QuickSort-ot a MergeSort helyett.

Bár a Quicksort és a Mergesort átlagos időbeli összetettsége: O (n log n), A Quicksort a preferált algoritmus, mivel rendelkezik egy O (log (n)) tér bonyolultsága. A Mergesort viszont megköveteli Tovább) extra tárhely, ami meglehetősen drága a tömbök számára.

A Quicksortnak különböző indexekhez kell hozzáférnie a műveleteihez, de ez a hozzáférés közvetlenül nem lehetséges a kapcsolt listákban, mivel nincsenek folyamatos blokkok; ezért egy elem eléréséhez meg kell ismételnünk az egyes csomópontokat a csatolt lista elejétől. Ezenkívül a Mergesort külön hely nélkül valósul meg LinkedLists.

Ebben az esetben általában a Quicksort és a Mergesort általános költségnövekedését részesítik előnyben.

5. Következtetés

A Quicksort egy elegáns rendezési algoritmus, amely a legtöbb esetben nagyon hasznos.

Általában „helyben” lévő algoritmus, amelynek átlagos időbeli összetettsége O (n log n).

Egy másik érdekes megemlítendő tény, hogy a Java-ok Tömbök. Rendezés () módszer a primitívek tömbjeinek rendezéséhez használja a Quicksort alkalmazást. A megvalósítás két forgatókönyvet használ, és sokkal jobban teljesít, mint az egyszerű megoldás, ezért a termelési kód esetében általában jobb a könyvtár módszerét használni.

Mint mindig, az algoritmus megvalósításának kódja megtalálható a GitHub adattárunkban.