Clasa a 7-a Lecția 2: Problema selecției și stive
Înregistrare video lecție
Problema selecției
Problema
Dat un șir de n numere și o poziție k în acel șir să se spună ce element s-ar afla pe acea poziție dacă șirul ar fi sortat.
Exemplu
Fie șirul 3 9 23 13 18 8 3 10 2 10 15 21 și poziția k = 6.
Dacă am ordona șirul am obține 2 3 3 8 9 10 10 13 15 18 21 23. Pe poziția 6 se află elementul 10, care este și răspunsul dorit.
Soluție forță brută
O soluție ce vine ușor în minte este să sortăm vectorul și apoi să afișăm elementul de la poziția k. Nu este eficientă, complexitatea ei va fi O(n2) cu sortare prin selecție, sau O(n log n) cu sortări mai rapide.
Soluția folosind algoritmul Quick select
Aplicăm un pas de pivotare în mod repetat. Algoritmul este prezentat aici: quickselect.
Ideea pivotării este următoarea: alegem un așa numit pivot. El este un element oarecare din vector. Putem să alegem elementul aflat la jumatea vectorului, v[n/2]. Sau putem să îl alegem la întâmplare, folosind o funcție ce generează numere aleatoare, cum ar fi funcția rand() în C (parte din biblioteca stdlib.h).
Fie p indicele pivotului și val = v[p] valoarea acelui pivot. Ne propunem să separăm vectorul în două: prima parte va conține elemente mai mici sau egale cu pivotul val. A doua parte va conține elemente mai mari sau egale cu pivotul val.
Odată efecutată pivotarea vom ști în care din cele două părți se va afla elementul pe poziția k în vectorul sortat. Putem, deci, selecta acea parte, continuând algoritmul doar pentru acel subvector.
Există mai mulți algoritmi de pivotare, toți liniari. Vă rămâne ca temă să implementați unul din ei. În linkul de pe Wikipedia de mai sus găsiți algoritmul propus de Lomuto, care nu este cel mai eficient. Ca bonus, v-aș recomanda să implementați algoritmul original al lui Tony Hoare.
Atenție! El nu este structurat! Va trebui să îl modificați! Sau, voi aprecia și mai mult dacă găsiți propria voastră implementare :-) .
Ce complexitate are acest algoritm?
Vom aplica în mod repetat pivotarea, ce are complexitate O(n). Pe medie vom păstra, la fiecare pas, jumătate din vector. Complexitatea va fi, deci, O(n + n/2 + n/4 + ... + 1). Observăm că suma nu va depăși niciodată 2n (deși se va apropia de acea valoare). Complexitatea este, deci O(n).
Atenție! Aceasta este o complexitate medie! Pe cazul cel mai rău putem să selectăm mereu o parte a vectorului care are cu un element mai puțin ca vectorul curent, ceea ce duce la o complexitate de O(n2) pe cazul cel mai rău.
Aplicăm repetat pivotarea quickselect. Calcul aproximativ al complexității pe cazul mediu: este O(n), în loc de O(n log n) dacă am fi sortat.
Pentru cei curioși, există o îmbunătățire a algoritmului quick select ce îi schimbă complexitatea la O(n) chiar și pe cazul cel mai rău, dar ea depășește nivelul cursului nostru. Puteți citi mai multe despre medianul medianelor aici: https://en.wikipedia.org/wiki/Median_of_medians .
Stive
Ce este un tip de date abstract?
Un tip de date abstract este un model matematic, ce privește tipul de date din punctul de vedere al utilizatorului. Astfel, el definește operații asupra datelor și comportamentul acestor operații, dar nu specifică o implementare.
Tipurile de date abstracte separă funcționalitatea de implementare. Acest lucru este util pentru analiza complexității algoritmilor. Este de menționat faptul că unele TDA au multiple implementări, cu avantaje și dezavantaje, precum vom vedea în lecțiile următoare.
Ce este o stivă?
Stiva (în engleză stack) este un concept simplu, pe care l-am mai folosit în trecut, fără a sublinia faptul că folosim o stivă.
O stivă este o grămadă de obiecte ordonate după ordinea LIFO: last in, first out. Aceasta înseamnă că putem adăuga obiecte în stivă, iar atunci când le vom scoate, le vom scoate în ordine inversă față de cum le-am adăugat. Vom vedea în lecțiile următoare că, prin contrast, coada scoate obiectele în aceeași ordine în care au fost adăugate.
Stiva este un tip de date abstract în care definim operațiile:
push(value)- inserează o valoare dată la sfârșitul listei;top- returnează valoarea de la sfârșitul listei;pop- șterge valoarea de la sfârșitul listei;empty- returnează 1 dacă stiva este goală (poate fi implementată și în cadrul operației top).
Pentru aceste operații există restricția menționată, anume că valorile trebuie returnate cu regula LIFO (Last In, First Out).
Pentru a înțelege mai bine ce este o stivă, urmăriți clipul de mai jos:
Implementare: stivă de întregi pozitivi sau zero
În practică stiva se implementează aproape întotdeauna ca un vector căruia i se adaugă la coadă elemente:
#define MAXN 1000
int stack[MAXN]; // stocarea valorilor propriu-zise
int stack_pointer = 0; // indice la prima valoare nefolosita in vector (totuna cu numărul de elemente din stiva)
// adauga valoarea 'val' la stiva, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de stiva plina
int push( int val ) {
if ( stack_pointer >= MAXN ) // stiva este plina?
return 0; // returnam eroare
stack[stack_pointer++] = val; // adaugam valoarea in stiva
return 1; // returnam succes
}
// returnează valoarea aflată în virful stivei, dacă ea exista
// in caz contrar returneaza -1
int top() {
return stack_pointer > 0 ? stack[stack_pointer - 1] : -1;
}
// elimina ultimul element din stiva daca se poate
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if ( stack_pointer == 0 ) // testam cazul de eroare
return 0;
stack_pointer--; // daca avem elemente pe stiva, il eliminam pe ultimul
return 1;
}
// returneaza 1 daca stiva este goala, 0 in caz contrar
int empty() {
return stack_pointer > 0;
}
Observații:
- În această implementare, cele patru operații au complexitate O(1).
- Remarcați o folosire corectă a funcțiilor: ele implementează operațiuni ce au sens separat, de sine stătător.
- Remarcați denumirile funcțiilor: ele sugerează operațiunea implementată.
- Am folosit instrucțiunea return în mijlocul funcției. Aceasta este o excepție de la regulă. Pe caz general, atunci când la intrarea într-o funcție avem de tratat cazuri particulare de ieșire imediată din funcție, putem folosi instrucțiunea return. Codul devine astfel mai clar, iar restul corpului funcției nu se deplasează spre dreapta prin indentare.
Sfaturi în utilizarea stivelor pentru rezolvarea problemelor
- Pentru problemele noastre, stiva se va implementa cu ajutorul unui vector;
- Operațiile
top,emptyșipoppresupun verificarea și manipularea numărului de elemente din vector. În exemplul de implementare numărul de elemente este denumitstack_pointer. Dar dacă vectorul vostru denumește numărul de elementen, atunci veți opera cun; - Nu este neapărată nevoie să scrieți funcții ca cele de mai sus pentru a lucra cu stive. Exemplul de mai sus își dorește să explice noțiunea de tip de date abstract care definește acele operații, iar implementarea arată cum s-ar implementa ele. Deci, ne interesează modul de funcționare al stivei, dar implementarea o putem face cum simțim că se potrivește mai bine problemei.
Tema 2
Să se rezolve următoarele probleme (program C în CodeBlocks, trimis la NerdArena):
