1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Idemo pogledati odabira vrste, algoritam

2
00:00:09,980 --> 00:00:12,800
za uzimanje popis brojeva te ih sortirati.

3
00:00:12,800 --> 00:00:15,750
Algoritam, zapamtite, je jednostavno korak-po-korak

4
00:00:15,750 --> 00:00:18,370
Postupak za ostvarivanje zadatka.

5
00:00:18,370 --> 00:00:21,470
Osnovna ideja iza odabira vrste je podijeliti

6
00:00:21,470 --> 00:00:23,390
naš popis na dva dijela -

7
00:00:23,390 --> 00:00:26,810
sortirani dio i nerazvrstani dio.

8
00:00:26,810 --> 00:00:30,200
Na svakom koraku algoritma, broj je premještena iz

9
00:00:30,200 --> 00:00:33,800
nerazvrstani dio na razvrstanog dijela dok na kraju

10
00:00:33,800 --> 00:00:35,880
Cijeli popis sortiran.

11
00:00:35,880 --> 00:00:38,510
Dakle, ovdje je popis od šest brojeva -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, i 15.

13
00:00:44,010 --> 00:00:47,680
Upravo sada je cijela lista smatra nesortirani.

14
00:00:47,680 --> 00:00:51,770
Iako broj kao 16 svibanj već biti u svom točne

15
00:00:51,770 --> 00:00:56,040
lokacija, naš algoritam nema načina znajući da do

16
00:00:56,040 --> 00:00:57,980
Cijeli popis sortiran.

17
00:00:57,980 --> 00:01:01,355
Dakle, mi ćemo razmotriti svaki broj koji će se nesortirani dok smo sortirati

18
00:01:01,355 --> 00:01:03,800
to mi sami.

19
00:01:03,800 --> 00:01:06,890
Znamo da želimo da popis bude u uzlaznom redoslijedu.

20
00:01:06,890 --> 00:01:10,200
Tako da ćete želite izgraditi sortirani dio našeg popisa

21
00:01:10,200 --> 00:01:13,280
s lijeva na desno, najmanji na najveći.

22
00:01:13,280 --> 00:01:17,970
Da bi to učinili, morat ćemo pronaći minimalnu Unsorted elementa

23
00:01:17,970 --> 00:01:21,350
i staviti na kraju poredani dijela.

24
00:01:21,350 --> 00:01:25,370
Budući da je ovaj popis nije sortiran, jedini način da to učinite je da

25
00:01:25,370 --> 00:01:29,330
pogledati svaki element u nerazvrstani dijela, prisjećajući

26
00:01:29,330 --> 00:01:32,010
element koji je najniži i usporedbom

27
00:01:32,010 --> 00:01:33,770
svaki element na to.

28
00:01:33,770 --> 00:01:36,150
Tako smo prvo ćete pogledati 23.

29
00:01:36,150 --> 00:01:38,650
Ovo je prvi element smo vidjeli, pa ćemo se sjetiti

30
00:01:38,650 --> 00:01:40,050
to je kao minimum.

31
00:01:40,050 --> 00:01:42,320
Sljedeća ćemo pogledati 42.

32
00:01:42,320 --> 00:01:46,720
42 je veći od 23, pa 23 je još uvijek minimalna.

33
00:01:46,720 --> 00:01:51,210
Sljedeća je četiri, što je manje od 23, pa ćemo se sjetiti 4

34
00:01:51,210 --> 00:01:52,880
kao novi minimum.

35
00:01:52,880 --> 00:01:56,380
Sljedeća je 16 koji je veći od 4, SO 4

36
00:01:56,380 --> 00:01:57,980
još uvijek je minimalna.

37
00:01:57,980 --> 00:02:03,670
8 je veći od 4, a 15 je veći od 4, tako da 4 mora biti

38
00:02:03,670 --> 00:02:05,980
Najmanji nerazvrstani element.

39
00:02:05,980 --> 00:02:09,350
Dakle, iako kao ljudi možemo odmah vidjeti da je četiri

40
00:02:09,350 --> 00:02:12,300
minimalni element, naš algoritam treba pogledati

41
00:02:12,300 --> 00:02:15,710
svaki nerazvrstani element, čak i nakon što smo našli 4 -

42
00:02:15,710 --> 00:02:16,860
minimalni element.

43
00:02:16,860 --> 00:02:19,900
Tako da sada smo pronašli minimalni element, 4, mi ćemo htjeti

