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

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 mij 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.)

        !grigore-moisil-2010/solutii/egipt?3.png!
Fig. 3. Poziţiile interschimbărilor: pij este indicele elementului egal cu j aflat pe poziţia i

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.