Introduktion til hurtig sorteringsalgoritmer i Java
Hurtig sortering i java, også kendt som partitionsudvekslingssortering, er en split og erobre sorteringsalgoritme. Hurtig sortering er et godt eksempel på en algoritme, der bedst bruger CPU-cacher på grund af dens kløft og erobrer karakter. Quicksort-algoritme er en af de mest anvendte sorteringsalgoritmer, især til at sortere de store lister, og de fleste programmeringssprog har implementeret den. I Quicksort-algoritmen er de originale data opdelt i to dele, der sorteres individuelt og derefter flettes for at producere sorterede data.
Lad os overveje, at matrixen (8, 6, 3, 4, 9, 2, 1, 7) skal sorteres ved hjælp af Quick Sort.
Trin til implementering af hurtig sorteringsalgoritmer
1. Vælg et element kaldet pivot fra matrixen. Generelt vælges det midterste element som drejepunktet. Lad os tage 4 som omdrejningspunktet.
2. Omarrangør arrayet i to dele, således at elementer, der er mindre end drejepinden, kommer før drejepoten, og elementer, der er større end pivotten, vises efter pivotten. Følgende trin følges:
- Vælg det venstre element dvs. 8, da 4 er drejepunktet og 8 er mere end 4, skal 8 flyttes til højre for 4, På højre side forlader vi 7, da det er større end 4 og vælg 1 for at skifte med 8 deraf efter udskiftning bliver array: 1, 6, 3, 4, 9, 2, 8, 7
- Vælg det næste venstre element, dvs. 6, Da 4 er drejepunktet, og 6 er mere end 4, skal 6 flyttes til højre for 4. På højre side forlader vi 7, 8, da de er større end 4 og vælger 2 til at udskifte med 6 og derefter efter at have udskiftet arrayet bliver: 1, 2, 3, 4, 9, 6, 8, 7
- Da alle elementer til venstre for pivoten er mindre end pivoten og alle elementer til højre for pivot er større end pivot, er vi færdige med 4 som pivot.
3. Anvend rekursivt trin 1 og 2 for den venstre undergruppe (matrix med elementer mindre end pivotten) og for den højre undergruppe (matrix med elementer mere end pivotten). Hvis arrayet kun indeholder et eller nulelementer, betragtes arrayet som assorteret.
Program til implementering af hurtig sorteringsalgoritmer
Her er et java-program til sortering af en række heltal ved hjælp af en hurtig sorteringsalgoritme.
Kode:
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));
)
)
Produktion:
Fordele ved hurtig sorteringsalgoritmer
Følgende er fordelene ved den hurtige sorteringsalgoritme:
- Fremragende referenceplacering: Referencens lokalitet er en processor's evne til at få adgang til den samme hukommelsesplacering gentagne gange over en kort periode. Hurtig sortering i java giver en fremragende lokalitet af reference på grund af det meget lille antal cache-fejl, som på moderne arkitekturer er kritisk for ydeevnen.
- Hurtig sortering er parallel: Når det første trin med opdeling af en matrix i mindre regioner er afsluttet, kan alle de individuelle undergrupper sorteres uafhængigt parallelt. På grund af denne årsag fungerer hurtig sortering bedre.
Kompleksitetsanalyse af hurtig sortering
Quicksort er en hurtig og halerekursiv algoritme, der fungerer efter skillet og erobre-princippet. Her er dens kompleksitetsanalyse i bedste, gennemsnitlige og værste tilfælde:
- Bedste sagskomplexitet: Hvis en matrix eller en liste indeholder n elementer, skal den første kørsel have O (n). Nu sorterer de resterende to undergrænser 2 * O (n / 2). Dette konkluderer i det bedste tilfælde kompleksiteten af O (n logn).
- Gennemsnitlig sagskompleksitet: Det gennemsnitlige tilfælde af quicksort er O (n log n).
- Værste sagskompleksitet: Valg af første eller sidste ville medføre dårligst mulige resultater for næsten sorterede eller næsten omvendt sorterede data. Hurtig sortering udfører O (n 2) i værste tilfælde.
I Java, Arrays. Sortering () -metoden bruger en hurtig sorteringsalgoritme til at sortere en matrix.
Anbefalede artikler
Dette er en guide til hurtig sorteringsalgoritmer i Java. Her diskuterer vi trinnene til implementering, fordele og kompleksitetsanalyse af en hurtig sorteringsalgoritme i java sammen med program. Du kan også se på de følgende artikler for at lære mere -
- Indsættelsessortering i Java
- do-while-loop i Java
- JComponent i Java
- Firkanter i Java
- Udskiftning af PHP
- Sorterer i C #
- Sorterer i Python
- C ++ algoritme | Eksempler på C ++ algoritme