Clasa a X-a · Șiruri de caractereRead in English
Sortarea alfabetică a cuvintelor în C++
În engleză: Sorting words alphabetically
Ideea
Separăm fraza în cuvinte cu strtok și le copiem într-o matrice de caractere cuv[100][31] (fiecare linie este un șir). Sortăm cu metoda bulelor; două cuvinte se compară cu strcmp(x, y), care întoarce o valoare pozitivă dacă x este după y în ordinea din tabelul ASCII. Interschimbarea se face prin trei apeluri strcpy, cu un șir auxiliar. Cuvintele sunt scrise cu litere mici (literele mari ar fi puse înaintea tuturor celor mici).
Descrierea în engleză
We split the sentence into words with strtok and copy them into a character matrix cuv[100][31] (every row is a string). We sort with bubble sort; two words are compared with strcmp(x, y), which returns a positive value if x comes after y in ASCII order. Swapping is done with three strcpy calls and a helper string. The words are lowercase (uppercase letters would be placed before all lowercase ones).
- Complexitate
- O(k * k * L), k cuvinte de lungime cel mult L
- Clasa
- Clasa a X-a (Grade 10)
- Capitol
- Șiruri de caractere
Exemple
Intrare
pere mere ana banane caise
Ieșire așteptată
ana banane caise mere pere
Intrare
mare mar marar ma
Ieșire așteptată
ma mar marar mare
Codul C++
Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.
/*
* Titlu: Sortarea alfabetică a cuvintelor
* Clasa: 10
* Capitol: Șiruri de caractere
* Descriere: Separăm fraza în cuvinte cu strtok și le copiem într-o matrice de
* caractere cuv[100][31] (fiecare linie este un șir). Sortăm cu metoda
* bulelor; două cuvinte se compară cu strcmp(x, y), care întoarce o valoare
* pozitivă dacă x este după y în ordinea din tabelul ASCII. Interschimbarea
* se face prin trei apeluri strcpy, cu un șir auxiliar. Cuvintele sunt
* scrise cu litere mici (literele mari ar fi puse înaintea tuturor celor mici).
* Complexitate: O(k * k * L), k cuvinte de lungime cel mult L
*
* Exemplu
* Intrare: pere mere ana banane caise
* Ieșire: ana banane caise mere pere
*
* Exemplu
* Intrare: mare mar marar ma
* Ieșire: ma mar marar mare
*/
#include <iostream>
#include <cstring>
using namespace std;
char cuv[100][31];
int main()
{
char s[256];
cin.getline(s, 256);
int k = 0;
char *p = strtok(s, " ");
while (p != NULL)
{
strcpy(cuv[k++], p);
p = strtok(NULL, " ");
}
bool schimbat = true;
while (schimbat)
{
schimbat = false;
for (int i = 0; i + 1 < k; i++)
{
if (strcmp(cuv[i], cuv[i + 1]) > 0)
{
char aux[31];
strcpy(aux, cuv[i]);
strcpy(cuv[i], cuv[i + 1]);
strcpy(cuv[i + 1], aux);
schimbat = true;
}
}
}
for (int i = 0; i < k; i++)
cout << cuv[i] << ' ';
cout << '\n';
return 0;
}
Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.