1
00:00:00,000 --> 00:00:02,826
>> [Musiikkia]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG Lloyd: Niin lisäyslajittelun on toinen
algoritmi voimme käyttää järjestellä jono.

4
00:00:09,370 --> 00:00:12,350
Ajatuksena algoritmi
on rakentaa lajitellut array

5
00:00:12,350 --> 00:00:19,670
paikallaan, siirtää elementtejä ulos
Muuten kuten mennä, tehdä tilaa.

6
00:00:19,670 --> 00:00:22,240
Tämä on hieman erilainen
valinnasta lajitella tai kupla

7
00:00:22,240 --> 00:00:25,460
lajitella, esimerkiksi silloin, kun
olemme säätämällä paikoissa,

8
00:00:25,460 --> 00:00:26,910
jossa Teemme swap.

9
00:00:26,910 --> 00:00:29,760
>> Tässä tapauksessa, mitä olemme todella
teet on liukuelementit

10
00:00:29,760 --> 00:00:31,390
yli, pois tieltä.

11
00:00:31,390 --> 00:00:34,030
Miten tämä algoritmi
työskennellä pseudokoodilla?

12
00:00:34,030 --> 00:00:37,646
No sanotaan nyt mielivaltaisesti sanoa, että
ensimmäinen alkiota lajitellaan.

13
00:00:37,646 --> 00:00:38,770
Me rakennamme sitä paikallaan.

14
00:00:38,770 --> 00:00:42,660
>> Aiomme mennä yksi osa kerrallaan ja
rakentaa, ja niin ensimmäinen asia näemme

15
00:00:42,660 --> 00:00:43,890
on yksi elementti array.

16
00:00:43,890 --> 00:00:47,720
Ja määritelmän, yksi
alkiotaulukko lajitellaan.

17
00:00:47,720 --> 00:00:50,850
>> Sitten me toista tämä prosessi until--
me toista seuraavista prosessin

18
00:00:50,850 --> 00:00:52,900
kunnes kaikki elementit lajitellaan.

19
00:00:52,900 --> 00:00:57,770
Katso seuraava lajittelemattoman elementti ja
aseta se lajitellut osaan,

20
00:00:57,770 --> 00:01:01,209
siirtämällä tarvittava määrä
elementtien pois tieltä.

21
00:01:01,209 --> 00:01:03,750
Toivottavasti tämä visualisointi
auttaa sinua nähdä, mitä on

22
00:01:03,750 --> 00:01:05,980
meneillään kanssa lisäyslajittelun.

23
00:01:05,980 --> 00:01:08,010
>> Joten jälleen, tässä on meidän
koko lajittelemattomat array,

24
00:01:08,010 --> 00:01:10,970
kaikki elementit merkitty punaisella.

25
00:01:10,970 --> 00:01:13,320
Ja nyt seurata
vaiheet meidän pseudokoodin.

26
00:01:13,320 --> 00:01:16,970
Ensimmäinen asia teemme, on kutsumme
ensimmäinen alkiota, lajiteltu.

27
00:01:16,970 --> 00:01:20,920
Joten olemme vain aio sanoa
viisi, olet nyt lajitellaan.

28
00:01:20,920 --> 00:01:24,570
>> Sitten katsomme seuraavan
lajittelematon alkio

29
00:01:24,570 --> 00:01:27,610
ja haluamme lisätä, että
osaksi lajiteltu osaan,

30
00:01:27,610 --> 00:01:29,750
siirtämällä elementtien yli.

31
00:01:29,750 --> 00:01:33,470
Joten kaksi on seuraava lajittelematonta
alkiota.

32
00:01:33,470 --> 00:01:36,250
Selvästi se kuuluu ennen
viisi, joten mitä aiomme tehdä

33
00:01:36,250 --> 00:01:41,580
on tavallaan järjestää kaksi varattu toisen,
siirtää viisi yli, ja aseta kaksi

34
00:01:41,580 --> 00:01:43,210
ennen viisi, minne pitäisi mennä.

35
00:01:43,210 --> 00:01:45,280
Ja nyt voimme sanoa, että kaksi on lajiteltu.

36
00:01:45,280 --> 00:01:48,400
>> Joten kuten näette, olemme vain toistaiseksi
tarkasteli kahta elementtejä jono.

37
00:01:48,400 --> 00:01:50,600
Emme ole katsonut
levätä ollenkaan, mutta olemme

38
00:01:50,600 --> 00:01:54,582
mutta nämä kaksi elementtiä lajiteltu
tapa siirtyminen mekanismin.

39
00:01:54,582 --> 00:01:56,410
>> Joten me toista prosessi uudelleen.

40
00:01:56,410 --> 00:01:58,850
Katsokaa seuraava lajittelemattoman
elementti, se on yksi.

41
00:01:58,850 --> 00:02:04,010
Katsotaanpa katsonut, että syrjään toisen,
siirtää kaikki yli, ja laita yksi

42
00:02:04,010 --> 00:02:05,570
jos se pitäisi mennä.

43
00:02:05,570 --> 00:02:08,110
>> Jälleen edelleen, olemme aina vain
katsoi yksi, kaksi ja viisi.

