Bevezetés a Java gyors rendezéséhez
A Java gyorsjelentés a következő cikkben felvázolja a java gyors gyorsrendezési algoritmusát. A Gyors rendezési algoritmus az egyik a válogatási algoritmus, amely hatékony és hasonló az egyesítési rendezési algoritmushoz. Ez az egyik leggyakrabban alkalmazott algoritmus valós idejű rendezési célokra. Ennek az algoritmusnak a legrosszabb esetbeli ideje bonyolultsága O (n 2), az átlagos esetidő bonyolultsága O (n log n), és a legjobb eset es időbonyolultsága O (n log n).
A hely bonyolultsága, ha O (n log n), ahol n, a bemenet mérete. A válogatás folyamata magában foglalja a bemenetek particionálását, a rekurzív iterációkat és az egyes rekurziókhoz tartozó forgó elem megjelölését. A szortírozás típusa ebben az algoritmusban a szomszédos elemek iteratív összehasonlítását foglalja magában.
Hogyan működik a Gyors rendezés a Java-ban?
A Gyors rendezés algoritmus Java-ban megvalósítható úgy, hogy ál állati kódot hoz létre, hatékonyan megtervezett és követett lépések sorozatával.
- A gyors rendezési algoritmus működésének fő elve az osztás és meghódítás megközelítésén alapul, és egyben hatékony rendezési algoritmus.
- A bemeneti tömb al-tömbökre oszlik és a felosztás egy pivot elemre épül, amely egy központi elem. A forgó elem mindkét oldalán található al-tömbök a fő területek, ahol a rendezés ténylegesen megtörténik.
- A központi forgó elem az az alap, amely a tömeget két partícióra osztja, ahol a tömb elemek bal oldala kevesebb, mint a forgó elem, és a tömb elemek jobb fele nagyobb, mint a forgó elem.
- A pivot elem megfontolása előtt bárki lehet a tömb elemeiből. Ezt a megértés megkönnyítése érdekében általában középsőnek, elsőnek vagy utolsónak tekintik. A pivot elem véletlenszerű lehet bármelyik tömb elemből.
- Példánkban a tömb utolsó elemét pivot elemnek tekintjük, ahol az al-tömbök particionálása a tömb jobb végétől kezdődik.
- Végül a pivot elem a rendezési folyamat befejezése után a tényleges rendezett helyzetében lesz, ahol a rendezés fő folyamata a rendezési algoritmus partíció logikájában rejlik.
- Az algoritmus hatékonysága az al-tömbök méretétől és azok kiegyensúlyozottságától függ. Minél inkább az al-tömbök nem kiegyensúlyozottak, annál inkább az idő bonyolultsága vezet a legrosszabb eset komplexitásához.
- A pivot elemek véletlenszerű kiválasztása sok esetben a legjobb időösszeállítást eredményezi, ahelyett, hogy egy adott kezdési, befejezési vagy középső indexet választanunk pivot elemként.
Példák a gyors rendezés végrehajtására a Java-ban
A QuickSort algoritmust az alábbiakban ismertetett Java programozási nyelv segítségével valósítottuk meg, és a kimeneti kód a kód alatt jelenik meg.
- A kód kezdetben a quickSortAlgo () módszer felhasználásával veszi a bemenetet, a argumentumként a tömböt, a kezdõ indexet és a végsõ indexet, azaz a tömb hosszát.
- A quickSortAlgo () metódus meghívása után megvizsgálja, hogy a kezdeti index kevesebb-e a végső indexnél, majd felhívja az arrayPartition () metódust, hogy megkapja a pivot elem értékét.
- A partíció elem tartalmazza a kisebb és nagyobb elemek elrendezésének logikáját a pivot elem körül az elem értékei alapján.
- Miután megkapta a pivot elemindexet a partíciós módszer végrehajtása után, a quickSortAlgo () metódusát önmagában rekurzív módon hívjuk meg, amíg az összes al-tömb nem lesz partícionálva és teljesen rendezve.
- A partíció logikában az utolsó elem pivot elemként van hozzárendelve, és az első elemet összehasonlítják a pivot elemmel, azaz az utolsó elemmel, amelyben az elemeket kicserélik annak alapján, hogy kisebbek vagy nagyobbak.
- Ez a rekurzációs folyamat mindaddig zajlik, amíg a tömb összes elemét nem osztják és rendezik, ahol a végeredmény egy kombinált rendezett tömb.
- Az elemeket csak a hurok iterációjában cseréljük, csak abban az esetben, ha az elem kisebb vagy egyenlő, mint a forgó elem.
- Az iterációs folyamat befejezése után az utolsó elemet felcserélik, azaz a pivot elem értékét balra mozgatják úgy, hogy új partíciókat készítsenek, és ugyanaz a folyamat ismétlődjön ismétlés formájában, amely a különböző lehetséges partíciókon történő rendezési műveletek sorozatát eredményezi alcsoportok kialakulásaként az adott tömb elemekből.
- Az alábbi kód bármilyen IDE-n futtatható, és a kimenet a main tömb értékének megváltoztatásával ellenőrizhető (). A fő módszert csak arra használják, hogy a kimenetet a konzolba hozzák. A Java kódolási szabványok részeként a fő módszer az alábbiak szerint eltávolítható, és létrehozható egy objektum, és az alábbi módszereket úgy lehet meghívni, hogy nem-statikussá teszik őket.
A gyors rendezési algoritmus kódvégrehajtása Java-ban
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Kimenet:
Következtetés
A gyors rendezési algoritmus hatékony, de nem sokkal stabilabb más válogatási technikákhoz képest. A gyors rendezési algoritmusok hatékonysága csökken az ismételt elemek nagyobb száma esetén, ami hátrány. Ebben a gyors rendezési algoritmusban optimalizálódik a tér komplexitása.
Ajánlott cikkek
Ez a útmutató a Gyors rendezés Java-ban. Itt tárgyaljuk, hogyan működik a Gyors rendezés a Java-ban, egy példával és a kód megvalósításával együtt. A további javasolt cikkeken keresztül további információkat is megtudhat -
- Heap Sort in Java
- Mi a bináris fa Java-ban?
- Bitmanipuláció Java-ban
- A Merge Sort áttekintése a JavaScript-en
- A gyors rendezés áttekintése a JavaScript-ben
- Halom Rendezés Pythonban
- A 6 legnépszerűbb rendezési algoritmus a JavaScript-ben