1
00:00:00,000 --> 00:00:02,826
>> [MUZIKO Ludante]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Do inserción varo estas alia
algoritmo ni povas uzi por ordigi tabelo.

4
00:00:09,370 --> 00:00:12,350
La ideo malantaŭ ĉi tiu algoritmo
estas konstrui vian ordo tabelo

5
00:00:12,350 --> 00:00:19,670
en lokon, movanta elementoj el
la maniero kiel vi iros, por fari lokon.

6
00:00:19,670 --> 00:00:22,240
Jen iomete malsama
el selektado varo aŭ bobelo

7
00:00:22,240 --> 00:00:25,460
speco, ekzemple, kie
ni modifu la lokoj,

8
00:00:25,460 --> 00:00:26,910
kie ni fari svopoj.

9
00:00:26,910 --> 00:00:29,760
>> En tiu kazo, kion ni vere
faras estas glitante elementoj

10
00:00:29,760 --> 00:00:31,390
super, de la vojo.

11
00:00:31,390 --> 00:00:34,030
Kiel funkcias tiu algoritmo
labori en _pseudocode_?

12
00:00:34,030 --> 00:00:37,646
Nu ni nur arbitre diras ke la
unua elemento de la tabelo estas ordigita.

13
00:00:37,646 --> 00:00:38,770
Ni konstruis ĝin en loko.

14
00:00:38,770 --> 00:00:42,660
>> Ni gonna iri unu elementon je fojo kaj
konstrui ĝin, kaj tiel ni unue vidu

15
00:00:42,660 --> 00:00:43,890
Estas unu elemento tabelo.

16
00:00:43,890 --> 00:00:47,720
Kaj per difino, unu
elemento tabelo estas ordigita.

17
00:00:47,720 --> 00:00:50,850
>> Tiam ni ripetas ĉi procezo until--
ni ripetas la sekva procezo

18
00:00:50,850 --> 00:00:52,900
ĝis ĉiuj de la elementoj estas ordo.

19
00:00:52,900 --> 00:00:57,770
Rigardu la sekva unsorted elemento kaj
enmeti ĝin en la ordo parton,

20
00:00:57,770 --> 00:01:01,209
per sxangxigxantaj la postulata nombro
de elementoj de la vojo.

21
00:01:01,209 --> 00:01:03,750
Espereble ĉi videbligo
helpos vin vidi ekzakte kio estas

22
00:01:03,750 --> 00:01:05,980
daŭriganta kun inserción varon.

23
00:01:05,980 --> 00:01:08,010
>> Do denove, jen nia
tuta unsorted tabelo,

24
00:01:08,010 --> 00:01:10,970
ĉiuj elementoj indikitaj en ruĝa.

25
00:01:10,970 --> 00:01:13,320
Kaj ni sekvas la
paŝojn de niaj _pseudocode_.

26
00:01:13,320 --> 00:01:16,970
La unua aĵo kiun ni faras, estas ni nomas la
unua ero de la tabelo, ordigitaj.

27
00:01:16,970 --> 00:01:20,920
Do ni estas nur gonna diru
kvin, vi nun ordo.

28
00:01:20,920 --> 00:01:24,570
>> Tiam ni rigardas la sekva
unsorted elemento de la tabelo

29
00:01:24,570 --> 00:01:27,610
kaj ni volas enmeti ke
en la ordo parton,

30
00:01:27,610 --> 00:01:29,750
per sxangxigxantaj elementoj super.

31
00:01:29,750 --> 00:01:33,470
Do du estas la sekva unsorted
elemento de la tabelo.

32
00:01:33,470 --> 00:01:36,250
Klare ĝi apartenas antaŭ la
kvin, do kio ni estas gonna do

33
00:01:36,250 --> 00:01:41,580
estas ia teni du flanken por dua,
ŝanĝi kvin super, kaj tiam enmeti du

34
00:01:41,580 --> 00:01:43,210
antaŭ kvin, kie devus iri.

35
00:01:43,210 --> 00:01:45,280
Kaj nun ni povas diri ke du estas ordo.

36
00:01:45,280 --> 00:01:48,400
>> Do kiel vi povas vidi, ni nur ĝis nun
rigardis du elementoj de la tabelo.

37
00:01:48,400 --> 00:01:50,600
Ni ne rigardis la
ripozi tute, sed ni

38
00:01:50,600 --> 00:01:54,582
got tiuj du elementoj ordo laŭ
vojo de la movanta mekanismo.

39
00:01:54,582 --> 00:01:56,410
>> Do ni ripeti la procezon denove.

40
00:01:56,410 --> 00:01:58,850
Rigardu la sekva unsorted
elemento, tio estas unu.

41
00:01:58,850 --> 00:02:04,010
Ni tenu kiu apartigas por dua,
ŝanĝi ĉiu, de li unu

42
00:02:04,010 --> 00:02:05,570
kie devus iri.

43
00:02:05,570 --> 00:02:08,110
>> Denove, ankoraŭ, ni nur iam
rigardis unu, du kaj kvin.

