STL - sort

Dal quinto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Algoritmi standard.

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.1: sort e stable_sort

L'algoritmo sort() ordina gli elementi compresi tra i due iteratori passati. Può essere utilizzato solo da container che hanno iteratori ad accesso casuale, come vector e deque.

Per l'ordinamento di list é dunque necessario usare la funzione membro list::sort().

L'algoritmo non é stabile, dunque se ci sono due o più elementi che dal punto di vista del comparatore sono uguali, non é detto che mantangano la posizione relativa iniziale. Nel caso peggiore le prestazioni di questo algoritmo possono degaradare, si può ricorrere a stable_sort() se questo può essere un problema. Sono resi disponibili due versioni di sort(), una usa l'operatore '<', l'altra permette di usare una funzione o un functor Compare.

Nell'esempio vediamo l'uso di sort e stable_sort nei due casi:

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>

using namespace std;

void dump(const vector<double>& v) {
    vector<double>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

bool integerLess(double x, double y) {
    return long(x) < long(y);
}

int main() {
    vector<double> v(20);

    srand(time(NULL));
    for (size_t i = 0; i < v.size(); ++i) {
        v[i] = (rand() % 3 + 1) + double((rand() % 100 + 1) / 1000.0);
    }
    random_shuffle(v.begin(), v.end());

    cout << "Original sequence" << endl;
    dump(v);

    vector<double> unstable = v;
    vector<double> stable = v;

    cout << endl << "Sorting using the standard operator less" << endl;

    // sorting with < operator:
    stable_sort(stable.begin(), stable.end());
    cout << "Stable sorting:" << endl;
    dump(stable);

    sort(unstable.begin(), unstable.end());
    cout << "Unstable sorting:" << endl;
    dump(unstable);

    cout << endl << "Sorting with custom comparator" << endl;

    unstable = v;
    stable = v;

    stable_sort(stable.begin(), stable.end(), integerLess);
    cout << "stable sorting (integer key):" << endl;
    dump(stable);

    sort(unstable.begin(), unstable.end(), integerLess);
    cout << "unstable sorting (integer key):\n";
    dump(unstable);
}

Inizializziamo l'array con valori decimali casuali in modo che in molti condividano la stessa parte intera.

Quando usiamo l'operatore '<' non c'é differenza nel risultato nell'uso di sort e stable_sort, ma usando la nostra funzione integerLess, che compara i valori interi, notiamo che solo la stable_sort permetta di mantenere la posizione relativa tra gli elementi dopo l'ordinamento.