Introduktion till snabbsortering i Java
Följande artikel Snabbsortering i Java ger en översikt för snabbsorteringsalgoritmen i java. Snabbsorteringsalgoritmen är en av sorteringsalgoritmerna som är effektiva och liknar den för sammanslagningssorteringsalgoritmen. Detta är en av de vanligaste algoritmerna för realtidsorteringsändamål. Den värsta fallskomplexiteten för denna algoritm är O (n 2), tidskomplexiteten i genomsnitt är O (n log n) och den bästa fallskomplexiteten är O (n log n).
Rymdkomplexiteten om O (n log n) där är n är storleken på ingången. Processen med sortering innebär partitionering av input, rekursiva iterationer och markering av ett viktigt element för varje rekursion. Typen av sortering i denna algoritm innefattar en jämförelse av intilliggande element på ett iterativt sätt.
Hur fungerar snabbsortering i Java?
Snabbsorteringsalgoritm kan implementeras i Java genom att bilda en pseudokod med en sekvens av steg designade och följda på ett effektivt sätt.
- Huvudprincipen för den snabba sorteringsalgoritmen som den fungerar är baserad på uppdelningen och erövringstrategin och är också en effektiv sorteringsalgoritm.
- Inmatningsfältet är uppdelat i undermatriser och indelningen baseras på ett svängelement som är ett centralt element. Delmatriserna på vardera sidan av pivotelementet är huvudområdena där sorteringen faktiskt sker.
- Det centrala svängningselementet är basen för att dela upp matrisen i två partitioner där den vänstra halvan av matriselementen är mindre än svängelementet och den högra halvan av matriselementen är större än svängelementet.
- Innan man tänker på pivotelementet kan det vara vem som helst från elementen i en matris. Detta betraktas normalt som mitt eller första eller sista för att underlätta förståelsen. Pivotelementet kan vara slumpmässigt från vilket som helst av arrayelementen.
- I vårt exempel betraktas det sista elementet i en matris som ett pivotelement, där delningen av undermatriser startar från den högra änden av matrisen.
- Slutligen kommer pivotelementet att vara i sitt faktiska sorterade läge efter avslutad sorteringsprocess, där huvudprocessen för sortering ligger i partitionslogiken för sorteringsalgoritmen.
- Effektiviteten för algoritmen beror på storleken på undermatriserna och hur de är balanserade. Ju mer deluppsättningarna är obalanserade, desto mer kommer tidskomplexiteten att leda till värsta fall.
- Valet av pivotelement på ett slumpmässigt sätt resulterar i bästa tidskomplexitet i många fall istället för att välja ett specifikt start-, slut- eller mittindex som pivotelement.
Exempel på implementering av snabbsortering i Java
QuickSort-algoritmen har implementerats med Java-programmeringsspråk enligt nedan och utgångskoden har visats under koden.
- Koden tar initialt inmatningen med metoden quickSortAlgo () med arrayen, initialindex och slutindex, dvs längden på arrayen som argument.
- Efter att ha ringt metoden quickSortAlgo () kontrollerar den om det initiala indexet är mindre än det slutliga indexet och anropar sedan metoden arrayPartition () för att få ett pivotelementvärde.
- Partitionselementet innehåller logiken för att ordna de mindre och större elementen runt pivotelementet baserat på elementvärdena.
- Efter att ha fått pivotelementindexet efter genomförandet av partitionsmetoden kallas metoden quickSortAlgo () av sig själv rekursivt tills alla delarrayerna är partitionerade och sorterade helt.
- I partitionslogiken tilldelas det sista elementet som pivotelement och det första elementet jämförs med pivotelementet, dvs det sista elementet där elementen byts ut baserat på om de är mindre eller större.
- Denna rekursionsprocess sker tills alla element i en matris är indelade och sorterade där det slutliga resultatet är en kombinerad sorterad matris.
- Elementen byts in i for-loop-iterationen endast om elementet är mindre än eller lika med svängelementet.
- Efter att iterationsprocessen har slutförts byts det sista elementet, dvs. pivotelementvärdet flyttas till vänster så att de nya partitionerna görs och samma process upprepas i form av rekursion vilket resulterar i serie sorteringsoperationer på olika möjliga partitioner som en bildning av undermatriser från de givna matriselementen.
- Nedanstående kod kan köras på valfri IDE och utgången kan verifieras genom att ändra matrisvärdet i huvudmenyn () Huvudmetoden används bara för att få utdata i konsolen. Som en del av Java-kodningsstandarder kan huvudmetoden tas bort nedanför och ett objekt kan skapas och metoder under nedan kallas genom att göra dem icke-statiska.
Kodimplementering av snabbsorteringsalgoritm i 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);
)
)
)
Produktion:
Slutsats
Snabbsorteringsalgoritmen är effektiv men inte mycket stabil jämfört med andra sorteringstekniker. Effektiviteten för snabbsorteringsalgoritmer minskar i fallet med ett större antal upprepade element, vilket är en nackdel. Rymdkomplexiteten är optimerad i denna snabbsorteringsalgoritm.
Rekommenderade artiklar
Detta är en guide till snabbsortering i Java. Här diskuterar vi hur Quick Sort fungerar i Java tillsammans med ett exempel och implementering av kod. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer -
- Heap Sort In Java
- Vad är ett binärt träd i Java?
- Bitmanipulation i Java
- Översikt över Sortera i JavaScript
- Översikt över snabbsortering i JavaScript
- Heap Sort i Python
- Topp 6 sorteringsalgoritm i JavaScript