Snabb sortera (5 / 7 steg)

Steg 5: Genomför qs_partition

Bakgrund

Innan jag går att implementera funktionen quick_sort, måste vi förstå att quick_sort inte göra mycket arbete själv. Vår qs_partition funktion gör det mesta av arbetet. qs_partition tar en vektor med heltal, en vänster gräns i arrayen och en höger fältetikettsgräns i arrayen som parametrar och returnerar ett heltal, precis som huvudsakliga.

* Obs: eftersom ett bibliotek vi använder (algorithm.h) redan har en funktion kallad partition, vi kallar våra partition funktion qs_partition.

Mål

Qs_partition uppgift är att välja ett nummer i matrisen som en pivot och separera alla talen i matrisen in i två grupper: de som är mindre än eller lika med pivot och de som är större. Det förlägger alla mindre eller lika nummer innan pivot och alla större nummer efter. Här är ett sätt som kan vara fulländad.

Steg

1) qs_partition först tar det första är det tillåtet att röra (objektet i den vänstra gränsen) och kallar det en pivot. Det finns inget speciellt händer här. Funktionen gör först bara förklara att ett värde som kallas pivot är lika med det första objektet som funktionen tillåts att få tillgång till.

2) på samma sätt, vi kallar en variabel toSwap och tilldela den index av vridningen.

3) vi kör sedan genom arrayen, titta på varje objekt från det andra värdet till på höger fältetikettsgräns. Vi jämföra inte det första värdet till värdet som pivot eftersom först värde är värdet som pivot.

4) på varje plats jämför vi värdet vid den platsen till våra pivot. Om värdet är mindre än eller lika med pivot, vill vi flytta värdet så långt mot början av matrisen som möjligt. Det är där toSwap kommer in. Vi ska byta värdet vid toSwap (eftersom toSwap är ett index) och det aktuella värdet ser vi, då vi ska öka toSwap med ett så vi inte byta ut de värden tillbaka ut i mitten av matrisen.

5) när vi har kört igenom alla nummer, representerar vårt toSwap index platsen där vi vill placera våra pivot. Så ska vi byta det vid toSwap och pivot värdet. Slutligen vi kommer tillbaka, eller skickas tillbaka till den funktion som kallas qs_partition, index för där vi sätter pivot. Här ser du varför snart.

Recension

Förhoppningsvis kan du se att vi har skapat den önskade effekten genom att byta sekventiellt tal mindre än pivot till första plats efter vår senaste swap,: alla siffror innan pivot är mindre än eller lika med pivot och alla siffror efter den större.