Introducere în algoritmii de sortare rapidă în Java
Sortarea rapidă în Java, de asemenea, cunoscut sub numele de partition-schimb sortare este un algoritm de împărțire și cucerire. Sortarea rapidă este un bun exemplu de algoritm care face cea mai bună utilizare a cache-urilor CPU, din cauza divizării sale și a cucerit natura. Algoritmul Quicksort este unul dintre cei mai folosiți algoritmi de sortare, în special pentru a sorta listele mari și majoritatea limbajelor de programare l-au implementat. În algoritmul Quicksort, datele originale sunt împărțite în două părți, care sunt sortate individual și apoi îmbinate pentru a produce date sortate.
Să luăm în considerare faptul că tabloul (8, 6, 3, 4, 9, 2, 1, 7) trebuie sortat folosind Sortare rapidă.
Pași pentru implementarea algoritmilor de sortare rapidă
1. Alegeți un element numit pivot din tablou. În general, elementul de mijloc este ales ca pivot. Să luăm 4 ca pivot.
2. Reorganizați tabloul în două părți astfel încât elementele mai mici decât pivot să vină înainte de pivot și elemente mai mari decât pivot să apară după pivot. Urmați următorii pași:
- Alegeți elementul din stânga, adică 8, întrucât 4 este pivotul și 8 este mai mult de 4, 8 trebuie mutat la dreapta 4, în partea dreaptă lăsăm 7, deoarece este mai mare de 4 și alege 1 pentru schimbare cu 8 prin urmare, după schimbarea tabloului devine: 1, 6, 3, 4, 9, 2, 8, 7
- Alegeți următorul element din stânga, adică 6, întrucât 4 este pivot și 6 este mai mult de 4, 6 trebuie să fie mutați la dreapta 4, în partea dreaptă lăsăm 7, 8, deoarece sunt mai mari de 4 și alegeți 2 pentru schimbarea cu 6, prin urmare, după schimbarea tabloului devine: 1, 2, 3, 4, 9, 6, 8, 7
- Acum, deoarece toate elementele din stânga pivotului sunt mai mici decât pivotul și toate elementele din dreapta pivotului sunt mai mari decât pivotul, am terminat cu 4 ca pivot.
3. Aplicați periodic pașii 1 și 2 pentru sub-tabloul din stânga (tablou cu elemente mai mici decât pivotul) și pentru sub-tabloul drept (tablou cu elemente mai mult decât pivotul). Dacă tabloul conține doar unul sau zero elemente, atunci tabloul este considerat asortat.
Program pentru implementarea algoritmilor de sortare rapidă
Iată un program java pentru a sorta o serie de numere întregi folosind un algoritm de sortare rapidă.
Cod:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
ieşire:
Avantajele algoritmilor de sortare rapidă
Următoarele sunt avantajele algoritmului de sortare rapidă:
- Localitate excelentă de referință: localitatea de referință este capacitatea unui procesor de a accesa aceeași locație de memorie în mod repetat într-o perioadă scurtă de timp. Sortarea rapidă în java oferă o localitate excelentă de referință datorită numărului foarte mic de ratări ale memoriei cache, ceea ce în arhitecturile moderne este esențial pentru performanță.
- Sortarea rapidă este paralelă: odată ce pasul inițial de repartizare a unui tablou în regiuni mai mici este finalizat, toate subordonările individuale pot fi sortate independent în paralel. Datorită acestui motiv, sortarea rapidă se comportă mai bine.
Analiza complexității sortării rapide
Quicksort este un algoritm rapid și recursiv, care funcționează după principiul divizării și cuceririi. Iată analiza complexității sale în cel mai bun, mediu și cel mai rău caz:
- Cea mai bună complexitate a cazurilor: Dacă un tablou sau o listă conține n elemente, prima execuție va avea nevoie de O (n). Acum, Sortarea celor două sub-parcări rămâne 2 * O (n / 2). Aceasta concluzionează complexitatea O (n logn) în cel mai bun caz.
- Complexitatea medie a cazului : Cazul mediu de interogare este O (n log n).
- Complexitatea cea mai rea a cazurilor: alegerea primului sau ultimul ar duce la performanțele cele mai grave pentru datele aproape sortate sau aproape inversate. Sortarea rapidă efectuează O (n 2) în cel mai rău caz.
În Java, Arrayuri. Metoda Sort () folosește un algoritm de sortare rapidă pentru a sorta un tablou.
Articole recomandate
Acesta este un ghid pentru Sortarea rapidă a algoritmilor în Java. Aici discutăm pașii de implementare, avantajele și analiza complexității unui algoritm de sortare rapidă în Java împreună cu programul. De asemenea, puteți consulta următoarele articole pentru a afla mai multe -
- Sortare inserție în Java
- bucla do-while în Java
- JComponent în Java
- Pătrate în Java
- Schimbarea în PHP
- Sortare în C #
- Sortare în Python
- C ++ Algoritm | Exemple de algoritm C ++