44
00:02:08,110 --> 00:02:12,480
Ni ne scias kion alian Venas
sed ni ordigitaj tiuj tri elementoj.

45
00:02:12,480 --> 00:02:16,030
>> Sekva unsorted elemento estas
tri, do ni starigis ĝin flanken.

46
00:02:16,030 --> 00:02:18,200
Ni movi sur kion ni
bezonas kiu, ĉi tiu fojo

47
00:02:18,200 --> 00:02:21,820
ne ĉiu kiel en la antaŭa
du kazoj, estas nur kvin.

48
00:02:21,820 --> 00:02:25,440
Kaj poste ni algluita tri en,
inter la du kaj kvin.

49
00:02:25,440 --> 00:02:27,849
>> Ses estas la sekva unsorted
elemento al la tabelo.

50
00:02:27,849 --> 00:02:31,140
Kaj fakte ses estas pli granda ol kvin, do
ni eĉ ne bezonas fari neniun swapping.

51
00:02:31,140 --> 00:02:35,710
Ni povas nur najlu ses rekte al
la fino de la ordo parton.

52
00:02:35,710 --> 00:02:38,270
>> Finfine, kvar estas la
lasta unsorted elemento.

53
00:02:38,270 --> 00:02:42,060
Do ni starigis ĝin flanken, movi super
la elementoj ni bezonas movi super,

54
00:02:42,060 --> 00:02:43,780
kaj tiam metis kvar kie apartenas.

55
00:02:43,780 --> 00:02:46,400
Kaj nun rigardu, ni ia
de ĉiuj elementoj.

56
00:02:46,400 --> 00:02:48,150
Rimarku kun inserción
varon, ni ne havis

57
00:02:48,150 --> 00:02:50,240
iri tien kaj reen sur la tabelo.

58
00:02:50,240 --> 00:02:54,720
Ni nur iris trans la tabelo
unu fojon, kaj ni ŝanĝiĝis aferoj

59
00:02:54,720 --> 00:02:59,870
ke ni estus jam renkontis, por
por fari lokon por la novaj elementoj.

60
00:02:59,870 --> 00:03:02,820
>> Do kio estas la plej malbona kazo
scenaro kun inserción varo?

61
00:03:02,820 --> 00:03:05,090
En la plej malbona kazo, la
tabelo estas en inversa ordo.

62
00:03:05,090 --> 00:03:11,180
Vi devas ŝanĝi ĉiun de la n elementoj
ĝis n pozicioj, ĉiu ununura tempo ni

63
00:03:11,180 --> 00:03:12,880
fari inserción.

64
00:03:12,880 --> 00:03:15,720
Ke estas multa ŝanĝado.

65
00:03:15,720 --> 00:03:18,014
>> En la plej bona kazo, la
tabelo estas perfekte ordigita.

66
00:03:18,014 --> 00:03:20,680
Kaj ia kiel kio okazis
kun kvin kaj ses en la ekzemplo,

67
00:03:20,680 --> 00:03:23,779
kie ni povus simple najlu gxin sur
sen devi fari ajnan vagantaj

68
00:03:23,779 --> 00:03:24,820
ni estus esence fari tion.

69
00:03:24,820 --> 00:03:27,560
>> Se vi imagas, ke nia
tabelo estis unu tra ses,

70
00:03:27,560 --> 00:03:29,900
ni volas dividi per
deklarante unu estas ordo.

71
00:03:29,900 --> 00:03:33,300
Du venas post unu do ni povas nur
diri, OK, bone unu kaj du estas ordo.

72
00:03:33,300 --> 00:03:36,190
Tri venas post du tiel, okej,
unu kaj du kaj tri estas ordo.

73
00:03:36,190 --> 00:03:39,590
>> Ni ne farante ajnan svopoj, ni estas
nur movanta ĉi arbitra linio

74
00:03:39,590 --> 00:03:42,460
inter ordo kaj unsorted kiel ni iru.

75
00:03:42,460 --> 00:03:46,646
Kiel efike kiel ni faris en la ekzemplo,
turnante elementoj blua, kiel ni procedas.

76
00:03:46,646 --> 00:03:48,270
Do kio estas la plej malbona kazo tempo de ekzekuto, tiam?

77
00:03:48,270 --> 00:03:51,854
Memoru, se ni devas deloki ĉiu el
la n elementoj eble n pozicioj,

78
00:03:51,854 --> 00:03:54,020
espereble ke donas vin
ideon, ke la plej malbona kazo

79
00:03:54,020 --> 00:03:57,770
ekzekuto estas Granda a de n kvadratoj.

80
00:03:57,770 --> 00:04:00,220
>> Se la tabelo estas perfekte
ordo, ĉiuj ni devas fari

81
00:04:00,220 --> 00:04:04,480
estas rigardi ĉiu ununura ero
fojon, kaj poste ni faris.

82
00:04:04,480 --> 00:04:08,440
Do en la plej bona kazo, ĝi estas omega de n.

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

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

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