1
00:00:06,911 --> 00:00:09,176
Lucrezi la biblioteca universității.

2
00:00:09,177 --> 00:00:11,396
E o după-masă liniștită

3
00:00:11,397 --> 00:00:17,061
când deodată vine
o livrare de 1.280 de cărți.

4
00:00:17,811 --> 00:00:21,489
Cărțile au fost livrate
într-o linie lungă și continuă,

5
00:00:21,490 --> 00:00:23,087
dar în dezordine

6
00:00:23,088 --> 00:00:26,301
și sistemul de clasificare
automată e stricat.

7
00:00:26,691 --> 00:00:29,476
Pe deasupra, cursurile încep mâine

8
00:00:29,477 --> 00:00:31,814
cea ce înseamnă că de dimineață devreme

9
00:00:31,815 --> 00:00:35,887
studenții vor veni în număr mare
ca să-și caute cărțile.

10
00:00:36,147 --> 00:00:38,583
Cum le sortezi pe toate la timp ?

11
00:00:39,123 --> 00:00:44,409
O metodă ar fi începerea dintr-un capăt
cu prima pereche de cărți.

12
00:00:44,729 --> 00:00:48,575
Dacă primele două cărți
sunt în ordine, lasă-le așa.

13
00:00:48,576 --> 00:00:50,609
Dacă nu, schimbă-le între ele.

14
00:00:50,610 --> 00:00:54,655
Fă același lucru cu a doua
și a treia carte, repetă procesul

15
00:00:54,656 --> 00:00:57,711
și continuă până când ajungi
la capătul liniei.

16
00:00:57,712 --> 00:01:00,961
La un moment dat vei da de cartea
care ar trebui să fie ultima

17
00:01:00,962 --> 00:01:04,486
și continuă să le schimbi
cu fiecare carte ce urmează,

18
00:01:04,486 --> 00:01:08,247
mutându-le până ajung la locul lor.

19
00:01:08,970 --> 00:01:12,114
Apoi ia-o de la început și repetă procesul

20
00:01:12,115 --> 00:01:15,399
ordonând toate cărțile la locul lor

21
00:01:15,400 --> 00:01:18,131
și continuă așa până toate vor fi sortate.

22
00:01:18,621 --> 00:01:21,661
Abordarea aceasta se numește
metoda balonului.

23
00:01:21,662 --> 00:01:23,955
E simplă, dar lentă.

24
00:01:23,956 --> 00:01:29,130
Ai face inițial 1.279 de comparații,

25
00:01:29,131 --> 00:01:33,422
apoi 1.278 și tot așa,

26
00:01:33,423 --> 00:01:38,341
ajungând la 818.560 de comparații.

27
00:01:38,342 --> 00:01:43,653
Dacă fiecare ar lua o secundă,
procesul ar dura peste nouă zile.

28
00:01:44,043 --> 00:01:48,338
O altă strategie ar fi să începi
cu sortarea primelor două cărți și atât.

29
00:01:48,339 --> 00:01:52,993
Apoi ia a treia carte
și compar-o cu cea de-a doua.

30
00:01:53,493 --> 00:01:56,932
Dacă locul său e înaintea acesteia,
schimbă-le între ele,

31
00:01:56,933 --> 00:01:59,400
apoi compar-o cu cea de pe primul loc

32
00:01:59,401 --> 00:02:01,441
și schimbă iar dacă e nevoie.

33
00:02:01,442 --> 00:02:03,639
Acum ai sortat primele trei cărți.

34
00:02:03,640 --> 00:02:07,491
Continuă să adaugi câte o carte
liniei deja ordonate,

35
00:02:07,492 --> 00:02:11,828
comparând și plasând noua carte

36
00:02:11,829 --> 00:02:15,434
acolo unde se potrivește.

37
00:02:15,734 --> 00:02:18,072
Această ordonare se numește
tehnica de inserție.

38
00:02:18,073 --> 00:02:19,523
Comparativ cu cea inițială,

39
00:02:19,524 --> 00:02:22,943
aceasta nu cere compararea
fiecărei perechi de cărți.

