1
00:00:00,000 --> 00:00:02,826
>> [Mūzikas atskaņošanai]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Tātad ievietošanas kārtošanas ir cits
algoritmu mēs varam izmantot, lai sakārtotu masīvu.

4
00:00:09,370 --> 00:00:12,350
Ideja šo algoritmu
ir veidot savu sakārtoti masīvs

5
00:00:12,350 --> 00:00:19,670
vietā, novirzot elementus no
veids, kā jums iet, lai padarītu telpu.

6
00:00:19,670 --> 00:00:22,240
Tas ir nedaudz atšķirīgs
no atlases veida vai burbuļa

7
00:00:22,240 --> 00:00:25,460
veida, piemēram, kur
mēs esam pielāgojot vietas,

8
00:00:25,460 --> 00:00:26,910
kur mēs nesam mijmaiņas darījumus.

9
00:00:26,910 --> 00:00:29,760
>> Šajā gadījumā tas, ko mēs esam patiesībā
dara, ir bīdāmās elementi

10
00:00:29,760 --> 00:00:31,390
vairāk, no tā.

11
00:00:31,390 --> 00:00:34,030
Kā šo algoritmu
strādāt pseudocode?

12
00:00:34,030 --> 00:00:37,646
Nu pieņemsim tikai patvaļīgi teikt, ka
masīva pirmais elements ir sakārtots.

13
00:00:37,646 --> 00:00:38,770
Mēs esam ēka to vietā.

14
00:00:38,770 --> 00:00:42,660
>> Mēs esam gonna iet vienu elementu laikā un
veidot tā, un tā ir pirmā lieta, ko mēs redzam

15
00:00:42,660 --> 00:00:43,890
ir viens no elementiem masīvs.

16
00:00:43,890 --> 00:00:47,720
Un pēc definīcijas, viena
elements masīvs ir sakārtots.

17
00:00:47,720 --> 00:00:50,850
>> Tad mēs atkārtot šo procesu until--
mēs atkārtot šādu procesu

18
00:00:50,850 --> 00:00:52,900
līdz visi no elementiem, kas ir sakārtoti.

19
00:00:52,900 --> 00:00:57,770
Paskaties nākamajā nešķirotu elementu un
ievietojiet to šķiroto daļu,

20
00:00:57,770 --> 00:01:01,209
pārvietojot vajadzīgo skaitu
elementu no tā.

21
00:01:01,209 --> 00:01:03,750
Cerams, ka šī vizualizācija
palīdzēs jums redzēt tieši to, kas ir

22
00:01:03,750 --> 00:01:05,980
notiek ar ievietošanas veida.

23
00:01:05,980 --> 00:01:08,010
>> Tātad atkal, šeit ir mūsu
Visa nešķiroti masīvs,

24
00:01:08,010 --> 00:01:10,970
visus elementus, kas norādīts sarkanā krāsā.

25
00:01:10,970 --> 00:01:13,320
Un pieņemsim sekot
soļi mūsu pseudocode.

26
00:01:13,320 --> 00:01:16,970
Pirmā lieta, ko mēs darām, ir mēs saucam
masīva pirmais elements, sakārtoti.

27
00:01:16,970 --> 00:01:20,920
Tātad mēs esam tikai gonna teiksim
pieci, jūs tagad sakārtoti.

28
00:01:20,920 --> 00:01:24,570
>> Tad mēs skatāmies uz nākamo
nešķiroti elements masīva

29
00:01:24,570 --> 00:01:27,610
un mēs vēlamies, lai ievietotu, ka
uz sakārtoti daļu,

30
00:01:27,610 --> 00:01:29,750
pārvietojot elementus pāri.

31
00:01:29,750 --> 00:01:33,470
Tātad divi ir nākamais nešķiroti
masīva elements.

32
00:01:33,470 --> 00:01:36,250
Nepārprotami tas pieder, pirms
pieci, lai to, ko mēs esam gonna do

33
00:01:36,250 --> 00:01:41,580
ir sava veida turēt divus malā uz otru,
pāriet pieci pāri, un pēc tam ievietot divas

34
00:01:41,580 --> 00:01:43,210
Pirms pieciem, kur jāiet.

35
00:01:43,210 --> 00:01:45,280
Un tagad mēs varam teikt, ka divi ir sakārtots.

36
00:01:45,280 --> 00:01:48,400
>> Tātad, kā jūs varat redzēt, mēs esam tikai tik tālu
paskatījās diviem elementiem masīva.

37
00:01:48,400 --> 00:01:50,600
Mēs neesam paskatījās
atpūsties vispār, bet mēs esam

38
00:01:50,600 --> 00:01:54,582
got šie divi elementi sakārtoti pēc
veids pārslēgšanas mehānisma.

39
00:01:54,582 --> 00:01:56,410
>> Tātad mēs atkal atkārtojiet procesu.

40
00:01:56,410 --> 00:01:58,850
Paskaties nākamajā nešķiroti
elements, tas ir viens.

41
00:01:58,850 --> 00:02:04,010
Pieņemsim, ka tur malā uz otru,
novirzīt visu vairāk, un ievietojiet vienu

42
00:02:04,010 --> 00:02:05,570
kur tam vajadzētu iet.

43
00:02:05,570 --> 00:02:08,110
>> Atkal, tomēr, mēs esam tikai kādreiz
paskatījās viens, divi, un pieci.

