infoarena informatica de performanta

Egipt

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

Fig. 1. În mij avem numărul elementelor care trebuie duse de pe poziţia i pe poziţia j
Observăm că
m₁₂ + m₁₃ = m₂₁ + m₃₁
m₂₁ + m₂₃ = m₁₂ + m₃₂
m₃₁ + m₃₂ = m₁₃ + m₂₃

Dacă avem 2 pe poziţia unui 1 şi 1 pe poziţia unui 2, avem nevoie de o singură interschimbare.
Dacă avem o configuraţie 2 3 1, sau 3 1 2, avem nevoie de două interschimbări.

Rezultă că numărul minim de interschimbări care sunt necesare pentru ordonarea şirului este:
min(m₁₂, m₂₁) + min(m₂₃, m₃₂) + min(m₁₃, m₃₁) + 2|m₁₂ − m₂₁|
Realizarea interschimbărilor:

 
Fig. 3. Poziţiile interschimbărilor: p_ij este indicele elementului egal cu j aflat pe poziţia i

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