1
00:00:00,000 --> 00:00:05,726
>> [Musiikkia]

2
00:00:05,726 --> 00:00:08,600
DOUG Lloyd: Valinta sort on
algoritmi, joka, kuten arvata saattaa,

3
00:00:08,600 --> 00:00:10,470
lajittelee joukon elementtejä.

4
00:00:10,470 --> 00:00:12,470
Ja algoritmi Recall
on askel-askeleelta sarja

5
00:00:12,470 --> 00:00:15,260
ohjeisto valmiiksi tehtävän.

6
00:00:15,260 --> 00:00:17,580
>> Valinnassa lajitella
Perusidea on tämä,

7
00:00:17,580 --> 00:00:22,080
löytää pienin lajittelemattoman elementti ja
lisätä sen loppuun lajitellun luettelon.

8
00:00:22,080 --> 00:00:26,970
Tehokkaasti Mitä tämä on rakentaa
lajiteltu lista, yksi osa kerrallaan.

9
00:00:26,970 --> 00:00:29,800
Rikkomatta alas pseudokoodina
voisimme todeta tämä algoritmi

10
00:00:29,800 --> 00:00:34,490
seuraavasti, toista tämä kunnes
ei lajittelemattoman elementtejä edelleen.

11
00:00:34,490 --> 00:00:38,660
Hae seuraavien lajittelemattoman
tiedot löytää pienimmän arvon,

12
00:00:38,660 --> 00:00:44,130
sitten vaihtaa pienimmän arvon kanssa
ensimmäinen osa lajittelemattoman osan.

13
00:00:44,130 --> 00:00:47,130
>> Se voi auttaa visualisoida,
joten katsotaanpa katsomaan tätä.

14
00:00:47,130 --> 00:00:49,710
Joten tämä, väitän, on
lajittelemattomat array ja olen

15
00:00:49,710 --> 00:00:53,040
ilmoittanut ilmoittamalla, että kaikki
Elementtien ovat värillisiä punainen,

16
00:00:53,040 --> 00:00:54,420
ne eivät ole vielä järjestetty.

17
00:00:54,420 --> 00:00:57,670
Tämä on koko
lajittelematon osa array.

18
00:00:57,670 --> 00:01:02,020
>> Joten mennään läpi vaiheet
valinta lajitella lajitella tähän array.

19
00:01:02,020 --> 00:01:05,296
Joten jälleen, aiomme toistaa
kunnes ei lajittelemattoman elementtejä edelleen.

20
00:01:05,296 --> 00:01:07,920
Aiomme haku kautta
tiedot löytää pienimmän arvon,

21
00:01:07,920 --> 00:01:11,990
ja sitten vaihtaa tämän arvon kanssa
ensimmäinen osa lajittelemattoman osan.

22
00:01:11,990 --> 00:01:14,380
>> Juuri nyt, jälleen, koko
array on lajittelemattomana osa.

23
00:01:14,380 --> 00:01:16,534
Kaikki punaiset elementit lajittelemattomia.

24
00:01:16,534 --> 00:01:18,700
Joten me etsiä ja
löydämme pienimmän arvon.

25
00:01:18,700 --> 00:01:20,533
Aloitamme alussa,
menemme loppuun,

26
00:01:20,533 --> 00:01:23,630
löydämme pienin arvo on, yksi.

27
00:01:23,630 --> 00:01:24,860
Niin, että on osa yksi.

28
00:01:24,860 --> 00:01:29,440
Ja sitten osa kaksi, vaihtaa että arvoa
ensimmäinen osa lajittelemattoman osan,

29
00:01:29,440 --> 00:01:31,340
tai ensimmäinen punainen elementti.

30
00:01:31,340 --> 00:01:34,980
>> Tässä tapauksessa se olisi
viisi, joten me vaihtaa yhdestä viiteen.

31
00:01:34,980 --> 00:01:37,320
Kun teemme tämän, voimme
visuaalisesti nähdä, että olemme

32
00:01:37,320 --> 00:01:41,260
muutti pienin arvostettu elementti
array, jotta alusta.

33
00:01:41,260 --> 00:01:43,920
Tehokkaasti lajittelu että elementti.

34
00:01:43,920 --> 00:01:47,520
>> Ja jotta voimme todellakin vahvistaa
ja toteavat, että yksi, lajitellaan.

35
00:01:47,520 --> 00:01:52,080
Ja niin me osoittavat lajiteltu osa
meidän array, värjäämällä se sininen.

36
00:01:52,080 --> 00:01:53,860
>> Nyt vain toista prosessi uudelleen.

37
00:01:53,860 --> 00:01:57,430
Me etsiä lajittelemattomat osa
array löytää pienin alkio.

38
00:01:57,430 --> 00:01:59,000
Tässä tapauksessa se on kaksi.

