h2(#egipt). 'Egipt':problema/egipt

*Solutie $1$*

*Soluţie $1$*

Fie $n1$ numărul elementelor egale cu $1$, $n2$ numărul elementelor egale cu $2$ şi $n3$ numărul elementelor egale cu $3$ în şirul dat $a$. Altfel spus, în şirul ordonat vom avea valori egale cu $1$ începând cu poziţia $1$ până la poziţia $n1$, valori egale cu $2$ începând cu poziţia $n1+1$ până la poziţia $n1+n2$, după care vom avea elemente egale cu $3$.
Notăm cu $m{~ij~}$ numărul elementelor egale cu $j$ care se află pe o poziţie pe care ar trebui să avem valoarea $i$. (Matricea $m$ are $3$ linii şi $3$ coloane.)

*Solutie $2$*

*Soluţie $2$*

Rezolvarea se face în două faze. În prima fază vom pune la loc elementele egale cu $1$. Pornim cu trei variabile: $i$ va itera pornind din prima poziţie şi va merge până în ultima poziţie unde trebuie să ajungă un element egal cu $1$; $i2$ va porni din prima poziţie unde trebuie să ajungă un element egal cu $2$ şi va merge pâna la ultima poziţie de acest fel; similar $i3$ va itera pe intervalul unde trebuie să ajungă elementele egale cu $3$.
$i2$ şi $i3$ vor fi poziţionate întotdeauna asupra unui element egal cu $1$. Dacă elementul pe care am poziţionat $i$ este egal cu $1$, nu trebuie să facem nimica, doar incrementăm $i$. Dacă acesta este egal cu $2$, vom schimba elementele de pe locurile $i$ şi $i2$ şi vom incrementa $i$, iar pe $i2$ îl poziţionăm pe următorul element egal cu $1$. Dacă cu $i2$ am depăşit pragul din dreapta al intervalului (adică ultimul loc unde trebuie să ajungă $2$), elementul de pe poziţia $i$ îl vom schimba cu elementul arătat de $i3$. Procedăm similar pentru elementele egale cu $3$.