Introducere în Sortarea rapidă în Java
Următorul articol Sortare rapidă în Java oferă o prezentare a algoritmului de sortare rapidă în Java. Algoritmul de sortare rapidă este unul dintre algoritmii de sortare eficient și similar cu cel al algoritmului de sortare a îmbinărilor. Acesta este unul dintre algoritmii utilizați frecvent în scopuri de sortare în timp real. Complexitatea timpului cel mai rău al acestui algoritm este O (n 2), complexitatea timpului mediu este O (n log n), iar complexitatea timpului cel mai bun este O (n log n).
Complexitatea spațiului dacă O (n log n) unde este n este mărimea intrării. Procesul de sortare implică împărțirea intrării, iterațiile recursive și marcarea unui element pivot pentru fiecare recurs. Tipul de sortare în acest algoritm implică o comparare a elementelor adiacente într-o manieră iterativă.
Cum funcționează Sortarea rapidă în Java?
Algoritmul de sortare rapidă poate fi implementat în Java formând un pseudo-cod cu o secvență de pași proiectați și urmați într-o manieră eficientă.
- Principiul principal al algoritmului de sortare rapidă pe care îl funcționează se bazează pe abordarea divide și cuceri și este, de asemenea, un algoritm eficient de sortare.
- Matricea de intrare este împărțită în sub-matrice și diviziunea se bazează pe elementul pivot care este un element central. Sub-tablele de ambele părți ale elementului pivot sunt principalele domenii în care are loc efectiv sortarea.
- Elementul de pivot central este baza pentru a împărți tabloul în două partiții unde jumătatea stângă a elementelor de tablă este mai mică decât elementul pivot și jumătatea dreaptă a elementelor de tablă este mai mare decât elementul pivot.
- Înainte de a lua în considerare elementul pivot, poate fi oricine din elementele unui tablou. Acest lucru este considerat în mod normal ca unul de mijloc sau primul sau ultimul pentru ușurința înțelegerii. Elementul pivot poate fi unul aleatoriu din oricare dintre elementele matricei.
- În exemplul nostru, ultimul element al unui tablou este considerat un element pivot, unde partiționarea sub-tablelor începe de la capătul drept al tabloului.
- În cele din urmă, elementul pivot va fi în poziția sa reală de sortare după finalizarea procesului de sortare, unde principalul proces de sortare se află în logica de partiție a algoritmului de sortare.
- Eficiența algoritmului depinde de dimensiunea sub-tablelor și de modul în care acestea sunt echilibrate. Cu cât sub-tablele sunt dezechilibrate, cu atât complexitatea timpului va duce la complexitatea cazurilor cele mai grave.
- Selectarea elementelor pivot într-o manieră aleatorie are ca rezultat cea mai bună complexitate de timp, în multe cazuri, în loc să alegeți un anumit indice de început, sfârșit sau mijloc ca elemente pivot.
Exemple pentru implementarea Sortării rapide în Java
Algoritmul QuickSort a fost implementat folosind limbajul de programare Java ca mai jos, iar codul de ieșire a fost afișat sub cod.
- Codul preia inițial folosirea metodei quickSortAlgo () cu tabloul, indexul inițial și indexul final, adică lungimea tabloului ca argumente.
- După apelarea la metoda quickSortAlgo (), verifică dacă indicele inițial este mai mic decât indicele final și apoi apelează la metoda arrayPartition () pentru a obține valoarea elementului pivot.
- Elementul de partiție conține logica aranjării elementelor mai mici și mai mari în jurul elementului pivot pe baza valorilor elementului.
- După obținerea indexului elementului pivot după executarea metodei partiției, metoda QuickSortAlgo () este apelată de la sine în mod recursiv până când toate sub-tablele sunt partiționate și sortate complet.
- În logica partiției, ultimul element este atribuit ca element pivot și primul element este comparat cu elementul pivot, adică ultimul în care elementele sunt schimbate pe baza dacă acestea sunt mai mici sau mai mari.
- Acest proces de recursie se întâmplă până când toate elementele unui tablou sunt partiționate și sortate unde rezultatul final este un tablou sortat combinat.
- Elementele sunt schimbate în interiorul iterației for-loop numai în cazul în care elementul este mai mic sau egal cu elementul pivot.
- După finalizarea procesului de iterație, ultimul element este schimbat, adică valoarea elementului pivot este mutată în partea stângă, astfel încât noile partiții să fie făcute și același proces se repetă sub formă de recursiune, care are ca rezultat o serie de operații de sortare pe diferite partiții posibile. ca o formare de sub-matrice din elementele date.
- Codul de mai jos poate fi rulat pe orice IDE și ieșirea poate fi verificată prin modificarea valorii matricei în principal () Metoda principală este utilizată doar în scopul obținerii ieșirii în consolă. Ca parte a standardelor de codare Java, metoda principală poate fi eliminată mai jos și poate fi creat un obiect și mai jos pot fi apelate metode făcându-le nestatice.
Punerea în aplicare a codului algoritmului de sortare rapidă în Java
/*
* 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);
)
)
)
ieşire:
Concluzie
Algoritmul de sortare rapidă este eficient, dar nu foarte stabil în comparație cu alte tehnici de sortare. Eficiența algoritmilor de sortare rapidă scade în cazul unui număr mai mare de elemente repetate, ceea ce reprezintă un dezavantaj. Complexitatea spațială este optimizată în acest algoritm de sortare rapidă.
Articole recomandate
Acesta este un ghid pentru Sortarea rapidă în Java. Aici vom discuta despre modul de funcționare rapidă în Java împreună cu un exemplu și implementarea codului. Puteți parcurge și alte articole sugerate pentru a afla mai multe -
- Sortare la grămadă în Java
- Ce este un arbore binar în Java?
- Bit Manipulation în Java
- Prezentare generală a Merge Sort în JavaScript
- Prezentare generală a Sortării rapide în JavaScript
- Sort de grămadă în Python
- Top 6 Sortarea algoritmului în JavaScript