1
00:00:00,000 --> 00:00:05,726
>> [Muzikos grojimo]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD atranka Rūšiuoti yra
algoritmas, kuris, kaip galima tikėtis,

3
00:00:08,600 --> 00:00:10,470
rūšiuoja iš elementų rinkinį.

4
00:00:10,470 --> 00:00:12,470
Ir algoritmas Prisiminkite
yra žingsnis po žingsnio rinkinys

5
00:00:12,470 --> 00:00:15,260
Nurodymų pildymo užduotį.

6
00:00:15,260 --> 00:00:17,580
>> Be atrankos rūšiuoti
Pagrindinė idėja yra tai,

7
00:00:17,580 --> 00:00:22,080
Raskite mažiausią nerūšiuotas elementą ir
įtraukti ją į išrūšiuotų sąrašo gale.

8
00:00:22,080 --> 00:00:26,970
Efektyviai Kas tai yra statyti
rūšiuotą sąrašas, vienas elementas, tuo pačiu metu.

9
00:00:26,970 --> 00:00:29,800
Karščiausios jį žemyn Pseudocode
galėtume teigti, šį algoritmą

10
00:00:29,800 --> 00:00:34,490
taip, pakartokite šį iki
nėra nerūšiuotos elementai išlieka.

11
00:00:34,490 --> 00:00:38,660
Paieška per nerūšiuotų
duomenų rasti mažiausią vertę,

12
00:00:38,660 --> 00:00:44,130
tada apsikeitimo mažiausią vertę su
pirmasis elementas nerūšiuotųomis dalis.

13
00:00:44,130 --> 00:00:47,130
>> Jis gali padėti vizualizuoti tai,
todėl galime imtis į tai žiūrėti.

14
00:00:47,130 --> 00:00:49,710
Taigi, tai, aš teigia, yra
nerūšiuotų masyvo ir aš

15
00:00:49,710 --> 00:00:53,040
nurodyta, kad, nurodant, kad visi
iš elementų yra raudoni,

16
00:00:53,040 --> 00:00:54,420
jie yra dar rūšiuojami.

17
00:00:54,420 --> 00:00:57,670
Tai yra visa
nerūšiuotų dalis masyvo.

18
00:00:57,670 --> 00:01:02,020
>> Taigi eikime per žingsnių
pasirinkimas rūšiuoti rūšiuoti šio masyvo.

19
00:01:02,020 --> 00:01:05,296
Taigi dar kartą, mes gonna kartojimą
kol nėra nerūšiuotos elementai išlieka.

20
00:01:05,296 --> 00:01:07,920
Mes gonna paiešką per
duomenų rasti mažiausią vertę,

21
00:01:07,920 --> 00:01:11,990
ir tada sukeisti šią vertę su
pirmasis elementas nerūšiuotųomis dalis.

22
00:01:11,990 --> 00:01:14,380
>> Dabar, vėlgi, visa
masyvas yra nerūšiuotos dalis.

23
00:01:14,380 --> 00:01:16,534
Visi raudonų elementų yra nerūšiuotos.

24
00:01:16,534 --> 00:01:18,700
Taigi, mes ieškoti ir
randame mažiausią vertę.

25
00:01:18,700 --> 00:01:20,533
Mes pradėti iš pradžių,
mes einame iki galo,

26
00:01:20,533 --> 00:01:23,630
randame mažiausios vertės yra viena.

27
00:01:23,630 --> 00:01:24,860
Štai pirmoji dalis.

28
00:01:24,860 --> 00:01:29,440
Ir tada antroji dalis, apsikeitimo šią vertę su
pirmasis elementas nerūšiuotųomis dalis,

29
00:01:29,440 --> 00:01:31,340
arba pirmą raudona elementas.

30
00:01:31,340 --> 00:01:34,980
>> Šiuo atveju, kad būtų
penki, todėl mes apsikeitimo vienerių ir penkerių.

31
00:01:34,980 --> 00:01:37,320
Kai mes tai darome, mes galime
vizualiai matyti, kad mes

32
00:01:37,320 --> 00:01:41,260
persikėlė mažiausią vertinami elementą
masyvo, į pačią pradžią.

33
00:01:41,260 --> 00:01:43,920
Efektyviai rūšiavimo, kad elementas.

34
00:01:43,920 --> 00:01:47,520
>> Ir todėl mes galime iš tiesų patvirtina,
ir nurodyti, kad vienas yra rūšiuojami.

35
00:01:47,520 --> 00:01:52,080
Ir todėl mes nurodyti surūšiuoti dalis
mūsų masyvas, kurį dažymas jis mėlynas.

36
00:01:52,080 --> 00:01:53,860
>> Dabar mes tiesiog vėl pakartokite šį procesą.

37
00:01:53,860 --> 00:01:57,430
Ieškome per nerūšiuotų dalis
masyvas rasti mažiausią elementą.

38
00:01:57,430 --> 00:01:59,000
Šiuo atveju, tai du.

