|

Algoritmi de Sortare – Sortarea prin Selecția Minimului 15


1. Obiectivele lecției:

  • Să înțeleagă principiul sortării prin selecția minimului (Selection Sort).
  • Să implementeze algoritmul în limbajul C++.
  • Să analizeze complexitatea algoritmului.
  • Să aplice metoda pentru rezolvarea unor probleme practice.

2. Conținutul lecției:

Ce este sortarea prin selecția minimului?

  • Definiție: Sortarea prin selecția minimului este un algoritm de sortare simplu care găsește cel mai mic element dintr-o listă nesortată și îl aduce la început, repetând procesul pentru restul listei.
  • Principiu: La fiecare pas, cel mai mic element din secțiunea nesortată a listei este plasat în poziția sa finală.

Cum funcționează?

  1. Găsește cel mai mic element din lista nesortată.
  2. Interschimbă-l cu primul element al listei nesortate.
  3. Repetă procesul pentru restul listei, reducând secțiunea nesortată cu un element la fiecare pas.

Pseudocod:

Intrare: Lista de n elemente

Pentru i de la 0 la n-1:

    minIndex = i

    Pentru j de la i+1 la n-1:

        Dacă lista[j] < lista[minIndex], atunci

            minIndex = j

    Interschimbă lista[i] cu lista[minIndex]

Ieșire: Lista sortată


3. Cod în C++:


Exemplu 1: Sortare crescătoare

#include <iostream>

using namespace std;

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

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

        int minIndex = i;

        // Găsește indexul minimului

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

            if (arr[j] < arr[minIndex]) {

                minIndex = j;

            }

        }

        // Interschimbare

        int temp = arr[i];

        arr[i] = arr[minIndex];

        arr[minIndex] = temp;

    }

}

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

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

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

    }

    cout << endl;

}

int main() {

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

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

    cout << „Array initial: „;

    printArray(arr, n);

    selectionSort(arr, n);

    cout << „Array sortat crescator: „;

    printArray(arr, n);

    return 0;

}


Exemplu 2: Sortare descrescătoare

#include <iostream>

using namespace std;

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

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

        int maxIndex = i;

        // Găsește indexul maximului

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

            if (arr[j] > arr[maxIndex]) {

                maxIndex = j;

            }

        }

        // Interschimbare

        int temp = arr[i];

        arr[i] = arr[maxIndex];

        arr[maxIndex] = temp;

    }

}

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

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

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

    }

    cout << endl;

}

int main() {

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

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

    cout << „Array initial: „;

    printArray(arr, n);

    selectionSortDescending(arr, n);

    cout << „Array sortat descrescator: „;

    printArray(arr, n);

    return 0;

}


4. Complexitatea algoritmului:

  1. Cazul cel mai defavorabil (O(n²)):
    • În fiecare iterație, algoritmul compară toate elementele nesortate pentru a găsi minimul.
  2. Cazul cel mai favorabil (O(n²)):
    • Lista este deja sortată, dar algoritmul continuă să compare toate elementele.
  3. Cazul mediu (O(n²)):
    • Lista are o ordine aleatorie.

Avantaje:

  • Simplu de implementat și de înțeles.
  • Nu necesită memorie suplimentară (sortare in-place).

Dezavantaje:

  • Ineficient pentru liste mari din cauza numărului mare de comparații.
  • Nu este un algoritm de sortare stabil (nu păstrează ordinea relativă a elementelor egale).

5. Activități practice pentru elevi:

  1. Scrieți un program care sortează un array de numere reale utilizând sortarea prin selecția minimului.
  2. Realizați un program care sortează un șir de caractere în ordine alfabetică folosind selecția minimului.
  3. Modificați algoritmul pentru a sorta un array astfel încât elementele pare să fie sortate crescător și cele impare descrescător.

6. Scheme logice:

  1. Sortarea prin selecția minimului:
    • Start -> Pentru fiecare element i: Găsește minimul în lista nesortată -> Interschimbă minimul cu arr[i] -> Stop.

7. Concluzie:

  • Sortarea prin selecția minimului este utilă pentru liste mici sau când simplitatea implementării este mai importantă decât eficiența.
  • Prin implementarea acestui algoritm, elevii pot înțelege mai bine conceptele de comparare și interschimbare.
  • Este un algoritm fundamental care poate fi extins și optimizat pentru aplicații mai complexe.

Similar Posts

Lasă un răspuns

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