Sortering av tegn på en C ++ -streng
Datamaskiner behandler strenger i operasjoner på karakternivå og lagrer dem i minnet, så alle Sorteringsalgoritme må vurdere strømmen av byte i strengen, så vel som deres numeriske eller alfabetiske forhold. Denne artikkelen vil dekke trinnene for å implementere de vanligste sorteringsalgoritmene for C ++ strenger.
Sortering av tegn på en C ++ -streng
Det er fem metoder for å sortere en streng som gitt:
- Valgssorter
- Innsettingssort
- Boble sort
- Rask sorter
- Sorter () funksjon
1: Valgssorter
Valgssorter er en sammenligningsbasert sorteringsalgoritme som fungerer ved å dele inngangen i to deler: en sublist av sortert tegn og en sublist av usortert tegn. Algoritmen søker deretter etter den usorterte sublisten etter det minste elementet og plasserer det minste elementet i sublisten til sorterte tegn. Den fortsetter denne prosessen til hele strengen er sortert.
Å implementere Valgssorter I C ++ vil vi bruke følgende trinn.
Trinn 1: Opprett en for sløyfe som starter med karakterindeks jeg lik 0. Løkken vil iterere gjennom strengen en gang.
Steg 2: Sett minimumsindeksen til i.
Trinn 3: Lag et nestet for sløyfe som starter med karakterindeks j lik I+1. Loopen vil iterere gjennom de gjenværende tegnene i strengen.
Trinn 4: Sammenlign tegnet ved indeks I med tegnet ved indeks j. Hvis tegnet ved indeks j er mindre enn tegnet ved indeks I, setter vi minimumsindeksen til j.
Trinn 5: Etter det nestet for sløyfe, bytter vi karakteren i minimumsindeks med tegnet ved indeks I.
Trinn 6: Gjenta trinn 1-5 til vi kommer til slutten av strengen.
Programmet for utvalgssort er gitt nedenfor:
#inkludere#inkludere
ved hjelp av navneområdet STD;
void SelectionSort (String & S)
int len = s.lengde();
for (int i = 0; i< len-1; i++)
int minindex = i;
for (int j = i+1; j
minindex = j;
if (minindex != i)
Swap (S [i], S [Minindex]);
int main ()
String str = "Dette er en sorteringsalgoritme";
cout<< "Original string was: " << str <
cout<< "Sorted string is: " << str <
I koden ovenfor sendes en strengreferanse inn i utvalg funksjon, som sorterer strengen på stedet. Ved å iterere over strengen fra gjeldende posisjon til slutten, identifiserer funksjonen det minste elementet i den usorterte delen av strengen. Elementet på det nåværende stedet i strengen blir slått ut for det minimale elementet etter at det er bestemt. Denne prosedyren gjentas for hvert element i strengen i funksjonens ytre sløyfe til hele strengen er ordnet i ikke-avtagende rekkefølge.
Produksjon
2: innsettingssort
Innsettingssort er en annen sammenligningsbasert sorteringsalgoritme og fungerer ved å dele inngangen i sorterte og usorterte deler. Algoritmen itererer deretter gjennom den usorterte delen av inngangen og legger elementet i sin riktige posisjon mens de skifter de større elementene mot høyre. For å gjøre dette, bør følgende trinn følges:
Trinn 1: Opprett en for loop som starter med karakterindeksen I lik 1. Løkken vil iterere gjennom strengen en gang.
Steg 2: Angi variabel -tasten lik tegnet ved indeks I.
Trinn 3: Lag et nestet mens sløyfe som starter med karakterindeks j lik i-1. Løkken vil iterere gjennom den sorterte delen av strengen.
Trinn 4: Sammenlign tegnet ved indeks j med variabel -tasten. Hvis variabel -tasten er mindre enn tegnet ved indeks J, bytter vi tegnet ved indeks J med tegnet ved indeks J+1. Sett deretter variabelen J lik J-1.
Trinn 5: Gjenta trinn 4 til j er større enn eller lik 0 eller variabel -tasten er større enn eller lik tegnet ved indeks j.
Trinn 6: Gjenta trinn 1-5 til vi kommer til slutten av strengen.
#inkludere#inkludere
ved hjelp av navneområdet STD;
int main ()
streng str;
cout<< "Original string was: " ;
getline (cin, str);
int lengde = str.lengde();
for (int i = 1; i = 0 && str [j]> temp)
str [j + 1] = str [j];
j--;
str [j + 1] = temp;
cout<< "\nSorted string is: " << str << " \n";
retur 0;
Vi deler opp matrisen i sorterte og usorterte sublister i dette kodestykket. Verdiene i den usorterte komponenten blir deretter sammenlignet, og de blir sortert før de blir lagt til den sorterte sublisten. Den sorterte matriserens første medlem vil bli sett på som en sortert sublist. Vi sammenligner hvert element i den usorterte sublisten med hvert element i den sorterte sublisten. Deretter flyttes alle større komponenter til høyre.
Produksjon
3: Boble Sort
En annen enkel sorteringsteknikk er boble sort, som kontinuerlig bytter elementer i nærheten hvis de er i feil rekkefølge. Likevel må du først forstå hva boble -sortering er og hvordan den fungerer. Når følgende streng er mindre (a [i]> a [i+1]), blir nabostrengene (a [i] og a [i+1]) byttet i boble -sorteringsprosessen. Å sortere en streng ved hjelp av boble sort I C ++, følg disse trinnene:
Trinn 1: Be brukerinndata for en matrise.
Steg 2: Endre navnene på strengene ved å bruke 'Strcpy'.
Trinn 3: Et nestet for sløyfe brukes til å gå over og sammenligne to strenger.
Trinn 4: Verdiene byttes hvis ASCII-verdien til y er større enn y+1 (bokstavene, sifrene og tegnene som er tildelt 8-biters koder).
Trinn 5: Byttingen fortsetter til tilstanden kommer tilbake.
Byttingen fortsetter i trinn 5 til tilstanden kommer tilbake usant.
#inkludere#inkludere
ved hjelp av navneområdet STD;
int main ()
char str [10] [15], arr [10];
int x, y;
cout<< "Enter Strings: ";
for (x = 0; x> str [x];
for (x = 1; x < 6; x++)
for (y = 1; y 0)
strcpy (arr, str [y - 1]);
strcpy (str [y - 1], str [y]);
strcpy (str [y], arr);
cout<< "\nAlphabetical order of Strings :\n";
for (x = 0; x < 6; x++)
cout<< Str[x] <
Ovennevnte Boble sort Programmet vi bruker en karaktermatrise som kan holde 6 Karakterstrenger som brukerinngang. De “Strcpy” Funksjon har blitt brukt der navnene på strengene byttes i en nestet funksjon. I IF -uttalelsen blir to strenger sammenlignet med “STRCMP” funksjon. Og når alle strengene er sammenlignet, skrives utgangen på skjermen.
Produksjon
4: Rask sort
Divide and Conquer -metoden brukes av Rask sorter rekursiv algoritme for å ordne varene i en viss rekkefølge. Metoden bruker tilnærmingen for å dele den samme listen i to ved hjelp av pivotverdien, som antas å være det første medlemmet ideelt sett, i stedet for å bruke ekstra lagring for sublistene. Ethvert element kan velges, men. Etter samtaler til rask sorter, Listen er delt ved hjelp av partisjonspunktet.
Trinn 1: Først, skriv inn en streng.
Steg 2: Forklar pivotvariabelen og tilordne den til strengens midterste karakter.
Trinn 3: Etablere de nedre og høyere grensene for strengen som henholdsvis de to variablene lave og høye.
Trinn 4: Begynn å dele opp listen i to grupper, den ene med tegn som er større enn pivotelementet og den andre med mindre tegn, ved å bruke en stundsløyfe og elementbytte.
Trinn 5: Kjør rekursivt algoritmen på den originale strengens to halvdeler for å lage den sorterte strengen.
#inkludere#inkludere
#inkludere
ved hjelp av navneområdet STD;
void Quicksort (std :: String & str, int s, int e)
int st = s, slutt = e;
int pivot = str [(st + end) / 2];
Gjør
mens (str [st] pivot)
slutt--;
if (st<= end)
Std :: Swap (Str [ST], Str [End]);
St ++;
slutt--;
mens (ST<= end);
hvis (s < end)
Quicksort (Str, S, End);
if (st< e)
Quicksort (Str, St, E);
int main ()
STD :: String Str;
coutstr;
Quicksort (Str, 0, (int) Str.størrelse () - 1);
cout<< "The sorted string: " <
I denne koden erklærer vi start- og sluttposisjonene til to variabler under 'start' og 'slutt' som vil bli erklært i forhold til karakterstrengen. Matrisen vil bli delt i to i Quicksort () Funksjon, deretter ved å bruke en do-mens-loop, vil elementene bli byttet, og prosedyren vil bli gjentatt til strengen er sortert. De Quicksort () Funksjon vil da bli kalt fra hoved() Funksjon og strengen som er lagt inn av brukeren vil bli sortert, og utgangen vil bli skrevet ut på skjermen.
Produksjon
5: C ++ bibliotekfunksjon
De sortere() Funksjonen er tilgjengelig i C ++ takket være den innebygde bibliotekfunksjonsalgoritmen. Vi lager en rekke navnestrenger og bruker innebygd sortere() Metode, som vil sortere strengene ved å bruke matrisens navn og størrelse som argumenter. Syntaks for denne funksjonen er:
Sorter (First Iterator, Last Iterator)Der strengens begynnelses- og sluttindekser er henholdsvis den første og siste iteratoren.
Sammenlignende sett er bruk av denne innebygde funksjonen raskere og enklere å fullføre enn å utvikle din egen kode. Bare ikke-avstandsstrenger kan sorteres ved hjelp av sortere() metode da den også bruker hurtig sorteringsalgoritmen for å gjøre det.
#inkludere#inkludere
ved hjelp av navneområdet STD;
int main ()
streng str;
coutstr;
Sorter (str.Begynn (), Str.slutt());
cout<< "The sorted string is: " <
I denne koden vil vi først legge inn en streng av brukeren, og deretter blir strengen sortert ved hjelp av sortere() metode og deretter trykt på skjermen.
Produksjon
Konklusjon
Når Sortering En tegn i en C ++ -streng, programmereren må vurdere typen slags algoritme som passer for oppgaven, samt størrelsen på strengen. Avhengig av størrelsen på strengen, kan innsetting, boble, seleksjonssort, hurtig sort eller sort () -funksjon brukes til å sortere tegn. Det avhenger av brukerens valg, hvilken metode de vil velge.