1
00:00:00,000 --> 00:00:05,726
>> [MUSIC JOC]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: un fel de selecție este o
algoritm care, așa cum s-ar putea aștepta,

3
00:00:08,600 --> 00:00:10,470
sortează un set de elemente.

4
00:00:10,470 --> 00:00:12,470
Și amintesc algoritm
este un set de pas-cu-pas

5
00:00:12,470 --> 00:00:15,260
de instrucțiuni pentru finalizarea unei sarcini.

6
00:00:15,260 --> 00:00:17,580
>> În selecție sorta
Ideea de bază este acest lucru,

7
00:00:17,580 --> 00:00:22,080
găsi cel mai mic element nesortat și
adăugați-l la sfârșitul listei sortate.

8
00:00:22,080 --> 00:00:26,970
Efectiv ceea ce face acest lucru este construi
o listă sortată, un element la un moment dat.

9
00:00:26,970 --> 00:00:29,800
Breaking-l în jos pentru a pseudocod
am putea afirma acest algoritm

10
00:00:29,800 --> 00:00:34,490
după cum urmează, se repetă acest lucru până când
nici un element nesortate rămân.

11
00:00:34,490 --> 00:00:38,660
Căutați prin nesortat
date pentru a găsi cea mai mică valoare,

12
00:00:38,660 --> 00:00:44,130
apoi schimba valoarea cea mai mică, cu
Primul element al părții nesortate.

13
00:00:44,130 --> 00:00:47,130
>> Aceasta poate ajuta pentru a vizualiza acest lucru,
Să aruncăm o privire la acest lucru.

14
00:00:47,130 --> 00:00:49,710
Deci acest lucru, eu susțin, este o
matrice nesortate și am

15
00:00:49,710 --> 00:00:53,040
indicat prin care indică faptul că toate
din elementele sunt de culoare roșie,

16
00:00:53,040 --> 00:00:54,420
ele nu sunt sortate încă.

17
00:00:54,420 --> 00:00:57,670
Aceasta este întregul
parte nesortate din matrice.

18
00:00:57,670 --> 00:01:02,020
>> Deci, hai sa mergem prin etapele de
selecție fel pentru a sorta această matrice.

19
00:01:02,020 --> 00:01:05,296
Deci, din nou, vom repeta
până rămâne nici un element nesortate.

20
00:01:05,296 --> 00:01:07,920
Vom căutare prin
date pentru a găsi cea mai mică valoare,

21
00:01:07,920 --> 00:01:11,990
și apoi de swap că valoarea cu
Primul element al părții nesortate.

22
00:01:11,990 --> 00:01:14,380
>> Chiar acum, din nou, întreaga
matrice este partea nesortate.

23
00:01:14,380 --> 00:01:16,534
Toate elementele roșii sunt nesortate.

24
00:01:16,534 --> 00:01:18,700
Asa ca am căuta prin și
găsim cea mai mică valoare.

25
00:01:18,700 --> 00:01:20,533
Începem de la început,
mergem până la capăt,

26
00:01:20,533 --> 00:01:23,630
găsim cea mai mică valoare este, o.

27
00:01:23,630 --> 00:01:24,860
Deci asta e prima parte.

28
00:01:24,860 --> 00:01:29,440
Și apoi partea a doua, schimb ca valoarea cu
primul element al părții nesortate,

29
00:01:29,440 --> 00:01:31,340
sau primul element roșie.

30
00:01:31,340 --> 00:01:34,980
>> În acest caz, care ar fi
cinci, asa ca am schimba una și cinci.

31
00:01:34,980 --> 00:01:37,320
Când facem acest lucru, putem
vezi vizual că am

32
00:01:37,320 --> 00:01:41,260
mutat de prim rang mai mic element
de matrice, la foarte început.

33
00:01:41,260 --> 00:01:43,920
Sortare în mod eficient acest element.

34
00:01:43,920 --> 00:01:47,520
>> Și astfel încât să putem confirma, într-adevăr
și de stat, care este de este sortată.

35
00:01:47,520 --> 00:01:52,080
Și așa vom indica porțiunea sortate
de oferta noastră, prin colorarea aceasta albastru.

36
00:01:52,080 --> 00:01:53,860
>> Acum ne repeta doar procesul din nou.

37
00:01:53,860 --> 00:01:57,430
Cautam prin partea nesortate de
matrice pentru a găsi cel mai mic element.

38
00:01:57,430 --> 00:01:59,000
În acest caz, este de două.

