Sissejuhatus Java kiiresse sortimisse
Järgmine artikkel Java-s pakub kiiret sortimist javas kiire sortimisalgoritmi jaoks. Kiire sortimise algoritm on üks sortimisalgoritmidest, mis on tõhus ja sarnane liitmise sortimise algoritmile. See on üks sagedamini kasutatavaid algoritme reaalajas sorteerimiseks. Selle algoritmi halvim ajaline keerukus on O (n 2), keskmise juhtumi ajaline keerukus on O (n log n) ja parimal juhul aja keerukus on O (n log n).
Ruumi keerukus, kui O (n log n) kus n on sisendi suurus. Sorteerimise protsess hõlmab sisendi eraldamist, rekursiivseid iteratsioone ja iga rekursiooni pöördeelemendi märkimist. Selle algoritmi sortimise tüüp hõlmab külgnevate elementide võrdlemist iteratiivsel viisil.
Kui kiiresti sortimine Java töötab?
Kiire sortimise algoritmi saab Java-s rakendada, moodustades pseudokoodi tõhusalt kavandatud ja järgitud sammude jada abil.
- Kiire sortimisalgoritmi peamine põhimõte, mis töötab, põhineb jagamise ja vallutamise lähenemisel ning on ka tõhus sortimisalgoritm.
- Sisendmassiiv jagatakse alammassiivideks ja jaotus põhineb pöördeelemendil, mis on keskne element. Pöördeelemendi mõlemal küljel olevad alammassiivid on peamised alad, kus sortimine tegelikult toimub.
- Keskne pöördeelement on massiivi jagamise alus kaheks partitsiooniks, kus massiivi elementide vasak pool on väiksem kui pöördeelement ja massiivi elementide parem pool on suurem kui pöördeelement.
- Enne pöördeelemendi kaalumist võib massiivi elementidest olla ükskõik kes. Tavaliselt peetakse seda mõistmise hõlbustamiseks keskmiseks või esimeseks või viimaseks. Pöördelement võib olla mis tahes massiivi elemendist juhuslik.
- Meie näites käsitletakse massiivi viimast elementi pöördeelemendina, kus alammassiivide eraldamine algab massiivi paremast otsast.
- Lõpuks on pöördeelement pärast sortimisprotsessi lõpuleviimist oma tegelikus sorteerimisasendis, kus peamine sortimisprotsess seisneb sortimisalgoritmi partitsiooniloogikas.
- Algoritmi efektiivsus sõltub alammassiivide suurusest ja nende tasakaalust. Mida rohkem alammassiive on tasakaalust väljas, seda rohkem viib aja keerukus halvimal juhul keerukamaks.
- Pöördelementide juhuslik valimine annab paljudel juhtudel parima aja keerukuse, selle asemel, et pöördeelementideks valida konkreetne algus-, lõpp- või keskmine indeks.
Näited Java-s kiirsorteerimise rakendamiseks
QuickSorti algoritm on rakendatud Java programmeerimiskeelt kasutades, nagu allpool näidatud, ja väljundkood on kuvatud koodi all.
- Kood võtab algul sisendi, kasutades meetodit quickSortAlgo (), kasutades argumentidena massiivi, algindeksi ja lõplikku indeksit, st massiivi pikkust.
- Pärast kiirmeetodile QuickSortAlgo () helistamist kontrollib ta, kas algne indeks on väiksem kui lõplik indeks, ja seejärel kutsub arrayPartition () meetodit, et saada pöördeelemendi väärtus.
- Partitsioonielement sisaldab loogikat väiksemate ja suuremate elementide paigutamiseks pöördeelemendi ümber elemendi väärtuste põhjal.
- Pärast pöördeelemendi indeksi saamist pärast partitsioonimeetodi täitmist kutsutakse QuickSortAlgo () meetodit iseenesest rekursiivselt, kuni kõik alammassiivid on jaotatud ja sorteeritud täielikult.
- Partitsiooniloogikas määratakse viimane element pöördeelemendiks ja esimest elementi võrreldakse pöördeelemendiga, st viimasega, kus elemente vahetatakse vastavalt sellele, kas need on väiksemad või suuremad.
- See rekursiooniprotsess toimub seni, kuni kõik massiivi elemendid on jaotatud ja sorteeritud, kus lõpptulemus on kombineeritud sorteeritud massiiv.
- Elemente vahetatakse silmuse iteratsiooni sees ainult juhul, kui element on pöördeelemendist väiksem või sellega võrdne.
- Pärast iteratsiooniprotsessi lõpuleviimist vahetatakse viimane element, st pöördeelemendi väärtus viiakse vasakule küljele, nii et tehakse uued partitsioonid ja sama protsess kordub rekursiooni vormis, mille tulemuseks on sorteerimistoimingute seeria erinevatel võimalikel sektsioonidel antud massiivi elementidest alammassiivide moodustumisena.
- Allpool toodud koodi saab käitada mis tahes IDE-ga ja väljundit saab kontrollida massiivi väärtuse muutmisega põhis () Põhimeetodit kasutatakse ainult väljundi konsooli saamiseks. Java kodeerimisstandardite osana saab põhimeetodi altpoolt eemaldada ja luua objekti ning allpool toodud meetodeid saab kutsuda muutes need mittestaatilisteks.
Koodis kiire sortimisalgoritmi rakendamine Java-s
/*
* 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);
)
)
)
Väljund:
Järeldus
Kiire sortimise algoritm on teiste sorteerimistehnikatega võrreldes tõhus, kuid mitte kuigi stabiilne. Kiire sortimise algoritmide efektiivsus langeb suurema arvu korduvate elementide korral, mis on puuduseks. Selle kiire sortimisalgoritmi abil on ruumi keerukus optimeeritud.
Soovitatavad artiklid
See on juhend Kiire sortimise kohta Java-s. Siin arutleme, kuidas Kiir sortimine Java-s töötab, koos näite ja koodi rakendamisega. Lisateavet leiate ka meie muudest soovitatud artiklitest -
- Hunnik sorteerib Java
- Mis on Java binaarne puu?
- Biti manipuleerimine Java-s
- Ühendamise sort JavaScriptis
- Ülevaade kiirest sortimisest JavaScriptis
- Hunnik sorteerimine Pythonis
- Kuus parimat sortimisalgoritmi JavaScriptis