44
00:02:19,900 --> 00:02:23,410
ga premjestiti u sortirani dio popisa.

45
00:02:23,410 --> 00:02:27,320
Budući da je ovo prvi korak, to znači da želimo staviti na 4

46
00:02:27,320 --> 00:02:29,680
početak popisa.

47
00:02:29,680 --> 00:02:33,040
Trenutno 23 je na početku popisa, tako

48
00:02:33,040 --> 00:02:36,080
ajmo zamijeniti 4 i 23.

49
00:02:36,080 --> 00:02:38,870
Dakle, sada naš popis izgleda ovako.

50
00:02:38,870 --> 00:02:42,710
Mi znamo da je 4 moraju biti u svojoj konačnoj lokaciji, jer je to

51
00:02:42,710 --> 00:02:45,890
i najmanji element i element na početku

52
00:02:45,890 --> 00:02:46,960
popisa.

53
00:02:46,960 --> 00:02:50,650
Dakle, to znači da mi ne zatreba da ga ponovno pokrene.

54
00:02:50,650 --> 00:02:53,910
Tako ćemo ponoviti ovaj postupak za dodavanje drugog elementa na

55
00:02:53,910 --> 00:02:55,910
sortirani dio popisa.

56
00:02:55,910 --> 00:02:58,950
Mi znamo da ne trebamo gledati na 4, jer je

57
00:02:58,950 --> 00:03:00,000
već riješeno.

58
00:03:00,000 --> 00:03:03,540
Dakle, možemo početi na 42, što ćemo se sjetiti kako se

59
00:03:03,540 --> 00:03:05,290
minimalni element.

60
00:03:05,290 --> 00:03:08,700
Dakle, sljedeći ćemo gledati na 23 što je manje od 42, pa smo

61
00:03:08,700 --> 00:03:11,620
sjećam 23 je novi minimalno.

62
00:03:11,620 --> 00:03:14,870
Zatim smo vidjeli 16 što je manje od 23, pa

63
00:03:14,870 --> 00:03:16,800
16 je novi minimalno.

64
00:03:16,800 --> 00:03:19,720
Sada gledamo 8 što je manje od 16, pa

65
00:03:19,720 --> 00:03:21,130
8 je nova minimalna.

66
00:03:21,130 --> 00:03:25,900
I na kraju 8 je manje od 15, tako da smo znali da je osam minimalna

67
00:03:25,900 --> 00:03:27,780
nerazvrstani element.

68
00:03:27,780 --> 00:03:30,660
Dakle, to znači da bismo trebali dodati 8 do razvrstani

69
00:03:30,660 --> 00:03:32,450
dio popisa.

70
00:03:32,450 --> 00:03:35,990
Upravo sada 4 je samo razvrstani element, tako želimo staviti

71
00:03:35,990 --> 00:03:38,410
8 pored 4.

72
00:03:38,410 --> 00:03:41,920
Budući 42 prvi element u nerazvrstani dijela od

73
00:03:41,920 --> 00:03:47,260
Popis ćemo žele zamijeniti 42 i 8.

74
00:03:47,260 --> 00:03:49,680
Dakle, sada naš popis izgleda ovako.

75
00:03:49,680 --> 00:03:53,830
4 i 8 predstavljaju sortirani dio popisa i

76
00:03:53,830 --> 00:03:56,440
Preostali brojevi predstavljaju nerazvrstani

77
00:03:56,440 --> 00:03:58,260
dio popisa.

78
00:03:58,260 --> 00:04:00,630
Tako ćemo nastaviti s drugom iteraciji.

79
00:04:00,630 --> 00:04:03,850
Mi smo započeli sa 23 ovaj put, jer mi ne treba gledati na

80
00:04:03,850 --> 00:04:05,770
je 4 i 8 više, jer oni '

81
00:04:05,770 --> 00:04:07,660
već riješeno.

82
00:04:07,660 --> 00:04:10,270
16 je manje od 23, pa ćemo se sjetiti

83
00:04:10,270 --> 00:04:12,070
16 kao novi minimum.

84
00:04:12,070 --> 00:04:18,149
16 je manji od 42, ali 15 je manje od 16, pa 15 moraju biti

85
00:04:18,149 --> 00:04:20,480
Minimalna nerazvrstani element.

86
00:04:20,480 --> 00:04:24,580
Dakle, sada želimo zamijeniti 15 i 23 na

