Metode de sortare: metoda bulelor și selecția – Algoritmi rezolvați în C++

Introducere

Sortarea este un proces esențial în programare, care implică aranjarea elementelor unei liste într-o ordine specifică. Există mai multe metode de sortare disponibile, fiecare cu propriile sale avantaje și dezavantaje. În acest articol, vom explora două metode de sortare comune: metoda bulelor și selecția. Vom prezenta, de asemenea, exemple de algoritmi rezolvați în limbajul de programare C++.

Metoda bulelor

Metoda bulelor este una dintre cele mai simple metode de sortare și este ușor de înțeles și de implementat. Algoritmul funcționează prin parcurgerea listei multiple ori, comparând elementele adiacente și interschimbându-le dacă nu sunt în ordine. Acest proces se repetă până când lista este sortată complet.

Pentru a exemplifica acest algoritm, să presupunem că avem următoarea listă de numere întregi:

int lista[] = {5, 2, 8, 1, 9};

Pasul inițial al metodei bulelor implică parcurgerea întregii liste și compararea elementelor adiacente. Dacă un element este mai mare decât elementul următor, acestea sunt interschimbate. În exemplul nostru, primul pas ar arăta astfel:

int lista[] = {2, 5, 8, 1, 9};

Procesul se repetă apoi pentru restul listei, rezultând într-o listă sortată:

int lista[] = {1, 2, 5, 8, 9};

Implementarea algoritmului metodei bulelor în C++ ar putea arăta astfel:

void metodaBulelor(int lista[], int lungime) {
for (int i = 0; i < lungime - 1; i++) {
for (int j = 0; j < lungime - i - 1; j++) {
if (lista[j] > lista[j + 1]) {
// interschimbare elemente
int temp = lista[j];
lista[j] = lista[j + 1];
lista[j + 1] = temp;
}
}
}
}

 

void sortarePrinBule(int lista[], int lungime) {
bool sorted;
do {
sorted = true;
for (int i = 0; i < lungime - 1; i++) {
if (lista[i] > lista[i + 1]) {
// interschimbare elemente
int aux = lista[i];
lista[i] = lista[i + 1];
lista[i + 1] = aux;
sorted = false;
}
}
} while (!sorted);
}

Metoda selecției

Metoda selecției este o altă metodă de sortare simplă și eficientă. Algoritmul funcționează prin găsirea celui mai mic element din listă și plasarea lui pe poziția corectă. Acest proces se repetă pentru fiecare element din listă, rezultând într-o listă sortată complet.

Pentru a exemplifica acest algoritm, să presupunem că avem aceeași listă de numere întregi ca în exemplul anterior:

int lista[] = {5, 2, 8, 1, 9};

Pasul inițial al metodei selecției implică găsirea celui mai mic element din listă și plasarea lui pe prima poziție. În exemplul nostru, primul pas ar arăta astfel:

int lista[] = {1, 2, 8, 5, 9};

Procesul se repetă apoi pentru restul listei, rezultând într-o listă sortată:

int lista[] = {1, 2, 5, 8, 9};

Implementarea algoritmului metodei selecției în C++ ar putea arăta astfel:

void metodaSelectiei(int lista[], int lungime) {
    for (int i = 0; i < lungime - 1; i++) {
        int minim = i;
        for (int j = i + 1; j < lungime; j++) {
            if (lista[j] < lista[minim]) {
                minim = j;
            }
        }
        // interschimbare elemente
        int temp = lista[minim];
        lista[minim] = lista[i];
        lista[i] = temp;
    }
}

Concluzie

Metodele de sortare, cum ar fi metoda bulelor și selecția, sunt esențiale în dezvoltarea programelor eficiente. Am prezentat algoritmi rezolvați pentru aceste metode în limbajul de programare C++. Este important să înțelegem avantajele și dezavantajele fiecărei metode de sortare și să le utilizăm în mod corespunzător în funcție de necesitățile noastre.

Este recomandat să explorăm și alte metode de sortare, precum sortarea prin inserție sau sortarea rapidă, pentru a avea o perspectivă mai largă asupra algoritmilor de sortare disponibili.