40
00:02:22,944 --> 00:02:26,953
În medie, se așteaptă
compararea fiecărei cărți

41
00:02:26,954 --> 00:02:29,213
cu jumătatea cărților ce urmează.

42
00:02:29,214 --> 00:02:32,122
În cazul ăsta, numărul total de comparații

43
00:02:32,123 --> 00:02:35,982
ar fi 409 280,

44
00:02:35,983 --> 00:02:37,465
durând cam cinci zile.

45
00:02:37,865 --> 00:02:40,353
Încă faci prea multe comparații.

46
00:02:40,354 --> 00:02:42,244
Uite o idee mai bună.

47
00:02:42,245 --> 00:02:44,614
Întâi, ridică aleatoriu o carte.

48
00:02:44,615 --> 00:02:48,956
Folosește-o ca separator
și compar-o cu fiecare carte.

49
00:02:49,396 --> 00:02:51,304
Apoi împarte linia

50
00:02:51,305 --> 00:02:54,776
așezând cărțile
dinaintea separatorului la stânga

51
00:02:55,386 --> 00:02:58,544
și cele ce vin după, la dreapta.

52
00:02:58,545 --> 00:03:00,314
Tocmai ai economisit
o grămadă de timp

53
00:03:00,314 --> 00:03:03,704
fără să fi nevoit să compari
toate cărțile din stânga

54
00:03:03,705 --> 00:03:06,555
cu oricare din dreapta.

55
00:03:07,005 --> 00:03:09,424
Acum, uitându-te
doar la cărțile din stânga,

56
00:03:09,425 --> 00:03:12,301
poți iar alege o partiție aleatorie

57
00:03:12,302 --> 00:03:17,025
și separă cărțile ce vin înaintea ei
de cele ce vin după ea.

58
00:03:17,026 --> 00:03:19,696
Continui să împarți cărțile
pe baza aceluiași principiu

59
00:03:19,736 --> 00:03:22,383
până ajungi să formezi
mici stive de cărți,

60
00:03:22,384 --> 00:03:27,394
fiecare ordonându-se rapid pe baza
altei strategii, la de inserție.

61
00:03:27,614 --> 00:03:32,775
Fiecare rundă de partiție
numără cam 1 280 de comparații.

62
00:03:32,776 --> 00:03:35,316
Dacă stivele conțin cam
același număr de cărți,

63
00:03:35,466 --> 00:03:41,255
ar trebui să dea 128 de stive
cu 10 cărți în fiecare grup,

64
00:03:41,256 --> 00:03:43,946
și durează cam 8 960 de secunde.

65
00:03:43,947 --> 00:03:48,555
Sortarea acestor grupuri mai mici
ar dura cam 22 de secunde fiecare.

66
00:03:48,556 --> 00:03:51,816
Per total, cu această tehnică
numită catalogarea rapidă

67
00:03:51,817 --> 00:03:54,702
poți ordona cărțile
în mai puțin de trei ore și jumătate.

68
00:03:54,703 --> 00:03:55,996
Dar există o hibă.

69
00:03:55,997 --> 00:03:59,574
Partițiile pot fi asimetrice,
fiind cronofage.

70
00:03:59,575 --> 00:04:01,476
Din fericire se întâmplă rar.

71
00:04:01,477 --> 00:04:04,909
De aceea catalogarea rapidă e
una din cele mai eficiente strategii

72
00:04:04,910 --> 00:04:06,915
folosite de programatorii de azi.

73
00:04:06,916 --> 00:04:11,036
Se folosește la sortarea articolelor
după preț în magazinele online

74
00:04:11,037 --> 00:04:14,857
sau în crearea listelor stațiilor
de benzină din vecinătatea unei locații

75
00:04:14,858 --> 00:04:16,378
sortate după distanță.

76
00:04:16,379 --> 00:04:20,406
În cazul tău, ai sortat rapid
și ți-a rămas și ceva timp liber.

77
00:04:20,406 --> 00:04:22,748
Încă o zi cu miză mare la bibliotecă.