Deo zbornika Učimo algoritme

Algoritam uparivanja čarapa

Kada sam bio student na MIT-u, jedan od mojih cimera imao je nekoliko desetina parova čarapa, svaki par sa malo drugačijom bojom ili dizajnom. Često je odlagao pranje veša dok nije potpuno ostao bez čistih čarapa, pa je svaki put kada bi ih prao imao prilično težak zadatak da ih ponovo upari.

Evo kako je to radio: Prvo bi izvadio nasumičnu čarapu iz gomile čistog veša, pa bi zatim izvadio još jednu nasumično i uporedio je sa prvom da vidi da li se slažu. Ako se nisu slagale, vratio bi drugu čarapu i izvadio novu. Nastavljao bi to sve dok ne bi našao odgovarajući par, a zatim bi ponovio isti postupak sa novom čarapom. Pošto je morao da pretražuje veliki broj čarapa, proces je išao vrlo sporo — naročito na početku, jer je bilo mnogo više čarapa za pregledanje pre nego što bi se pojavio par.

Studirao je matematiku i očigledno je pohađao neki kurs o računarima. Jednog dana, kada je doneo svoju korpu za veš nazad u našu sobu, objavio je: „Odlučio sam da koristim bolji algoritam za uparivanje čarapa.“ Hteo je da kaže da će sada koristiti postupak potpuno različite prirode. Izvadio je prvu čarapu i stavio je na sto, zatim je izvadio sledeću čarapu i uporedio je sa prvom; pošto se nisu slagale, stavio je drugu pored prve. Sada bi svaku novu čarapu koju bi izvadio uporedio sa rastućim redom čarapa na stolu. Kada bi pronašao par, spojio bi ih i ubacio u fioku. Kada nije, dodao bi neuparenu čarapu u red. Korišćenjem ovog metoda, uspeo je da upari čarape višestruko brže nego ranije.

Izvor: W. Daniel Hillis, The Pattern On The Stone: The Simple Ideas That Make Computers Work