[C++] STL Sort algorithm

[MAMRETRAS]

Am vazut de multe ori scrise in 5~10 randuri sortari ineficiente. Cu un singur rand, se pot sorta elementele unui array foarte simplu si eficient, cu ajutorul functiei sort din biblioteca algorithm.

 

Functia sort primeste ca parametrii: adresa de memorie de la care sa inceapa sortarea, adresa de memorie unde sa se opreasca cu sortarea si optional un functor care sa decida criteriul de sortare.

 

Exemplu sortare in ordine crescatoare a elementelor de la jumatatea vectorului spre sfarsit:

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

int main() {
    std::vector<int> input = { 2, 5, 7, 6, 3, 4, 15, 11, 12, 18, 14, 27 , 5, 3, 12, 4 };

    std::sort(input.begin() + input.size() / 2, input.end());
    
    for (const auto& entry : input) {
        std::cout << entry << " ";
    }
    
    return 0;
}

// out: 2 5 7 6 3 4 15 11 3 4 5 12 12 14 18 27  

 

Exemplu sortare in ordine crescatoare a tuturor elementelor cu restricita ca elementele pare sa apara in stanga elementelor impare:

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

int main() {
    std::vector<int> input = { 2, 5, 7, 6, 3, 4, 15, 11, 12, 18, 14, 27 , 5, 3, 12, 4 };
    
    auto ascending_even_left_odd_right = [](int a, int b) {
        if (a % 2 == 0 && b % 2 == 1)
            return 1;
        if (a % 2 == 1 && b % 2 == 0)
            return 0;
        if (a < b)
            return 1;
        return 0;
    };
    
    std::sort(input.begin(), input.end(), ascending_even_left_odd_right);
    
    for (const auto& entry : input) {
        std::cout << entry << " ";
    }
    
    return 0;
}
                              
// out: 2 4 4 6 12 12 14 18 3 3 5 5 7 11 15 27

Pentru aprofundare, abordeaza urmatoarele probleme:

• EASY: sorteaza in ordine descrescatoare toate elementele
• MEDIUM: sorteaza in ordine crescatoare prima jumatate si in ordine descrescatoarea a 2-a jumatate
• HARD: sorteaza in zig-zag, primele 4 elemente crescator, urmatoarele 4 descrescator, urmatoarele 4 crescator si tot asa

 

Pentru inrebari, va astept cu un reply sau cu un PM in cazul in care topicul este inchis. Bafta!

[Andreigl]

@Vesca, poți să faci exemple și cu Array? Dar nu folosind std, sau, și și

[MAMRETRAS]

@shanker' Am lasat comentariu "// <- HERE" bucatilor de cod care sorteaza array-ul (nu stiu de ce nu iti place std::vector). Restul codului e neimportant pentru problema vizata in acest tutorial.

#include <algorithm>
#include <iostream>

const int max_array_size = 100;

void afisare_array(int arr[], int size) {
    for (int npos = 0; npos < size; ++npos) {
        std::cout << arr[npos] << " ";
    }
    std::cout << "\n";
}

void afisare_crescatoare(int arr[], int size) {
    std::sort(arr, arr + size); // <- HERE
    afisare_array(arr, size);
}

void afisare_crescatoare_prima_jumatate(int arr[], int size) {
    std::sort(arr, arr + size / 2); // <- HERE
    afisare_array(arr, size);
}

bool criteriu_descrescator(int a, int b) {
    return a > b;
}
void afisare_descrescatoare(int arr[], int size) {
    std::sort(arr, arr + size, criteriu_descrescator); // <- HERE
    afisare_array(arr, size);
}

int* deep_copy_array(int arr[max_array_size], int size) {
    int* new_arr = new int[max_array_size];
    std::copy(arr, arr + size, new_arr);
    return new_arr;
}

int main() {
    int array[max_array_size];
    int N;
    
    std::cout << "Introdu numarul de elemente: "; std::cin >> N;
    std::cout << "Introdu elementele: ";
    for (int npos = 0; npos < N; ++npos) {
        std::cin >> array[npos];
    }
    
    std::cout << "Sortare crescatoare: \n";
    afisare_crescatoare(deep_copy_array(array, N), N);
    
    std::cout << "Sortare descrescatoare: \n";
    afisare_descrescatoare(deep_copy_array(array, N), N);
    
    std::cout << "Sortare crescatoare prima jumatate: \n";
    afisare_crescatoare_prima_jumatate(deep_copy_array(array, N), N);
    
    return 0;
}

