C++ sorting classes faster than qsort

Question

I have a class

class Zaposlenik { 
private:
    string prezime; 
    string funkcija; 
    double placa; 
public:
    bool operator==(const string& prezime) const; 
    bool operator<(const string &prezime) const; 
    bool operator<(const Zaposlenik &other) const; 

I use operators with string for binary search and operator< with Zaposlenik for sorting

I can't change the header class I can only write code in .cpp.

I also have

class Firma { 
private: 
vector<Zaposlenik> zaposlenici; 
public: 
void sort();

I can't change that class either,I have to write .cpp for it. I upload the 2 .cpp to a auto grading server that inputs 500 000 Zaposlenik into vector zaposlenici and then preforms 2 000 000 searches.

I used qsort and bsearch and it was too slow. It can't be longer then 3s when I upload it.

I have written overloaded operators and I belive they are fine,but apparently qsort can be faster.

Vector is sorted by string prezime and names are from "aaaa" to "ZZZZ" so 4 letter combination of big and small letters.

string funkcija; and double placa; don't mean anything for sorting.

Can someone tell me which sort would be faster then qsort? Keep in mind that I don't have any control over main and I can't count members when they are made.

P.S. there are other functions in classes but they don't have any meaning for this part. There is also function for Bsearch but that is as fast as it gets I belive.

Answer 1

Three things:

• Use std::sort instead of std::qsort, it’s faster because it can inline calls to the comparison operator (if you define it in the header or enable link-time optimisations).

• Override swap for your class so that it can be swapped efficiently instead of copying via a temporary variable. However, that requires changing the header (because you need access to the private variables).

• Since your sorted strings are of fixed length 4, a different sorting algorithm will be beneficial. The classical choice, which is fairly easy to implement, is radix sort. Judging from some of your comments it seems likely that your professor wants you to implement this.