44
00:02:08,110 --> 00:02:12,480
Emme tiedä mitä muuta on tulossa,
mutta olemme lajiteltu näistä kolmesta.

45
00:02:12,480 --> 00:02:16,030
>> Seuraava lajittelemattomat elementti on
kolme, joten me aseta se sivuun.

46
00:02:16,030 --> 00:02:18,200
Me siirtää, mitä me
täytyy joka tällä kertaa

47
00:02:18,200 --> 00:02:21,820
ei ole kaikki kuten edellisessä
kaksi tapausta, se on vain viisi.

48
00:02:21,820 --> 00:02:25,440
Ja sitten me kiinni kolme,
kahden ja viiden.

49
00:02:25,440 --> 00:02:27,849
>> Kuusi on seuraava lajittelematonta
elementti array.

50
00:02:27,849 --> 00:02:31,140
Ja itse asiassa kuusi on suurempi kuin viisi, joten
emme edes tarvitse tehdä mitään vaihtamista.

51
00:02:31,140 --> 00:02:35,710
Voimme vain tack kuusi oikealle ja
loppuun järjestetty osan.

52
00:02:35,710 --> 00:02:38,270
>> Lopuksi neljä on
viime lajittelemattomat elementti.

53
00:02:38,270 --> 00:02:42,060
Niin me sen syrjään, siirtää yli
elementit meidän siirtää yli,

54
00:02:42,060 --> 00:02:43,780
ja sitten laittaa neljä minne se kuuluu.

55
00:02:43,780 --> 00:02:46,400
Ja nyt näyttää, olemme tavallaan
kaikki tekijät.

56
00:02:46,400 --> 00:02:48,150
Huomaa insertiovektorilla
lajitella, meillä ei ollut

57
00:02:48,150 --> 00:02:50,240
mennä edestakaisin jono.

58
00:02:50,240 --> 00:02:54,720
Me vain meni poikki array
kerran, ja muutimme asiat

59
00:02:54,720 --> 00:02:59,870
että olimme jo kohdanneet, jotta
tehdä tilaa uusia elementtejä.

60
00:02:59,870 --> 00:03:02,820
>> Niin mitä pahimmassa tapauksessa
skenaario kanssa lisäyslajittelun?

61
00:03:02,820 --> 00:03:05,090
Pahimmassa tapauksessa,
array on päinvastaisessa järjestyksessä.

62
00:03:05,090 --> 00:03:11,180
Sinun täytyy siirtää kunkin n elementtien
jopa n kantoja, joka ikinen kerta me

63
00:03:11,180 --> 00:03:12,880
tehdä lisäys.

64
00:03:12,880 --> 00:03:15,720
Se on paljon siirtää.

65
00:03:15,720 --> 00:03:18,014
>> Parhaassa tapauksessa
array on täydellisesti lajitellaan.

66
00:03:18,014 --> 00:03:20,680
Ja tavallaan kuin mitä tapahtui
viisi ja kuusi esimerkissä,

67
00:03:20,680 --> 00:03:23,779
jossa voisimme vain tack sen
ilman tehdä siirtyisi,

68
00:03:23,779 --> 00:03:24,820
olimme lähinnä tehdä.

69
00:03:24,820 --> 00:03:27,560
>> Jos kuvitella, että meidän
array oli yksi läpi kuusi,

70
00:03:27,560 --> 00:03:29,900
alkaisimme pois
julistamisesta yksi lajitellaan.

71
00:03:29,900 --> 00:03:33,300
Kaksi tulee yhden niin voimme vain
sanovat, OK, hyvin yksi ja kaksi lajitellaan.

72
00:03:33,300 --> 00:03:36,190
Kolme tulee sen jälkeen kaksi niin, OK,
yksi ja kaksi ja kolme lajitellaan.

73
00:03:36,190 --> 00:03:39,590
>> Emme teet mitään vaihtosopimukset, olemme
vain liikkuvat tämä mielivaltainen linja

74
00:03:39,590 --> 00:03:42,460
välillä lajitellaan ja lajittelemattomat menemme.

75
00:03:42,460 --> 00:03:46,646
Yhtä tehokkaasti kuin teimme esimerkissä,
Kääntöelimien sininen, kuten me edetä.

76
00:03:46,646 --> 00:03:48,270
Niin mitä pahimmassa tapauksessa runtime, sitten?

77
00:03:48,270 --> 00:03:51,854
Muista, jos meillä on siirtää kunkin
n elementit mahdollisesti n kantoja,

78
00:03:51,854 --> 00:03:54,020
toivottavasti, joka antaa sinulle
ajatus, että pahimmassa tapauksessa

79
00:03:54,020 --> 00:03:57,770
runtime on Big O n neliö.

80
00:03:57,770 --> 00:04:00,220
>> Jos matriisi on täysin
lajiteltu, kaikki meidän on tehtävä

81
00:04:00,220 --> 00:04:04,480
on tarkastella jokaisen elementin
kerran, ja sitten olemme tehneet.

82
00:04:04,480 --> 00:04:08,440
Joten parhaassa tapauksessa, se on omega n.

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

84
00:04:09,490 --> 00:04:11,760
Tämä on CS50.

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