39
00:01:59,000 --> 00:02:02,100
>> Me vaihtaa että ensimmäisen
elementti lajittelemattoman osan.

40
00:02:02,100 --> 00:02:05,540
Tässä tapauksessa kaksi myös sattuu olemaan
ensimmäinen osa lajittelemattoman osan.

41
00:02:05,540 --> 00:02:08,650
Joten me vaihtaa kaksi itsensä kanssa,
joka oikeastaan ​​vain lähtee kaksi

42
00:02:08,650 --> 00:02:11,257
missä se on, ja se on järjestetty.

43
00:02:11,257 --> 00:02:13,840
Jatkuu, me etsiä
löytää pienin alkio.

44
00:02:13,840 --> 00:02:15,030
Se on kolme.

45
00:02:15,030 --> 00:02:17,650
Me vaihtaa sen ensimmäisen
elementti, joka on viisi.

46
00:02:17,650 --> 00:02:19,450
Ja nyt kolme lajitellaan.

47
00:02:19,450 --> 00:02:22,440
>> Me etsimme kautta uudelleen, ja me
löytää pienin elementti on neljä.

48
00:02:22,440 --> 00:02:28,070
Me vaihtaa sen ensimmäinen osa
lajittelematonta osittain, ja nyt neljä lajitellaan.

49
00:02:28,070 --> 00:02:29,910
>> Huomaamme, että viisi on
pienin elementti.

50
00:02:29,910 --> 00:02:32,900
Me vaihtaa sen ensimmäisen
elementti lajittelemattoman osan.

51
00:02:32,900 --> 00:02:34,740
Ja nyt viisi lajitellaan.

52
00:02:34,740 --> 00:02:36,660
>> Ja sitten lopuksi, meidän
lajittelemattomat osa koostuu

53
00:02:36,660 --> 00:02:38,576
vain yksi elementti,
joten me etsiä

54
00:02:38,576 --> 00:02:41,740
ja huomaamme, että kuusi on
pienin, ja itse asiassa ainoa elementti.

55
00:02:41,740 --> 00:02:44,906
Ja sitten voimme todeta, että se on järjestetty.

56
00:02:44,906 --> 00:02:47,530
Ja nyt olemme siirtynyt meidän array
olemasta täysin lajittelematta

57
00:02:47,530 --> 00:02:52,660
punainen, täysin lajiteltu
sininen, käyttäen valinta lajitella.

58
00:02:52,660 --> 00:02:54,920
>> Niin mitä pahimmassa tapauksessa täällä?

59
00:02:54,920 --> 00:02:57,830
Hyvin ehdoton pahin
tapauksessa, meidän on katsottava yli

60
00:02:57,830 --> 00:03:02,170
kaikki elementit array
löytää pienin lajittelemattoman elementti,

61
00:03:02,170 --> 00:03:04,750
ja meidän on toistettava
tämä prosessi n kertaa.

62
00:03:04,750 --> 00:03:09,090
Kerran kutakin alkiota
koska me vain tässä algoritmi,

63
00:03:09,090 --> 00:03:12,180
lajitella yksi elementti kerrallaan.

64
00:03:12,180 --> 00:03:13,595
>> Mikä on parhaassa tapauksessa?

65
00:03:13,595 --> 00:03:15,040
No se on täsmälleen sama, eikö?

66
00:03:15,040 --> 00:03:18,440
Meillä on todellakin vielä selata
jokainen alkio

67
00:03:18,440 --> 00:03:22,040
varmistaakseen, että se on,
Itse asiassa, pienin elementti.

68
00:03:22,040 --> 00:03:26,760
>> Joten pahimmassa tapauksessa runtime, me
joutua toistamaan prosessi n kertaa,

69
00:03:26,760 --> 00:03:28,960
kerran kutakin n elementtejä.

70
00:03:28,960 --> 00:03:31,940
Ja parhaassa tapauksessa,
meidän täytyy tehdä samoin.

71
00:03:31,940 --> 00:03:35,340
>> Joten ajattelu takaisin meidän
laskennallinen vaativuus työkalupakki,

72
00:03:35,340 --> 00:03:39,250
mitä luulet on pahin
tapauksessa runtime valintaan lajitella?

73
00:03:39,250 --> 00:03:41,840
Mitä luulet on paras
tapauksessa runtime valintaan lajitella?

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

75
00:03:44,760 --> 00:03:49,325
>> Arvasit Big O n potenssiin,
ja Big Omega n potenssiin?

76
00:03:49,325 --> 00:03:49,950
Olisit oikeassa.

77
00:03:49,950 --> 00:03:52,490
Ne ovat itse asiassa,
Pahimmassa tapauksessa ja parhaassa tapauksessa ajaa

78
00:03:52,490 --> 00:03:55,100
ajat, valinnan lajitella.

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

80
00:03:56,260 --> 00:03:58,600
Tämä on CS50.

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