Ce te intereseaza:

void afisare_crescatoare(int arr[], int size) {
    std::sort(arr, arr + size);
    afisare_array(arr, size);
}

void afisare_crescatoare_prima_jumatate(int arr[], int size) {
    std::sort(arr, arr + size / 2);
    afisare_array(arr, size);
}

bool criteriu_descrescator(int a, int b) {
    return a > b;
}
void afisare_descrescatoare(int arr[], int size) {
    std::sort(arr, arr + size, criteriu_descrescator);
    afisare_array(arr, size);
}

Console:

Introdu numarul de elemente: 8
Introdu elementele: 7 8 6 3 5 4 1 2
Sortare crescatoare: 
1 2 3 4 5 6 7 8 
Sortare descrescatoare: 
8 7 6 5 4 3 2 1 
Sortare crescatoare prima jumatate: 
3 6 7 8 5 4 1 2 

 

Edited January 29, 2020 by Vesca

[Andreigl]

Nu mai fă prescurtări, în loc de

bool criteriu_descrescator(int a, int b) {
    return a > b;
}

puteai pune:

bool criteriu_descrescator(int a, int b) {
    if (a > b)
        return 1;
    else
        return 0;
}

 

E mai clar ce face funcția asa, zic eu  

Motivul pentru care eu nu folosesc vectorii este că atunci când ai nevoie de un vector bidimensional, lucrurile se complică ... deci rămân la array ?

 

Ia, populează-mi o matrice cu vectori, după faci suma elementelor pe diagonală, de la primul pănâ la ultimul element, ca și în poza de mai jos:

 

 

 

 

Edited January 29, 2020 by shanker'

[MAMRETRAS]

11 hours ago, shanker' said:

Nu mai fă prescurtări, în loc de

bool criteriu_descrescator(int a, int b) {
    return a > b;
}

puteai pune:

bool criteriu_descrescator(int a, int b) {
    if (a > b)
        return 1;
    else
        return 0;
}

 

N-are rost sa faci asta'.

Ochiul uman consuma mult mai ușor o linie de cod in loc de 4. Totodată, este redundant (sau mai pe românește, pleonasm).

Ce faci tu este același lucru cu a pune paranteze redundante, cum ar fi:

int a = (2 * 3) + 4;

Ce rost au parantezele aici? Nu au. Si cu si fara paranteze tot inmultirea se face prima data.

Alt exemplu ar fi cu pleonasmul, gen Hagi:

daca e adevarat atunci
    e adevarat
altfel
    nu e adevarat

Ceea ce e redundant, mai bine spui direct:

e adevarat / nu e adevarat

Ai aici și aici doua articole despre acest aspect.

Ca lectura suplimentara iți sugerez si acest articol unde se vorbeste despre branch prediction. Long story short, pentru computer e mai ok sa nu folosesti if decat sa folosesti.

 

11 hours ago, shanker' said:

Motivul pentru care eu nu folosesc vectorii este că atunci când ai nevoie de un vector bidimensional, lucrurile se complică ... deci rămân la array ?

 

Ia, populează-mi o matrice cu vectori, după faci suma elementelor pe diagonală, de la primul pănâ la ultimul element, ca și în poza de mai jos:

Nu se complica asa tare, doar daca nu ai lucrat destul cu vectori poate sa ti se para complicat. Oricum, problema nu vizeaza acest tutorial, deci o sa fac un alt tutorial unde voi explica cum sa folosesti vector pentru matrice, folosind problema ta ca exemplificare.

Edited January 30, 2020 by Vesca

[Andreigl]

@Vesca , eu ți-am zis cum mi se pare mie mai „logic”, totuși varianta ta ar fi bună pentru un apel lambda  

 

std::sort(array, array + size, [](int a, int b)
	{ return a > b; }
);

 

Am adăugat acest topic în algoritmi elementari.

[MAMRETRAS]

6 minutes ago, shanker' said:

@Vesca , eu ți-am zis cum mi se pare mie mai „logic”, totuși varianta ta ar fi bună pentru un apel lambda  

 

std::sort(array, array + size, [](int a, int b)
	{ return a > b; }
);

 

Am adăugat acest topic în algoritmi elementari.

Evident că se poate pune și lambda. Nu l'am pus așa pentru a arata și cum e cu funcție. Lambda am pus mai sus.

Edited January 30, 2020 by Vesca

[Jackson Brooklyn]

Topic inactiv de mai mult de 3 zile.