39
00:01:59,000 --> 00:02:02,100
>> Am schimba că, odată cu primul
element al părții nesortate.

40
00:02:02,100 --> 00:02:05,540
În acest caz, de două, de asemenea, se întâmplă să fie
primul element al părții nesortate.

41
00:02:05,540 --> 00:02:08,650
Așa că am două schimb cu ea însăși,
care de fapt doar două frunze

42
00:02:08,650 --> 00:02:11,257
unde este, și este sortate.

43
00:02:11,257 --> 00:02:13,840
Continuând pe, căutăm prin
pentru a găsi cel mai mic element.

44
00:02:13,840 --> 00:02:15,030
E trei.

45
00:02:15,030 --> 00:02:17,650
Am schimba cu primul
Element, care este de cinci.

46
00:02:17,650 --> 00:02:19,450
Și acum trei sunt sortate.

47
00:02:19,450 --> 00:02:22,440
>> Am căuta prin nou, iar noi
găsi cel mai mic element este de patru.

48
00:02:22,440 --> 00:02:28,070
Am schimba cu primul element al
parte nesortate, iar acum patru sunt sortate.

49
00:02:28,070 --> 00:02:29,910
>> Constatăm că cinci este
cel mai mic element.

50
00:02:29,910 --> 00:02:32,900
Am schimba cu primul
element al părții nesortate.

51
00:02:32,900 --> 00:02:34,740
Și acum cinci sunt sortate.

52
00:02:34,740 --> 00:02:36,660
>> Și apoi în cele din urmă, ne
parte nesortate constă

53
00:02:36,660 --> 00:02:38,576
de doar un singur element,
asa ca am căuta prin

54
00:02:38,576 --> 00:02:41,740
și constatăm că șase este
mai mic, și, de fapt, doar elementul.

55
00:02:41,740 --> 00:02:44,906
Și apoi putem afirma că este sortate.

56
00:02:44,906 --> 00:02:47,530
Și acum ne-am pornit oferta noastră
de a fi complet nesortate

57
00:02:47,530 --> 00:02:52,660
în roșu, a sortate complet
în albastru, folosind selecția fel.

58
00:02:52,660 --> 00:02:54,920
>> Deci, ce este cel mai rău caz aici?

59
00:02:54,920 --> 00:02:57,830
Ei bine, în cel mai rău absolut
caz, trebuie să se uite peste

60
00:02:57,830 --> 00:03:02,170
toate elementele matricei la
găsi cel mai mic element nesortat,

61
00:03:02,170 --> 00:03:04,750
și trebuie să repetăm
acest proces de n ori.

62
00:03:04,750 --> 00:03:09,090
Odată pentru fiecare element al matricei
pentru că numai noi, în acest algoritm,

63
00:03:09,090 --> 00:03:12,180
fel un element la momentul.

64
00:03:12,180 --> 00:03:13,595
>> Care este cel mai bun caz?

65
00:03:13,595 --> 00:03:15,040
Ei bine, e exact la fel, nu?

66
00:03:15,040 --> 00:03:18,440
Noi de fapt, au să-și intensifice în continuare prin
fiecare singur element de matrice

67
00:03:18,440 --> 00:03:22,040
în scopul de a confirma faptul că este,
în fapt, cel mai mic element.

68
00:03:22,040 --> 00:03:26,760
>> Deci cel mai rău Runtime caz, ne vom
trebuie să repete un proces de n ori,

69
00:03:26,760 --> 00:03:28,960
o dată pentru fiecare dintre n elemente.

70
00:03:28,960 --> 00:03:31,940
Și în cel mai bun caz,
trebuie să facă același lucru.

71
00:03:31,940 --> 00:03:35,340
>> Deci, gândire înapoi nostru
set de instrumente de calcul complexitatea,

72
00:03:35,340 --> 00:03:39,250
ce crezi că este cel mai rău
caz de execuție pentru selectarea fel?

73
00:03:39,250 --> 00:03:41,840
Care credeți că este cel mai bun
caz de execuție pentru selectarea fel?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Ai ghicit Big O N pătrat,
și Big Omega de n pătrat?

76
00:03:49,325 --> 00:03:49,950
Ai avea dreptate.

77
00:03:49,950 --> 00:03:52,490
Acestea sunt, de fapt,
cel mai rău caz și cel mai bun caz a alerga

78
00:03:52,490 --> 00:03:55,100
ori, pentru selectarea fel.

79
00:03:55,100 --> 00:03:56,260
>> Sunt Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Acest lucru este CS50.

81
00:03:58,600 --> 00:04:00,279