Ordenar una array de números de versión

Dada una array de strings arr[] , que consta de N strings, cada una de las cuales representa números separados por puntos en forma de versiones de software.

Entrada: arr[] = {“1.1.2”, “0.9.1”, “1.1.0”}
Salida: “0.9.1” “1.1.0” “1.1.2”

Entrada: arr[] = {“1.2”, “0.8.1”, “1.0”}
Salida: “0.8.1” “1.0” “1.2”

Enfoque: siga los pasos a continuación para resolver el problema:

• Cree una función para comparar dos strings.
• Almacene strings en un vector .
• Para comparar dos strings S1 y S2 separadas por puntos , itere hasta la longitud min(S1, S2) + 1 y compare cada parte numérica de la string y ordene según corresponda.
• Repita los pasos anteriores para cada par de cuerdas y ordene la array en consecuencia.

A continuación se muestra la implementación de la idea anterior:

C++

// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std;    // Compares two strings int check(const string& a, const string& b) {        int al = a.length();     int bl = b.length();        int i = 0, j = 0;     while (i < al && j < bl) {         if (a[i] == b[j]) {             ++i;             ++j;         }         else if (a[i] > b[j]) {             return 1;         }         else             return -1;     }        if (i == al && j == bl)         return 0;     if (i == al)         return -1;     return 1; }    // Function to split strings based on dots vector<string> getTokens(const string& a) {     vector<string> v;     string s;        // Stringstream is used here for     // tokenising the string based     // on "." delimiter which might     // contain unequal number of "."[dots]     stringstream ss(a);     while (getline(ss, s, '.')) {         v.push_back(s);     }     return v; }    // Comparator to sort the array of strings bool comp(const string& a, const string& b) {        // Stores the numerical substrings     vector<string> va, vb;     va = getTokens(a);     vb = getTokens(b);        // Iterate up to length of minimum     // of the two strings     for (int i = 0; i < min(va.size(), vb.size());          i++) {            // Compare each numerical substring         // of the two strings         int countCheck = check(va[i], vb[i]);            if (countCheck == -1)             return true;            else if (countCheck == 1)             return false;     }        if (va.size() < vb.size())         return true;        return false; }    // Driver Code int main() {        vector<string> s;     s.push_back("1.1.0");     s.push_back("1.2.1");     s.push_back("0.9.1");     s.push_back("1.3.4");     s.push_back("1.1.2");     s.push_back("1.1.2.2.3");     s.push_back("9.3");        // Sort the strings using comparator     sort(s.begin(), s.end(), comp);        // Display the sorted order     for (int i = 0; i < s.size(); i++) {         cout << s[i] << endl;     }     cout << endl;     return 0; }

Producción:

0.9.1
1.1.0
1.1.2
1.1.2.2.3
1.2.1
1.3.4
9.3

Complejidad de tiempo: O(N*L*logN), donde N es el número total de strings de versión, L es la longitud máxima entre esas strings.
Espacio Auxiliar: O(N * L)