Grade 10 · Character stringsCitește în română

Sorting words alphabetically

Original: Sortarea alfabetică a cuvintelor

O(n²)C++1761 lines2 examples

The idea

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).

Original description (Romanian)

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).

Complexity
O(k * k * L), k words of length at most L
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

pere mere ana banane caise

Expected output

ana banane caise mere pere
Example 2

Input

mare mar marar ma

Expected output

ma mar marar mare

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sortarea-alfabetica-a-cuvintelor.cpp
/*
 * 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;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.