87
00:04:24,580 --> 00:04:26,310
dajte nam taj popis.

88
00:04:26,310 --> 00:04:30,500
The sortirani dio popisa se sastoji od 4, 8 i 15, a

89
00:04:30,500 --> 00:04:33,210
ti elementi još uvijek nesortirani.

90
00:04:33,210 --> 00:04:36,900
No, to samo tako dogodi da sljedeći nerazvrstani element, 16,

91
00:04:36,900 --> 00:04:38,480
je već riješeno.

92
00:04:38,480 --> 00:04:42,060
Međutim, ne postoji način za našeg algoritma znati da 16

93
00:04:42,060 --> 00:04:45,230
je već u svom pravom mjestu, tako da smo još uvijek trebaju

94
00:04:45,230 --> 00:04:47,870
ponoviti točno na isti proces.

95
00:04:47,870 --> 00:04:53,750
Dakle vidimo da se 16 je manje od 42, a 16 je manji od 23, pa

96
00:04:53,750 --> 00:04:56,230
16 mora biti minimalno element.

97
00:04:56,230 --> 00:04:59,010
To je nemoguće zamijeniti taj element sa sobom, pa možemo

98
00:04:59,010 --> 00:05:01,780
jednostavno ostaviti ga u tom položaju.

99
00:05:01,780 --> 00:05:04,660
Dakle, trebamo jedan više loptu u naš algoritam.

100
00:05:04,660 --> 00:05:09,370
42 veći od 23, tako da 23 mora biti

101
00:05:09,370 --> 00:05:10,970
Minimalna nerazvrstani element.

102
00:05:10,970 --> 00:05:17,410
Nakon što smo zamijenili 23 i 42, mi završiti s naša konačna

103
00:05:17,410 --> 00:05:18,530
razvrstani popis -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Mi znamo 42 moraju biti u ispravnom mjestu, budući da je

106
00:05:26,830 --> 00:05:30,210
Jedini element lijevo, te da je izbor vrsta.

107
00:05:30,210 --> 00:05:32,100
Idemo sada formalizirati naše algoritam s nekim

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
Na liniji jedan, možemo vidjeti da trebamo integrirati više

110
00:05:37,760 --> 00:05:39,530
svaki element popisa.

111
00:05:39,530 --> 00:05:42,150
Osim posljednjeg elementa, budući da je jedan element koji

112
00:05:42,150 --> 00:05:44,230
Popis je već riješeno.

113
00:05:44,230 --> 00:05:48,100
Na liniji dva, smatramo da je prvi element nerazvrstani

114
00:05:48,100 --> 00:05:51,080
dio popisa biti minimalna, kao što smo učinili s našim

115
00:05:51,080 --> 00:05:53,750
Na primjer, tako da imamo nešto za usporediti.

116
00:05:53,750 --> 00:05:57,260
Linija tri započinje drugi petlju u kojoj smo ponoviti više

117
00:05:57,260 --> 00:05:59,170
svaki nerazvrstani element.

118
00:05:59,170 --> 00:06:02,150
Mi znamo da je nakon što sam iteracija je izdvojiti dio

119
00:06:02,150 --> 00:06:05,330
našeg popisa mora sam elementi u njemu od svakog koraka

120
00:06:05,330 --> 00:06:06,890
vrste jedan element.

121
00:06:06,890 --> 00:06:11,770
Dakle, prvi nerazvrstani element mora biti u poziciji i plus jedan.

122
00:06:11,770 --> 00:06:15,440
Na liniji četiri, možemo usporediti trenutni element na minimum

123
00:06:15,440 --> 00:06:17,750
element koji smo do sada vidjeli.

124
00:06:17,750 --> 00:06:20,560
Ako je trenutna element manji od minimuma

125
00:06:20,560 --> 00:06:23,870
element, onda ćemo se sjetiti trenutni element kao nova

126
00:06:23,870 --> 00:06:26,250
Minimalna na liniji pet.

127
00:06:26,250 --> 00:06:29,900
Konačno, na linijama šest i sedam, možemo zamijeniti minimalno

128
00:06:29,900 --> 00:06:33,080
element s prvom nerazvrstani elementa, čime

129
00:06:33,080 --> 00:06:36,990
dodavanjem na poredani dio popisa.

130
00:06:36,990 --> 00:06:40,030
Nakon što smo algoritam, važno pitanje koje treba postaviti

131
00:06:40,030 --> 00:06:43,370
sebe kao programera je koliko dugo se to uzeti?

