1
00:00:00,000 --> 00:00:05,726
>> [Zenelejátszási]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selection sort egy
algoritmus, ahogy az várható,

3
00:00:08,600 --> 00:00:10,470
rendezi egy sor elemet.

4
00:00:10,470 --> 00:00:12,470
És algoritmus visszahívás
egy lépésről-lépésre sor

5
00:00:12,470 --> 00:00:15,260
Az utasítások egy feladat elvégzéséhez.

6
00:00:15,260 --> 00:00:17,580
>> A kiválasztás rendezni az
alapötlet ezt,

7
00:00:17,580 --> 00:00:22,080
Keresse meg a legkisebb nem válogatott elem és
add hozzá a végén a rendezett listát.

8
00:00:22,080 --> 00:00:26,970
Hatékonyan Mi ez épít
egy rendezett lista, az egyik elem egy időben.

9
00:00:26,970 --> 00:00:29,800
Breaking le, hogy pszeudokódja
állíthatnánk azt, ez az algoritmus

10
00:00:29,800 --> 00:00:34,490
az alábbiak szerint, ismételje meg ezt, amíg
nem szétválogatott elem marad.

11
00:00:34,490 --> 00:00:38,660
Keresés a szétválogatás nélkül
adatokat, hogy megtalálják a legkisebb értéket,

12
00:00:38,660 --> 00:00:44,130
majd cserélni a legkisebb érték a
első eleme A szétválogatás nélkül részt.

13
00:00:44,130 --> 00:00:47,130
>> Segíthet, hogy megjelenítsék ezt,
ezért vessünk egy pillantást erre.

14
00:00:47,130 --> 00:00:49,710
Tehát ez azt állítják,, egy
szétválogatás nélkül tömb, és már

15
00:00:49,710 --> 00:00:53,040
jelezte azt jelezve, hogy minden
Az elemek piros színű,

16
00:00:53,040 --> 00:00:54,420
még nincsenek rendezve.

17
00:00:54,420 --> 00:00:57,670
Ez az a teljes
szétválogatás nélküli része a tömbben.

18
00:00:57,670 --> 00:01:02,020
>> Szóval menjünk a lépéseit
kiválasztási sorrend rendezni ezt a tömböt.

19
00:01:02,020 --> 00:01:05,296
Tehát újra, meg fogjuk ismétlés
amíg nem válogatott elemek maradnak.

20
00:01:05,296 --> 00:01:07,920
Csinálunk keresési keresztül
adatokat, hogy megtalálják a legkisebb értéket,

21
00:01:07,920 --> 00:01:11,990
majd cserélni ezt az értéket a
első eleme A szétválogatás nélkül részt.

22
00:01:11,990 --> 00:01:14,380
>> Most ismét a teljes
tömb A rendezetlen része.

23
00:01:14,380 --> 00:01:16,534
Mind a piros elemek szelektálatlan.

24
00:01:16,534 --> 00:01:18,700
Tehát keresgélni és
találjuk a legkisebb érték.

25
00:01:18,700 --> 00:01:20,533
Kezdjük az elején,
megyünk a végén,

26
00:01:20,533 --> 00:01:23,630
találjuk a legkisebb érték, egy.

27
00:01:23,630 --> 00:01:24,860
Szóval ez is része az egyik.

28
00:01:24,860 --> 00:01:29,440
Aztán a második rész, a csere azt az értéket
Az első elem a szétválogatás nélküli része,

29
00:01:29,440 --> 00:01:31,340
vagy az első piros elem.

30
00:01:31,340 --> 00:01:34,980
>> Ebben az esetben az lenne
Öt, ezért cserélni egy és öt.

31
00:01:34,980 --> 00:01:37,320
Amikor ezt tesszük, amit lehet
vizuálisan látni, hogy már

32
00:01:37,320 --> 00:01:41,260
költözött a legkisebb értékű elem
A tömb, a legelején.

33
00:01:41,260 --> 00:01:43,920
Hatékonyan válogatás adott elem.

34
00:01:43,920 --> 00:01:47,520
>> És így valóban megerősítik,
és kijelentik, hogy az egyik, van rendezve.

35
00:01:47,520 --> 00:01:52,080
És így fogunk tüntetni a rendezve része
a mi tömb, színezés, hogy kék.

36
00:01:52,080 --> 00:01:53,860
>> Most már csak ismételjük meg a folyamatot újra.

37
00:01:53,860 --> 00:01:57,430
Mi keresni a szétválogatás nélküli része
a tömb, hogy megtalálják a legkisebb eleme.

38
00:01:57,430 --> 00:01:59,000
Ebben az esetben, ez a két.

