version sort - feedback



  • Hallo,

    ich moechte folgendes beispiel implementieren und brauechte mal ein kurzes feedback zu meinem code. das ist jetzt keine production ready code. es geht nur um wie ich den algo implementieren kann...

    /*
    How would you sort the list of version numbers. For eg: You are given a list A as
    ["1.1","1.15","12.0","1.23","12.3"]. Now sort this ?
    */

    #include <iostream>
    #include <string>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    using namespace std;
    
    void append_zero(std::string &version, int len) {
    	for (int i = 0; i < len; i++) {
    		version.push_back('0');
    	}
    }
    
    std::string get_string_front_comma(std::string &str) {
    	auto comma_pos = str.find('.');
    	return str.substr(0, comma_pos);
    }
    
    std::string get_string_after_comma(std::string &str) {
    	auto comma_pos = str.find('.');
    	return str.substr(comma_pos, str.size() - comma_pos);
    }
    
    int string_to_int(std::string &str) {
    	int value = 0;
    	std::stringstream ss;
    	ss << str;
    	ss >> value;
    	return value;
    }
    
    void add_zero_padding(std::string &str) {
    	auto pos_comma = str.find(".");
    	if (pos_comma == std::string::npos) {
    		throw "invalid version number";
    	}
    	int precission = str.size() - pos_comma - 1;
    	if (precission < 2) {
    		append_zero(str, precission);
    	}
    }
    
    struct compare {
    	bool operator()(std::string lhs, std::string rhs) {
    		add_zero_padding(lhs);
    		add_zero_padding(rhs);
    
    		// compare front comma
    		std::string s1 = get_string_front_comma(lhs);
    		std::string s2 = get_string_front_comma(rhs);
    		int l = string_to_int(s1);
    		int r = string_to_int(s2);
    		if (l != r) {
    			return l < r;
    		}
    
    		// compare after comma
    		s1 = get_string_after_comma(lhs);
    		s2 = get_string_after_comma(rhs);
    		l = string_to_int(s1);
    		r = string_to_int(s2);
    		return l < r;
    	}
    };
    
    void version_sort(std::vector<string> &vec) {
    	std::sort(vec.begin(), vec.end(), compare());
    }
    
    int main() {
    	// your code goes here
    
    	std::vector<string> versions = {"1.1","1.15","12.0","1.23","12.3"};
    	version_sort(versions);
    
    	for (auto e : versions) {
    		std::cout << e << endl;	
    	}
    
    	return 0;
    }
    

  • Mod

    Und wenn irgendwann mal eine Versionsnummer 1.234 kommt, funktioniert es nicht mehr? Ich würde den Teil vor dem Punkt numerisch vergleichen und die Zeichenkette nach dem Komma lexikographisch.

    "precision" schreibt man übrigens nicht so, wie du denkst. Und das Wort für Dezimaltrennzeichen ist "decimal" oder "decimal mark", weil es eben für die meisten Menschen auf der Welt kein "comma" ist. "front" ist das "Vorderteil", nicht "vor", welches "before" wäre.



  • Hi SeppJ,

    warum soll es mit "1.234" nicht funktionieren?

    wie kann ich die zeichen nach dem dezimalzeichen lexikographisch vergleichen?

    LG



  • coderatte schrieb:

    warum soll es mit "1.234" nicht funktionieren

    Weil dein Padding am Ende nur bis 2 Nachkommastellen auffüllt. Das heißt bei 1.234 vergleichst du 234 mit den nur zwei Nachkommastellen der anderen Versionsnummern. Statt den Teil hinter dem Komma als int zu vergleichen müsste der direkte Vergleich der strings funktionieren (ungetestet). Das ist dann wie die Sortierung im Wörterbuch. Also der Nachkommateil "23" kommt vor "234".



  • @sebi707: meinst du so?

    #include <iostream>
    #include <string>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    using namespace std;
    
    int max_precision = 0;
    
    void append_zero(std::string &version, int len) {
    	for (int i = 0; i < len; i++) {
    		version.push_back('0');
    	}
    }
    
    std::string get_string_front_comma(std::string &str) {
    	auto comma_pos = str.find('.');
    	return str.substr(0, comma_pos);
    }
    
    std::string get_string_after_comma(std::string &str) {
    	auto comma_pos = str.find('.');
    	return str.substr(comma_pos, str.size() - comma_pos);
    }
    
    int string_to_int(std::string &str) {
    	int value = 0;
    	std::stringstream ss;
    	ss << str;
    	ss >> value;
    	return value;
    }
    
    void add_zero_padding(std::string &str) {
    	auto pos_comma = str.find(".");
    	if (pos_comma == std::string::npos) {
    		throw "invalid version number";
    	}
    	int precision = str.size() - pos_comma - 1;
    	if (precision < max_precision) {
    		append_zero(str, max_precision - precision);
    	}
    }
    
    void get_max_precision(std::vector<std::string> &vec) {
    	for (int i = 0; i < vec.size(); i++) {
    		auto pos_comma = vec[i].find(".");
    		if (pos_comma == std::string::npos) {
    			throw "invalid version number";
    		}
    		int precision = vec[i].size() - pos_comma - 1;
    		if (precision > max_precision) {
    			max_precision = precision;
    		}
    	}
    }
    
    struct compare {
    	bool operator()(std::string lhs, std::string rhs) {
    		add_zero_padding(lhs);
    		add_zero_padding(rhs);
    
    		// compare front comma, nummerical compare
    		std::string s1 = get_string_front_comma(lhs);
    		std::string s2 = get_string_front_comma(rhs);
    		int l = string_to_int(s1);
    		int r = string_to_int(s2);
    		if (l != r) {
    			return l < r;
    		}
    
    		// compare after comma, lexicographical compare
    		return lhs < rhs;
    	}
    };
    
    void version_sort(std::vector<string> &vec) {
    	get_max_precision(vec);
    	std::sort(vec.begin(), vec.end(), compare());
    }
    
    int main() {
    	// your code goes here
    
    	try {
    		std::vector<string> versions = {"1.2a", "1.1","1.15","12.0","1.23","12.3", "1.234"};
    		version_sort(versions);
    
    		for (auto e : versions) {
    			std::cout << e << endl;	
    		}
    	} catch(const char *e) {
    		std::cout << e << std::endl;
    	}
    
    	return 0;
    }
    


  • Ja so ginge es. Und die Geschichte mit get_max_precision und dem Padding wird ja dann unnötig.



  • Grauenhafter Code, daher werde ich den nicht weiter kommentieren. Wenn ich schon sehe, dass eine Stringkonstante geworfen wird 😞 .

    Aber zu Versionsnummern habe ich einen Hinweis: Üblicherweise ist die Versionsnummer keine Fliesskommazahl sondern eine Folge von dezimalen Ganzzahlen. Also nach "1.9" kommt "1.10". Und manchmal gibt es noch eine weitere Stelle wie beispielsweise "1.9.1", welches am ehesten so zwischen "1.9" und "1.10" einsortiert weder sollten. Wobei das schon nicht ganz eindeutig ist.

    Siehe auch Linux-Versionsnummern



  • @tntnet: das ist kein production ready code!!


Log in to reply