1
00:00:00,000 --> 00:00:05,726
>> [Muusika mängib]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Valik omamoodi on
algoritmi, et te võite arvata,

3
00:00:08,600 --> 00:00:10,470
sorteerib elementidega.

4
00:00:10,470 --> 00:00:12,470
Ja algoritm tagasikutsumine
on samm-sammult komplekt

5
00:00:12,470 --> 00:00:15,260
käskude täitmise ülesanne.

6
00:00:15,260 --> 00:00:17,580
>> Veinide sorteerida
Põhiidee on see,

7
00:00:17,580 --> 00:00:22,080
Leida väikseim sorteerimata element ja
lisada see lõpuks sorteeritud nimekirja.

8
00:00:22,080 --> 00:00:26,970
Tõhusalt Mis see on ehitada
Sorteeritud nimekirja, üks element korraga.

9
00:00:26,970 --> 00:00:29,800
Breaking see alla pseudokoodi
me võiks väita seda algoritmi

10
00:00:29,800 --> 00:00:34,490
järgmiselt korda seda kuni
no sorteerimata elemendid jäävad.

11
00:00:34,490 --> 00:00:38,660
Otsige sorteerimata
andmete leida väikseim väärtus,

12
00:00:38,660 --> 00:00:44,130
siis vahetada väiksema väärtusega koos
Esimene osa sorteerimata osa.

13
00:00:44,130 --> 00:00:47,130
>> See võib aidata visualiseerida seda,
Võtame pilk see.

14
00:00:47,130 --> 00:00:49,710
Nii et see, ma väita, on
sorteerimata massiivi ja ma olen

15
00:00:49,710 --> 00:00:53,040
märkinud, näidates, et kõik
elemendid on punased,

16
00:00:53,040 --> 00:00:54,420
need pole veel sorteerida.

17
00:00:54,420 --> 00:00:57,670
See on kogu
sorteerimata osa massiivi.

18
00:00:57,670 --> 00:01:02,020
>> Nii lähme läbi sammud
valikut omamoodi sorteerida seda valikut.

19
00:01:02,020 --> 00:01:05,296
Nii jälle, me saame korrata
kuni ei sorteerimata elemendid jäävad.

20
00:01:05,296 --> 00:01:07,920
Me teeme otsida
andmete leida väikseim väärtus,

21
00:01:07,920 --> 00:01:11,990
ja siis vahetada, et väärtus koos
Esimene osa sorteerimata osa.

22
00:01:11,990 --> 00:01:14,380
>> Praegu jälle kogu
massiiv on sorteerimata osa.

23
00:01:14,380 --> 00:01:16,534
Kõik punase elemendid sorteerimata.

24
00:01:16,534 --> 00:01:18,700
Nii me otsida ja
leiame väikseim väärtus.

25
00:01:18,700 --> 00:01:20,533
Me alustame algusest,
läheme lõpuni,

26
00:01:20,533 --> 00:01:23,630
leiame väikseim väärtus on üks.

27
00:01:23,630 --> 00:01:24,860
Nii et esimene osa.

28
00:01:24,860 --> 00:01:29,440
Ja siis teine ​​osa, vahetada, et väärtus
esimene osa sorteerimata osa,

29
00:01:29,440 --> 00:01:31,340
või esimese punase element.

30
00:01:31,340 --> 00:01:34,980
>> Sellisel juhul oleks
viis, nii et me vahetada üks kuni viis.

31
00:01:34,980 --> 00:01:37,320
Kui me seda teeme, saame
visuaalselt näha, et me oleme

32
00:01:37,320 --> 00:01:41,260
kolis väikseim väärtus element
massiivi, et algusest peale.

33
00:01:41,260 --> 00:01:43,920
Tõhusalt sorteerimine, et element.

34
00:01:43,920 --> 00:01:47,520
>> Ja nii me saame tõepoolest kinnitada
ja väidavad, et üks on järjestatud.

35
00:01:47,520 --> 00:01:52,080
Ja nii me näitavad järjestatud osa
meie massiivi, värvimine see sinine.

36
00:01:52,080 --> 00:01:53,860
>> Nüüd jääb üle vaid korrata protsessi uuesti.

37
00:01:53,860 --> 00:01:57,430
Me otsida sorteerimata osa
massiivi leida väikseim element.

38
00:01:57,430 --> 00:01:59,000
Sel juhul on kaks.

