Introduktion till snabbsorteringsalgoritmer i Java
Snabbsortering i java, även känd som partition-exchange sort, är en klyvnings- och erövringssorteringsalgoritm. Snabbsortering är ett bra exempel på en algoritm som utnyttjar CPU-cachemakar bäst på grund av dess uppdelning och erövring. Quicksort-algoritmen är en av de mest använda sorteringsalgoritmerna, särskilt för att sortera de stora listorna och de flesta programmeringsspråk har implementerat den. I Quicksort-algoritmen delas originaldata upp i två delar som sorteras individuellt och sedan slås samman för att producera sorterade data.
Låt oss överväga att matrisen (8, 6, 3, 4, 9, 2, 1, 7) måste sorteras med Quick Sort.
Steg för att implementera snabbsorteringsalgoritmer
1. Välj ett element som heter pivot i matrisen. Generellt väljs mittelementet som pivot. Låt oss ta 4 som pivot.
2. Ordna arrayen i två delar så att element som är mindre än pivot kommer före pivot och element som är större än pivot visas efter pivot. Följande steg följs:
- Välj det vänstra elementet dvs 8, eftersom 4 är pivoten och 8 är mer än 4, 8 måste flyttas till höger om 4, på höger sida lämnar vi 7 eftersom det är större än 4 och plock 1 för att byta med 8 därmed efter byte av array blir: 1, 6, 3, 4, 9, 2, 8, 7
- Välj nästa vänstra element dvs 6, Eftersom 4 är pivot och 6 är mer än 4, måste 6 flyttas till höger om 4, På höger sida lämnar vi 7, 8 eftersom de är större än 4 och plockar 2 för att byta med 6 följaktligen efter att ha bytt ut arrayen blir: 1, 2, 3, 4, 9, 6, 8, 7
- Nu eftersom alla element till vänster om pivot är mindre än pivot och alla element till höger om pivot är större än pivot, är vi färdiga med 4 som pivot.
3. Använd rekursivt steg 1 och 2 för den vänstra deluppsättningen (matris med element mindre än pivoten) och för den högra undergruppen (matris med element mer än pivoten). Om matrisen endast innehåller ett eller nollelement, betraktas arrayen som blandad.
Program för att implementera snabbsorteringsalgoritmer
Här är ett java-program för att sortera en rad heltal med hjälp av en snabbsorteringsalgoritm.
Koda:
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:
Fördelar med snabbsorteringsalgoritmer
Följande är fördelarna med den snabba sorteringsalgoritmen:
- Utmärkt referensort: Referensplatsen är en processor förmåga att få åtkomst till samma minnesplats upprepade gånger under en kort tidsperiod. Snabb sortering i java ger utmärkt referensplats på grund av det mycket lilla antalet cachemissningar, som på moderna arkitekturer är avgörande för prestanda.
- Snabbsortering är parallelliserbar: När det första steget att dela upp en matris i mindre regioner är klar kan alla enskilda delområden sorteras oberoende parallellt. På grund av detta orsakar snabb sortering bättre.
Komplexitetsanalys av snabb sortering
Quicksort är en snabb och svansrekursiv algoritm som fungerar enligt dividerings- och erövringsprincipen. Här är dess komplexitetsanalys i bästa, genomsnittliga och värsta fall:
- Bästa fallskomplexitet: Om en matris eller en lista innehåller n-element behöver den första körningen O (n). Sortering av återstående två delområden tar nu 2 * O (n / 2). Detta avslutar i bästa fall komplexiteten hos O (n logn).
- Genomsnittlig fallkomplexitet: Det genomsnittliga fallet med kvicksort är O (n log n).
- Värsta fallskomplexitet: Att välja första eller sista skulle orsaka värsta fall för nästan sorterade eller nästan omvänd sorterade data. Snabbsortering utför O (n 2) i värsta fall.
I Java, Arrays. Metoden Sortering () använder en snabbsorteringsalgoritm för att sortera en matris.
Rekommenderade artiklar
Detta är en guide till snabbsorteringsalgoritmer i Java. Här diskuterar vi stegen för att implementera, fördelar och komplexitetsanalys av en snabb sorteringsalgoritm i java tillsammans med program. Du kan också titta på följande artiklar för att lära dig mer -
- Insättningssortering i Java
- gör-medan-loop i Java
- JComponent i Java
- Kvadrater i Java
- Byta in PHP
- Sorterar i C #
- Sorterar i Python
- C ++ algoritm | Exempel på C ++ -algoritm