Cum sortez un vector în C++ fără sort()?

Cu o metodă elementară: prin selecție (aduci minimul în față), prin interschimbarea vecinilor (metoda bulelor) sau prin inserție. Toate fac în jur de n² pași.

sort din <algorithm> nu este în programă, deci sortezi cu una dintre metodele elementare. Cea mai simplă de scris este metoda bulelor: compari vecinii și îi interschimbi dacă sunt în ordine greșită, până când o parcurgere întreagă nu mai schimbă nimic:

bool schimbat;
do {
    schimbat = false;
    for (int i = 1; i < n; i++)
        if (v[i] > v[i+1]) {
            int aux = v[i]; v[i] = v[i+1]; v[i+1] = aux;
            schimbat = true;
        }
} while (schimbat);

Selecția caută cel mai mic element din ce a rămas și îl aduce pe prima poziție liberă. Face puține interschimbări. Inserția pune fiecare element la locul lui între cele deja sortate. E foarte rapidă pe un vector aproape sortat.

Toate trei fac în jur de n² pași. Pentru n de ordinul miilor e instantaneu, pentru sute de mii e prea mult. Dacă valorile sunt întregi, nenegative și mărginite, sortarea prin numărare cu un vector de frecvențe e liniară.

Pentru descrescător, inversezi semnul comparației. Lecția despre sortare le compară pe toate.

Lecția care merge mai departe: Metode elementare de sortare