39
00:01:59,000 --> 00:02:02,100
>> Mes apsikeitimo, kad su pirmuoju
elementas nerūšiuotųomis dalis.

40
00:02:02,100 --> 00:02:05,540
Šiuo atveju du taip pat atsitinka būti
pirmasis elementas nerūšiuotųomis dalis.

41
00:02:05,540 --> 00:02:08,650
Taigi, mes apsikeitimo du su savimi,
kuri tikrai tik palieka du

42
00:02:08,650 --> 00:02:11,257
kur ji yra, ir tai rūšiuojami.

43
00:02:11,257 --> 00:02:13,840
Tęsiant, mes ieškoti
rasti mažiausią elementą.

44
00:02:13,840 --> 00:02:15,030
Tai trys.

45
00:02:15,030 --> 00:02:17,650
Mes sukeisti su pirmuoju
elementas, kuris yra penki.

46
00:02:17,650 --> 00:02:19,450
O dabar trys yra rūšiuojami.

47
00:02:19,450 --> 00:02:22,440
>> Mes ieškoti dar kartą, ir mes
rasti mažiausias elementas yra keturi.

48
00:02:22,440 --> 00:02:28,070
Mes sukeisti su pirmuoju elementu
nerūšiuotų dalis, o dabar keturi rūšiuojamos.

49
00:02:28,070 --> 00:02:29,910
>> Manome, kad penki yra
mažiausias elementas.

50
00:02:29,910 --> 00:02:32,900
Mes sukeisti su pirmuoju
elementas nerūšiuotųomis dalis.

51
00:02:32,900 --> 00:02:34,740
Ir dabar penkios yra rūšiuojami.

52
00:02:34,740 --> 00:02:36,660
>> Ir tada galiausiai, mūsų
nerūšiuotų dalį sudaro

53
00:02:36,660 --> 00:02:38,576
tiesiog vieno elemento,
todėl mes ieškoti

54
00:02:38,576 --> 00:02:41,740
ir matome, kad šeši yra
mažiausias, ir iš tikrųjų, tik elementas.

55
00:02:41,740 --> 00:02:44,906
Ir tada mes galime teigti, kad ji yra rūšiuojami.

56
00:02:44,906 --> 00:02:47,530
Ir dabar mes perėjo mūsų masyvas
iki galo Nerūšiuotos

57
00:02:47,530 --> 00:02:52,660
raudonai, visiškai rūšiuojami
mėlyna, naudojant atrankos rūšiuoti.

58
00:02:52,660 --> 00:02:54,920
>> Taigi, kas blogiausiu atveju čia?

59
00:02:54,920 --> 00:02:57,830
Na absoliutus blogiausias
atveju, mes turime pažvelgti per

60
00:02:57,830 --> 00:03:02,170
visi iš masyvo elementų iki
Raskite mažiausią nerūšiuotas elementas,

61
00:03:02,170 --> 00:03:04,750
ir mes turime kartoti
šis procesas n kartų.

62
00:03:04,750 --> 00:03:09,090
Kai kiekvienam masyvo elementą
nes mes tik, šiuo algoritmu,

63
00:03:09,090 --> 00:03:12,180
Rūšiuoti vienas elementas metu.

64
00:03:12,180 --> 00:03:13,595
>> Koks geriausias scenarijus?

65
00:03:13,595 --> 00:03:15,040
Na tai lygiai tas pats, tiesa?

66
00:03:15,040 --> 00:03:18,440
Mes iš tikrųjų turime dar žingsnis per
kiekvienas elementas masyve

67
00:03:18,440 --> 00:03:22,040
siekiant patvirtinti, kad ji yra,
Iš tiesų, mažiausias elementas.

68
00:03:22,040 --> 00:03:26,760
>> Taigi blogiausiu atveju Runtime, mes
turi pakartoti procesą n kartų,

69
00:03:26,760 --> 00:03:28,960
vieną kartą kiekvienas iš n elementų.

70
00:03:28,960 --> 00:03:31,940
Ir geriausiu atveju,
turime padaryti tą patį.

71
00:03:31,940 --> 00:03:35,340
>> Taigi galvoju grįžti į mūsų
skaičiavimo sudėtingumas rinkinys,

72
00:03:35,340 --> 00:03:39,250
ką jūs manote yra blogiausia
atveju Veikimo atrankos rūšiuoti?

73
00:03:39,250 --> 00:03:41,840
Ką manote yra geriausias
atveju Veikimo atrankos rūšiuoti?

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

75
00:03:44,760 --> 00:03:49,325
>> Ar galite atspėti, Big O n kvadratu,
Big omega n kvadratu?

76
00:03:49,325 --> 00:03:49,950
Jūs norite būti teisus.

77
00:03:49,950 --> 00:03:52,490
Tie, iš tiesų,
blogiausiu atveju ir geriausias atvejis paleisti

78
00:03:52,490 --> 00:03:55,100
kartų, dėl atrankos rūšiuoti.

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

80
00:03:56,260 --> 00:03:58,600
Tai CS50.

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