39
00:01:59,000 --> 00:02:02,100
>> Me vahetada, et esimese
element sorteerimata osa.

40
00:02:02,100 --> 00:02:05,540
Sel juhul kaks ka juhtub olema
esimene osa sorteerimata osa.

41
00:02:05,540 --> 00:02:08,650
Nii me swap kaks iseendaga
mis tõesti lihtsalt jätab kaks

42
00:02:08,650 --> 00:02:11,257
kus see on, ja see on järjestatud.

43
00:02:11,257 --> 00:02:13,840
Jätkub me otsida
leida kõige väikseim element.

44
00:02:13,840 --> 00:02:15,030
See on kolm.

45
00:02:15,030 --> 00:02:17,650
Me vahetada see esimene
element, mis on viis.

46
00:02:17,650 --> 00:02:19,450
Ja nüüd kolm on järjestatud.

47
00:02:19,450 --> 00:02:22,440
>> Me otsida uuesti, ja me
Leida väikseim element on neli.

48
00:02:22,440 --> 00:02:28,070
Me vahetada see esimene osa
sorteerimata osa, ja nüüd neli on järjestatud.

49
00:02:28,070 --> 00:02:29,910
>> Me leiame, et viis on
väikseim element.

50
00:02:29,910 --> 00:02:32,900
Me vahetada see esimene
element sorteerimata osa.

51
00:02:32,900 --> 00:02:34,740
Ja nüüd viis on järjestatud.

52
00:02:34,740 --> 00:02:36,660
>> Ja siis lõpuks, meie
sorteerimata osa koosneb

53
00:02:36,660 --> 00:02:38,576
vaid ühe elemendi,
nii et me otsida

54
00:02:38,576 --> 00:02:41,740
ja me leiame, et kuus on
väikseim, ja tegelikult ainus element.

55
00:02:41,740 --> 00:02:44,906
Ja siis saame väita, et see on järjestatud.

56
00:02:44,906 --> 00:02:47,530
Ja nüüd me oleme lülitatakse meie massiivi
alates on täiesti Sorteerimata

57
00:02:47,530 --> 00:02:52,660
punane, täielikult järjestatud
sinine, kasutades valikut omamoodi.

58
00:02:52,660 --> 00:02:54,920
>> Mis siis halvimal juhul siin?

59
00:02:54,920 --> 00:02:57,830
Noh absoluutne halvim
Juhul, me peame vaatama üle

60
00:02:57,830 --> 00:03:02,170
kõik elemendid massiivi
Leida väikseim sorteerimata element,

61
00:03:02,170 --> 00:03:04,750
ja me peame kordama
Selle protsessi n korda.

62
00:03:04,750 --> 00:03:09,090
Kui iga element massiivi
sest me ainult selle algoritmi,

63
00:03:09,090 --> 00:03:12,180
Sorteeri üks element ajal.

64
00:03:12,180 --> 00:03:13,595
>> Milline on parim stsenaarium?

65
00:03:13,595 --> 00:03:15,040
Aga see on täpselt sama, eks ole?

66
00:03:15,040 --> 00:03:18,440
Me tegelikult on ikka sammult läbi
iga element massiivi

67
00:03:18,440 --> 00:03:22,040
et kinnitada, et see on,
tegelikult väikseim element.

68
00:03:22,040 --> 00:03:26,760
>> Nii et halvimal juhul runtime, me
kordama protsessi n korda,

69
00:03:26,760 --> 00:03:28,960
üks kord iga n elemente.

70
00:03:28,960 --> 00:03:31,940
Ja parimal juhul,
me peame tegema sama.

71
00:03:31,940 --> 00:03:35,340
>> Nii mõeldes meie
arvutuslik keerukus tööriistakasti,

72
00:03:35,340 --> 00:03:39,250
Mis sa arvad, on kõige hullem
Juhul runtime valiku omamoodi?

73
00:03:39,250 --> 00:03:41,840
Mis te arvate, on parim
Juhul runtime valiku omamoodi?

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

75
00:03:44,760 --> 00:03:49,325
>> Kas sa vist Big O n ruudus
ja Big Omega n ruudus?

76
00:03:49,325 --> 00:03:49,950
Sa oleks õige.

77
00:03:49,950 --> 00:03:52,490
Need on, et tegelikult
Halvimal juhul ja parimal juhul run

78
00:03:52,490 --> 00:03:55,100
korda, valiku omamoodi.

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

80
00:03:56,260 --> 00:03:58,600
See on CS50.

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