44
00:02:08,110 --> 00:02:12,480
Mēs nezinām, ko vēl nāk,
bet mēs esam sakārtots šos trīs elementus.

45
00:02:12,480 --> 00:02:16,030
>> Nākamais nešķiroti elements ir
trīs, tāpēc mēs noteikti to malā.

46
00:02:16,030 --> 00:02:18,200
Mēs novirzīt vairāk nekā to, ko mēs
ir nepieciešams, kas, šoreiz

47
00:02:18,200 --> 00:02:21,820
nav viss kā iepriekšējā
divas lietas, tas ir tikai pieci.

48
00:02:21,820 --> 00:02:25,440
Un tad mēs stick trim,
starp diviem un pieciem.

49
00:02:25,440 --> 00:02:27,849
>> Seši ir nākamais nešķiroti
elements masīva.

50
00:02:27,849 --> 00:02:31,140
Un faktiski seši ir lielāks par pieciem, lai
mums nav pat nepieciešams veikt nekādas pārnešana.

51
00:02:31,140 --> 00:02:35,710
Mēs varam tikai sadiegšana sešas tiesības uz
beigas sakārtoti porciju.

52
00:02:35,710 --> 00:02:38,270
>> Visbeidzot, četri ir
pēdējais nešķiroti elements.

53
00:02:38,270 --> 00:02:42,060
Tāpēc mēs noteikti to malā, novirzīt vairāk
elementi mums ir nepieciešams pāriet pāri,

54
00:02:42,060 --> 00:02:43,780
un pēc tam nodot četras kur tā pieder.

55
00:02:43,780 --> 00:02:46,400
Un tagad izskatās, mēs esam sava veida
no visiem elementiem.

56
00:02:46,400 --> 00:02:48,150
Ievērojiet ar ievietošanas
kārtot, mums nebija

57
00:02:48,150 --> 00:02:50,240
iet uz priekšu un atpakaļ pāri masīvs.

58
00:02:50,240 --> 00:02:54,720
Mēs tikai gāja pāri masīvs
vienu reizi, un mēs pārvietoti lietas

59
00:02:54,720 --> 00:02:59,870
ka mēs gribētu jau radušās, lai
lai atbrīvotu vietu jauniem elementiem.

60
00:02:59,870 --> 00:03:02,820
>> Tātad, kas ir sliktākais gadījums
scenārijs ar ievietošanas kārtošanas?

61
00:03:02,820 --> 00:03:05,090
Sliktākajā gadījumā
masīvs ir apgrieztā secībā.

62
00:03:05,090 --> 00:03:11,180
Jums ir novirzīt katru no n elementiem
līdz n pozīcijām, katru reizi, kad mēs

63
00:03:11,180 --> 00:03:12,880
veikt ievietošanu.

64
00:03:12,880 --> 00:03:15,720
Tas ir daudz novirzot.

65
00:03:15,720 --> 00:03:18,014
>> Labākajā gadījumā
masīvs ir perfekti sakārtots.

66
00:03:18,014 --> 00:03:20,680
Un veida, piemēram, to, kas notika
ar pieciem un sešiem piemērā,

67
00:03:20,680 --> 00:03:23,779
kur mēs varētu vienkārši sadiegšana to
bez darīt jebkuru pārnesi,

68
00:03:23,779 --> 00:03:24,820
mēs gribētu būtībā darīt.

69
00:03:24,820 --> 00:03:27,560
>> Ja jūs varat iedomāties, ka mūsu
masīvs bija viens pa sešiem,

70
00:03:27,560 --> 00:03:29,900
mēs gribētu sākt,
pasludina vienu, ir sakārtots.

71
00:03:29,900 --> 00:03:33,300
Divi nāk pēc viena tāpēc mēs varam tikai
teikt, OK, arī viens un divi ir sakārtoti.

72
00:03:33,300 --> 00:03:36,190
Trīs nāk pēc diviem tā, OK,
viens un divi, un trīs ir sakārtoti.

73
00:03:36,190 --> 00:03:39,590
>> Mēs esam ne nekādus mijmaiņas darījumus, mēs esam
tikai pārvietojas šo patvaļīgu līniju

74
00:03:39,590 --> 00:03:42,460
starp sašķiroti un šķirotas, kā mums iet.

75
00:03:42,460 --> 00:03:46,646
Tikpat efektīvi kā mēs to darījām piemērā,
pagriežot elementus zils, kā mēs turpināt.

76
00:03:46,646 --> 00:03:48,270
Tātad, kas ir sliktākajā gadījumā runtime, tad?

77
00:03:48,270 --> 00:03:51,854
Atcerieties, ja mums ir novirzīt katru no
tad n elementus iespējams n pozīcijas,

78
00:03:51,854 --> 00:03:54,020
cerams, ka dod jums
ideja, ka sliktākajā gadījumā

79
00:03:54,020 --> 00:03:57,770
runtime ir Big O n brusas.

80
00:03:57,770 --> 00:04:00,220
>> Ja masīvs ir pilnīgi
sakārtots, viss, kas mums ir jādara

81
00:04:00,220 --> 00:04:04,480
ir apskatīt katru elementu
vienreiz, un tad mēs esam darījuši.

82
00:04:04,480 --> 00:04:08,440
Tātad labākajā gadījumā, tas ir omega n.

83
00:04:08,440 --> 00:04:09,490
>> Es esmu Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Tas ir CS50.

85
00:04:11,760 --> 00:04:13,119