|

Algoritmi de Sortare – Sortarea prin Inserție 14


1. Obiectivele lecției:

  • Să înțeleagă principiul sortării prin inserție (Insertion Sort).
  • Să implementeze algoritmul în limbajul C++.
  • Să analizeze complexitatea algoritmului.
  • Să aplice sortarea prin inserție pentru rezolvarea unor probleme practice.

2. Conținutul lecției:

Ce este sortarea prin inserție?

  • Definiție: Sortarea prin inserție este un algoritm care construiește lista sortată pe măsură ce parcurge elementele nesortate, inserând fiecare element la poziția sa corectă în lista sortată.
  • Principiu: Compară elementul curent cu toate elementele din partea sortată a listei și îl inserează la locul potrivit.

Cum funcționează?

  1. Consideră primul element sortat.
  2. Parcurge restul elementelor din lista nesortată.
  3. Pentru fiecare element, compară-l cu elementele din lista sortată și mută elementele mai mari pentru a face loc.
  4. Inserează elementul curent la poziția corectă.

Pseudocod:

Intrare: Lista de n elemente

Pentru i de la 1 la n-1:

    Elementul curent = lista[i]

    j = i – 1

    Cât timp j >= 0 și lista[j] > Elementul curent:

        lista[j + 1] = lista[j]

        j = j – 1

    lista[j + 1] = Elementul curent

Ieșire: Lista sortată


3. Cod în C++:


Exemplu 1: Sortare crescătoare

#include <iostream>

using namespace std;

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

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

        int current = arr[i];

        int j = i – 1;

        // Mută elementele mai mari decât current la dreapta

        while (j >= 0 && arr[j] > current) {

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

            j–;

        }

        // Inserează elementul curent la poziția corectă

        arr[j + 1] = current;

    }

}

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);

    insertionSort(arr, n);

    cout << „Array sortat crescator: „;

    printArray(arr, n);

    return 0;

}


Exemplu 2: Sortare descrescătoare

#include <iostream>

using namespace std;

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

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

        int current = arr[i];

        int j = i – 1;

        // Mută elementele mai mici decât current la dreapta

        while (j >= 0 && arr[j] < current) {

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

            j–;

        }

        // Inserează elementul curent la poziția corectă

        arr[j + 1] = current;

    }

}

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);

    insertionSortDescending(arr, n);

    cout << „Array sortat descrescator: „;

    printArray(arr, n);

    return 0;

}


4. Complexitatea algoritmului:

  1. Cazul cel mai defavorabil (O(n²)):
    • Lista este ordonată invers.
    • Fiecare element trebuie comparat și mutat.
  2. Cazul cel mai favorabil (O(n)):
    • Lista este deja sortată.
    • Fiecare element este comparat o singură dată.
  3. Cazul mediu (O(n²)):
    • Lista are o ordine aleatorie.

Avantaje:

  • Simplu de implementat.
  • Eficient pentru liste mici sau aproape sortate.
  • Sortare stabilă (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 inserție.
  2. Realizați un program care sortează un șir de caractere în ordine alfabetică folosind sortarea prin inserție.
  3. Modificați algoritmul pentru a sorta array-ul crescător pentru elementele pozitive și descrescător pentru cele negative.

6. Scheme logice:

  1. Sortarea prin inserție:
    • Start -> Pentru fiecare element i -> Compară elementul curent cu elementele precedente -> Mută elementele mai mari -> Inserează elementul curent -> Stop.

7. Concluzie:

  • Sortarea prin inserție este un algoritm intuitiv și eficient pentru liste mici.
  • Este mai rapid decât alte metode simple (cum ar fi sortarea prin selecție) pentru liste aproape sortate.
  • Prin implementarea acestui algoritm, elevii vor înțelege mai bine conceptele de comparare și mutare a elementelor.

Similar Posts

Lasă un răspuns

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