Meny

QuickSort i Java - algoritm, illustration och implementering

  • Huvud
  • Övrig
  • QuickSort i Java - algoritm, illustration och implementering

quicksort java algorithm

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning förklarar Quicksort-algoritmen i Java, dess illustrationer, QuickSort-implementering i Java med hjälp av kodexempel:

Quicksort-sorteringsteknik används ofta i programvaruapplikationer. Quicksort använder en divide-and-conquer-strategi som merge sort.

I quicksort-algoritmen väljs först ett specialelement som kallas 'pivot' och arrayen eller listan i fråga är uppdelad i två delmängder. De partitionerade delmängderna kan eller kanske inte vara lika stora.

=> Läs igenom Easy Java Training Series.

standardgateway inte tillgängligt Windows 10

QuickSort-teknik i Java

Mellanväggarna är sådana att alla element som är mindre än svängelementet är till vänster om svängningen och elementen större än svängningen är till höger om svängningen. Quicksort-rutinen sorterar rekursivt de två underlistorna. Quicksort fungerar effektivt och även snabbare även för större matriser eller listor.

Vad du kommer att lära dig:

Quicksort Partition Java

Partitionering är nyckelprocessen för Quicksort-tekniken. Så vad är partitionering?

Med en matris A väljer vi ett värde x som kallas pivot så att alla element som är mindre än x är före x och alla element som är större än x är efter x.

Ett pivotvärde kan vara något av följande:

  • Det första elementet i matrisen
  • Det sista elementet i matrisen
  • Mittelementet i matrisen
  • Alla slumpmässiga element i matrisen

Detta pivotvärde placeras sedan i rätt position i arrayen genom att partitionera arrayen. Således är utgången från 'partitioneringsprocessen' svängvärdet i rätt läge och elementen mindre än sväng till vänster och element större än en sväng till höger.

Tänk på följande diagram som förklarar partitioneringsprocessen.

partitioneringsprocess

Ovanstående diagram visar processen för partitionering av array genom att upprepade gånger välja det sista elementet i arrayen som en pivot. Observera att vi på varje nivå delar upp matrisen i två undergrupper genom att placera ledpunkten i rätt position.

Därefter listar vi algoritmen och pseudokoden för quicksort-teknik som också inkluderar partitionsrutin.

Quicksort Algorithm Java

Den allmänna algoritmen för quicksort ges nedan.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Nedan anges pseudokoden för quicksort-tekniken.

Pseudokod för snabb sortering

Följande är pseudokoden för en snabb sorteringsteknik. Observera att vi har tillhandahållit pseudokoden för snabbsortering och partitioneringsrutin.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

Illustration

Låt oss se illustrationen av quicksort-algoritmen. Ta följande array som ett exempel. Här har vi valt det sista elementet som pivot.

Som visat är det första elementet märkt lågt och det sista elementet är högt.

Illustration av Quicksort-algoritmen

Som framgår av ovanstående illustration finns det två pekare, höga och låga som pekar på det sista och första elementet i matrisen. Båda dessa pekare flyttas när snabbsorten fortskrider.

När elementet som pekas av den låga pekaren blir större än pivotelementet och elementet som pekas av den höga pekaren är mindre än pivotelementet, byter vi ut de element som pekas av den låga och höga pekaren, och varje pekare går framåt med en position.

Ovanstående steg utförs tills båda pekarna korsar varandra i matrisen. När de har passerat får ledelementet sin rätta position i matrisen. Vid denna tidpunkt är matrisen partitionerad och nu kan vi sortera varje undergrupp oberoende genom att rekursivt tillämpa en snabb sorteringsalgoritm på var och en av undergruppen.

Quicksort-implementering i Java

QuickSort-tekniken kan implementeras i Java med antingen rekursion eller iteration. I detta avsnitt kommer vi att se båda dessa tekniker.

Rekursivt Quicksort

Vi vet att den grundläggande tekniken för quicksort som illustreras ovan använder rekursion för att sortera matrisen. I det rekursiva quicksortet efter partitionering av arrayen kallas quicksort-rutinen rekursivt för att sortera underarrayerna.

Nedanstående implementering visar quicksort-tekniken med rekursion.

import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Produktion:

Originalmatris: (4, -1, 6, 8, 0, 5, -3)
Sorterad matris: (-3, -1, 0, 4, 5, 6, 8)

Rekursivt snabbsort - utdata

Iterativ Quicksort

I iterativ quicksort använder vi hjälpstacken för att placera mellanparametrar istället för att använda rekursions- och sorteringspartitioner.

Följande Java-program implementerar iterativ quicksort.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Produktion:

Originalmatris: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Sorterad matris: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Iterativ snabbsort - utdata

Vanliga frågor

F # 1) Hur fungerar en Quicksort?

Svar: Quicksort använder en splittring och erövrar strategi. Quicksort partitionerar först en array runt ett valt pivotelement och genererar underarrayer som sorteras rekursivt.

F # 2) Vad är tidskomplexiteten för Quicksort?

Svar: Tidskomplexiteten för quicksort i genomsnitt är O (nlogn). I värsta fall är det O (n ^ 2) samma som urvalssorteringen.

F # 3) Var används Quicksort?

Svar: Quicksort används mest i rekursiva applikationer. Quicksort är delen av C-biblioteket. Dessutom implementerar nästan programmeringsspråken som använder inbyggd sortering quicksort.

F # 4) Vilken är fördelen med Quicksort?

Svar:

  • Quicksort är en effektiv algoritm och kan enkelt sortera även en enorm lista med element.
  • Den är på plats och behöver därför inte extra utrymme eller minne.
  • Det används ofta och ger ett effektivt sätt att sortera datamängder av vilken längd som helst.

F # 5) Varför är Quicksort bättre än sammanslagningen?

Svar: Den främsta anledningen till att quicksort är bättre än merge-sorteringen är att quicksort är en sorteringsmetod på plats och inte kräver ytterligare minnesutrymme. Sammanfoga sortering kräver ytterligare minne för mellanliggande sortering.

Slutsats

Quicksort anses vara den bästa sorteringsalgoritmen främst på grund av dess effektivitet att sortera till och med en enorm datamängd på O (nlogn) -tid.

Quicksort är också en platssortering och kräver inte extra minnesutrymme. I den här handledningen har vi sett det rekursiva och iterativa genomförandet av quicksort.

I vår kommande handledning fortsätter vi med sorteringsmetoder i Java.

=> Ta en titt på Java-nybörjarguiden här.

Rekommenderad läsning

^