132
00:06:43,370 --> 00:06:46,970
Mi smo prvi put ću postaviti pitanje koliko dugo to traje za to

133
00:06:46,970 --> 00:06:50,070
algoritam za rad u najgorem slučaju?

134
00:06:50,070 --> 00:06:51,640
Podsjetimo mi predstavljaju ovu trčanje

135
00:06:51,640 --> 00:06:55,060
put s velikom O notacijom.

136
00:06:55,060 --> 00:06:58,650
Da bi se utvrdilo minimalnu Unsorted element, mi

137
00:06:58,650 --> 00:07:01,880
bitno je usporediti svaki element u popisu na

138
00:07:01,880 --> 00:07:04,040
svaki drugi element u popisu.

139
00:07:04,040 --> 00:07:08,430
Intuitivno, ovo zvuči kao O n kvadrata radu.

140
00:07:08,430 --> 00:07:12,050
Gledajući naše pseudocode, mi također imaju petlju ugniježđena unutar

141
00:07:12,050 --> 00:07:14,420
drugi petlja, koja doista zvuči kao O

142
00:07:14,420 --> 00:07:16,480
n kvadrata radu.

143
00:07:16,480 --> 00:07:19,250
Međutim, zapamtite da mi ne treba gledati preko

144
00:07:19,250 --> 00:07:23,460
Cijeli popis prilikom utvrđivanja minimalne Unsorted elementa?

145
00:07:23,460 --> 00:07:26,600
Nakon što smo znali da je četiri godine izdvojiti, na primjer, nismo

146
00:07:26,600 --> 00:07:28,170
trebamo gledati na to opet.

147
00:07:28,170 --> 00:07:31,020
Znači li to niža trčanje vremena?

148
00:07:31,020 --> 00:07:34,510
Za naš popis duljine 6, morali smo napraviti pet

149
00:07:34,510 --> 00:07:37,990
usporedbe za prvi element, četiri usporedbe za

150
00:07:37,990 --> 00:07:40,750
Drugi element, i tako dalje.

151
00:07:40,750 --> 00:07:44,690
To znači da je ukupan broj koraka je zbroj

152
00:07:44,690 --> 00:07:49,160
integers od 1 na duljinu popisa minus 1.

153
00:07:49,160 --> 00:07:51,005
Mi može predstavljati to sa zbrajanjem.

154
00:07:57,980 --> 00:07:59,910
Nećemo ići u summations ovdje.

155
00:07:59,910 --> 00:08:04,900
No, ispostavilo se da je to zbir jednak n puta

156
00:08:04,900 --> 00:08:07,540
n minus 1 preko 2.

157
00:08:07,540 --> 00:08:14,220
Ili ravnopravno, n kvadrat preko dva minus n preko dvije.

158
00:08:14,220 --> 00:08:18,860
Kada govorimo o asimptotska izvođenja, to n kvadratna izraz

159
00:08:18,860 --> 00:08:22,070
će dominirati ovaj n pojam.

160
00:08:22,070 --> 00:08:27,850
Dakle, odabir vrsta je O od n na kvadrat.

161
00:08:27,850 --> 00:08:31,460
Podsjetimo da je u našem primjeru, odabrana vrsta još uvijek potrebna za

162
00:08:31,460 --> 00:08:33,850
provjerite je li broj koji je već razvrstani

163
00:08:33,850 --> 00:08:35,450
potrebna kako bi se preselio.

164
00:08:35,450 --> 00:08:38,929
Dakle, to znači da ako smo trčali odabira vrste preko već

165
00:08:38,929 --> 00:08:43,070
razvrstani popis, to će zahtijevati isti broj koraka kao što je

166
00:08:43,070 --> 00:08:46,340
bi kada se izvodi preko potpuno nerazvrstani popisu.

167
00:08:46,340 --> 00:08:51,470
Dakle, izbor vrsta ima najboljem slučaju izvedbe n kvadrata,

168
00:08:51,470 --> 00:08:56,820
koje predstavljaju omega n kvadrata.

169
00:08:56,820 --> 00:08:58,600
I to je to za izbor vrste.

170
00:08:58,600 --> 00:09:00,630
Samo jedan od mnogih algoritama možemo

171
00:09:00,630 --> 00:09:02,390
koristiti za sortiranje popisa.

172
00:09:02,390 --> 00:09:05,910
Moje ime je Tommy, a to je cs50.