39
00:01:59,000 --> 00:02:02,100
>> Mi cserélni, hogy az első
eleme a szétválogatás nélkül részt.

40
00:02:02,100 --> 00:02:05,540
Ebben az esetben két is előfordul, hogy
Az első elem a szétválogatás nélkül részt.

41
00:02:05,540 --> 00:02:08,650
Tehát csere két önmagával,
ami tényleg csak hagy két

42
00:02:08,650 --> 00:02:11,257
hogy hol van, és ez válogatni.

43
00:02:11,257 --> 00:02:13,840
Folytatva, amit keresni
hogy megtalálják a legkisebb eleme.

44
00:02:13,840 --> 00:02:15,030
Ez három.

45
00:02:15,030 --> 00:02:17,650
Mi cserélni neki az első
elem, amely öt.

46
00:02:17,650 --> 00:02:19,450
És most három rendezve.

47
00:02:19,450 --> 00:02:22,440
>> Mi keresgélni újra, és
Keresse meg a legkisebb elem négy.

48
00:02:22,440 --> 00:02:28,070
Mi cserélni neki az első eleme a
osztályozás nélküli része, és most négy rendezve.

49
00:02:28,070 --> 00:02:29,910
>> Azt látjuk, hogy az öt az
A legkisebb eleme.

50
00:02:29,910 --> 00:02:32,900
Mi cserélni neki az első
eleme a szétválogatás nélkül részt.

51
00:02:32,900 --> 00:02:34,740
És most öt rendezve.

52
00:02:34,740 --> 00:02:36,660
>> És akkor végül, mi
szétválogatott része áll

53
00:02:36,660 --> 00:02:38,576
csak egyetlen elem,
így keresni

54
00:02:38,576 --> 00:02:41,740
és azt látjuk, hogy hat a
legkisebb, és valójában egyetlen eleme.

55
00:02:41,740 --> 00:02:44,906
És akkor azt mondhatjuk, hogy válogatni.

56
00:02:44,906 --> 00:02:47,530
És most már kapcsolva a tömb
attól, hogy teljesen szétválogatott

57
00:02:47,530 --> 00:02:52,660
piros, teljesen rendezve
kék, a kiválasztási sorrend.

58
00:02:52,660 --> 00:02:54,920
>> Szóval mi a legrosszabb forgatókönyv itt?

59
00:02:54,920 --> 00:02:57,830
Nos az abszolút legrosszabb
esetben meg kell nézni fölött

60
00:02:57,830 --> 00:03:02,170
valamennyi elemét a tömb
Keresse meg a legkisebb osztályozás nélküli elemet,

61
00:03:02,170 --> 00:03:04,750
és meg kell ismételni
E folyamat n-szer.

62
00:03:04,750 --> 00:03:09,090
Miután minden egyes eleme a tömb
mert csak ebben az algoritmus,

63
00:03:09,090 --> 00:03:12,180
Rendezés egyik eleme időpontban.

64
00:03:12,180 --> 00:03:13,595
>> Mi a legjobb esetben?

65
00:03:13,595 --> 00:03:15,040
Hát ez pontosan ugyanaz, ugye?

66
00:03:15,040 --> 00:03:18,440
Igazából az is átléphető
minden egyes eleme a tömb

67
00:03:18,440 --> 00:03:22,040
annak érdekében, hogy erősítse meg, hogy,
Tény, hogy a legkisebb elem.

68
00:03:22,040 --> 00:03:26,760
>> Tehát a legrosszabb esetben runtime, mi
meg kell ismételni a folyamatot n-szer,

69
00:03:26,760 --> 00:03:28,960
egyszer minden n elem.

70
00:03:28,960 --> 00:03:31,940
És a legjobb esetben,
van, hogy ugyanezt tegyék.

71
00:03:31,940 --> 00:03:35,340
>> Szóval gondoltam vissza a
számítási komplexitás eszköztár,

72
00:03:35,340 --> 00:03:39,250
mit gondolsz a legrosszabb
esetében futásidejű kiválasztási sorrend?

73
00:03:39,250 --> 00:03:41,840
Mit gondolsz a legjobb
esetében futásidejű kiválasztási sorrend?

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

75
00:03:44,760 --> 00:03:49,325
>> Te hiszem Big O n faragva,
és a Big Omega n faragva?

76
00:03:49,325 --> 00:03:49,950
Igazad van.

77
00:03:49,950 --> 00:03:52,490
Azok, sőt, a
Legrosszabb esetben és a legjobb esetben távon

78
00:03:52,490 --> 00:03:55,100
szor, a kiválasztási sorrend.

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

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

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