Capitolul 18 · Lecția 18.3 din 4

Interclasarea a doi vectori sortați

Algoritmul cu doi indici, complexitatea liniară și legătura cu sortarea prin interclasare.

Capitolul 18: Algoritmi clasici de BAC

Pe această pagină6 secțiuni

Problema

Ai doi vectori deja sortați crescător. Trebuie să obții un al treilea vector, tot sortat, care conține toate elementele.

De ce nu concatenezi și sortezi

Ar merge, dar ai pierde informația că vectorii erau deja sortați. Concatenare plus sortare înseamnă $O((n+m) \log(n+m))$ . Interclasarea corectă face $O(n + m)$ , adică liniar.

Algoritmul

Folosești doi indici, câte unul pentru fiecare vector:

cât timp ambii indici sunt în interiorul vectorilor, compari elementele curente și îl iei pe cel mai mic, avansând indicele corespunzător;
când unul dintre vectori s-a terminat, copiezi restul celuilalt, care e deja sortat.

Pasul 2 e esențial și e cel mai des uitat.

Exemplu

$a = [1, 4, 7]$ , $b = [2, 3, 8, 9]$

Pas	Compară	Ia	Rezultat
1	1 vs 2	1	[1]
2	4 vs 2	2	[1,2]
3	4 vs 3	3	[1,2,3]
4	4 vs 8	4	[1,2,3,4]
5	7 vs 8	7	[1,2,3,4,7]
6	a epuizat	rest din b	[1,2,3,4,7,8,9]

Legătura cu sortarea prin interclasare

Interclasarea e pasul de bază al algoritmului merge sort: împarți vectorul în două, sortezi fiecare jumătate, apoi le interclasezi. Complexitate totală: $O(n \log n)$ .

Reține

Cele două bucle finale, care copiază ce a rămas, nu sunt opționale. Fără ele pierzi elemente, iar programul dă rezultat parțial, care pare corect la prima vedere.

Greșeli frecvente

Se uită copierea restului. Verifică mereu cu un exemplu în care un vector se termină primul.
Se folosește un singur indice pentru ambii vectori.
Se presupune că vectorii sunt sortați fără să fie. Interclasarea cere vectori sortați.

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[100], b[100], c[200];
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];

    for (int t = 0; t < k; t++) cout << c[t] << " ";
    return 0;
}

Date de intrarese trimit programului la citire

Instrumente pentru lecția asta

Vizualizator de sortări

Vezi pas cu pas cum lucrează metoda bulelor, a selecției, a inserției și a numărării pe același vector.

compară vecini și îi interschimbă

mutare
comparație
la locul ei

Pornim.

pasul 1 din 24

Numără pașii: pentru același vector, metodele nu fac același număr de operații.

Explorează interactiv

Se încarcă instrumentul…

Bifează când ai terminat, ca s-o vezi citită pe toate dispozitivele.

Testează-te pe capitolul 18

Lecția în clipuri

Clipuri scurte, cu voce și subtitrări.