|

Algoritmi de Sortare – Sortarea prin Metoda Bulelor 13


1. Obiectivele lecției:

  • Să înțeleagă principiul metodei de sortare prin bule (Bubble Sort).
  • Să implementeze metoda în limbajul C++.
  • Să analizeze eficiența algoritmului (complexitatea în timp).
  • Să aplice metoda pentru rezolvarea unor probleme practice.

2. Conținutul lecției:

Ce este sortarea prin metoda bulelor?

  • Definiție: Sortarea prin metoda bulelor este un algoritm de sortare simplu care compară perechi de elemente adiacente și le interschimbă dacă sunt în ordine greșită, repetând procesul până când lista este sortată.
  • Principiu: La fiecare pas, cel mai mare element „urcă” spre poziția sa finală, ca o bulă care se ridică la suprafață.

Pasii metodei:

  1. Compară fiecare pereche de elemente adiacente din listă.
  2. Dacă ele sunt în ordine greșită, interschimbă-le.
  3. Repetă procesul pentru toate elementele, reducând numărul de elemente analizate cu 1 la fiecare iterație (ultimele elemente devin sortate).
  4. Termină când nu mai există schimbări în timpul unei iterații.

Pseudocod:

Intrare: Lista de n elemente

Pentru i de la 0 la n-1:

    Pentru j de la 0 la n-i-2:

        Dacă lista[j] > lista[j+1], atunci

            Interschimbă lista[j] cu lista[j+1]

Ieșire: Lista sortată


3. Cod în C++:

#include <iostream>

using namespace std;

int main() {

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr) / sizeof(arr[0]);

    // Afișarea array-ului inițial

    cout << „Array initial: „;

    for (int i = 0; i < n; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

    // Implementarea algoritmului Bubble Sort

    for (int i = 0; i < n – 1; i++) {

        for (int j = 0; j < n – i – 1; j++) {

            if (arr[j] > arr[j + 1]) {

                // Interschimbare

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

    // Afișarea array-ului sortat

    cout << „Array sortat: „;

    for (int i = 0; i < n; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

    return 0;

}


Exemplu 2: Sortare descrescătoare

#include <iostream>

using namespace std;

int main() {

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr) / sizeof(arr[0]);

    // Afișarea array-ului inițial

    cout << „Array initial: „;

    for (int i = 0; i < n; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

    // Implementarea algoritmului Bubble Sort pentru ordine descrescătoare

    for (int i = 0; i < n – 1; i++) {

        for (int j = 0; j < n – i – 1; j++) {

            if (arr[j] < arr[j + 1]) {

                // Interschimbare

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

    // Afișarea array-ului sortat descrescător

    cout << „Array sortat descrescator: „;

    for (int i = 0; i < n; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

    return 0;

}


4. Complexitatea algoritmului:

  1. Cazul cel mai defavorabil (O(n²)):
    • Lista este ordonată invers față de cea dorită.
    • Fiecare pereche trebuie interschimbată.
  2. Cazul cel mai favorabil (O(n)):
    • Lista este deja sortată.
    • Algoritmul detectează această situație dacă este optimizat.
  3. Cazul mediu (O(n²)):
    • Lista are o ordine aleatorie.

Optimizare:

Pentru a îmbunătăți algoritmul, se poate introduce o variabilă care detectează dacă au fost efectuate schimbări într-o iterație. Dacă nu există schimbări, algoritmul se oprește.

Cod optimizat:

void bubbleSortOptimized(int arr[], int n) {

    bool swapped;

    for (int i = 0; i < n – 1; i++) {

        swapped = false;

        for (int j = 0; j < n – i – 1; j++) {

            if (arr[j] > arr[j + 1]) {

                // Interschimbare

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

                swapped = true;

            }

        }

        // Dacă nu s-au făcut schimbări, lista este deja sortată

        if (!swapped) break;

    }

}


5. Activități practice pentru elevi:

  1. Scrieți un program care sortează un array de numere reale utilizând metoda bulelor.
  2. Realizați un program care sortează un șir de caractere folosind aceeași metodă.
  3. Modificați algoritmul pentru a sorta array-ul astfel încât să fie sortat crescător pentru elementele pare și descrescător pentru cele impare.

6. Scheme logice:

  1. Schema generală Bubble Sort:
    • Start -> Pentru fiecare element i -> Pentru fiecare element j -> Compară și interschimbă arr[j]>arr[j+1] -> Terminare -> Stop.
  2. Schema optimizată:
    • Start -> Inițializează swapped = false -> Compară și interschimbă -> Dacă swapped == false -> Terminare -> Stop.

7. Concluzie:

  • Sortarea prin metoda bulelor este un algoritm simplu de înțeles, dar mai puțin eficient pentru liste mari.
  • Este potrivit pentru situații în care numărul de elemente este mic sau când simplitatea implementării este mai importantă decât eficiența.
  • Elevii vor înțelege mai bine conceptele de comparare, interschimbare și iterație.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *