Revizia anterioară Revizia următoare
Egipt
Rezolvare cu metoda greedy
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.
În a doua fază vor ajunge şi elementele egale cu 2 şi 3 la locul lor, prin interschimbări evidente.
