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

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Izbor vrsta je
algoritam koji, kao što bi ste očekivali,

3
00:00:08,600 --> 00:00:10,470
sortira niz elemenata.

4
00:00:10,470 --> 00:00:12,470
I algoritam opoziv
je korak-po-korak set

5
00:00:12,470 --> 00:00:15,260
uputa za dovršetak zadatka.

6
00:00:15,260 --> 00:00:17,580
>> U izboru sortiranje
Osnovna ideja je ovo,

7
00:00:17,580 --> 00:00:22,080
Pronađi najmanji nesortiranog element i
dodati na kraju sortiranog popisa.

8
00:00:22,080 --> 00:00:26,970
Učinkovito što to čini se graditi
popis razvrstani, jedan element u isto vrijeme.

9
00:00:26,970 --> 00:00:29,800
Razbijanje dolje pseudokod
možemo navesti ovaj algoritam

10
00:00:29,800 --> 00:00:34,490
kako slijedi, ponovite sve dok
nema Nesortirani elementi ostaju.

11
00:00:34,490 --> 00:00:38,660
Pretraži kroz nesortiran
Podaci pronaći najmanju vrijednost,

12
00:00:38,660 --> 00:00:44,130
zatim zamijeniti najmanju vrijednost s
Prvi element nerazvrstanog dijela.

13
00:00:44,130 --> 00:00:47,130
>> To može pomoći vizualizirati to,
pa neka je pogledati ovo.

14
00:00:47,130 --> 00:00:49,710
Dakle, ovo, smatram, je
nesortirani niz i imam

15
00:00:49,710 --> 00:00:53,040
to ukazuje ukazuje da je sve
elemenata su crvene boje,

16
00:00:53,040 --> 00:00:54,420
oni još nisu razvrstani.

17
00:00:54,420 --> 00:00:57,670
Ovo je cijeli
nesortirani dio polja.

18
00:00:57,670 --> 00:01:02,020
>> Tako ćemo proći kroz korake
Izbor vrsta za sortiranje ovaj niz.

19
00:01:02,020 --> 00:01:05,296
Pa opet, mi ćemo ponoviti
dok nema Nesortirani elementi ostaju.

20
00:01:05,296 --> 00:01:07,920
Ćemo potragu kroz
Podaci pronaći najmanju vrijednost,

21
00:01:07,920 --> 00:01:11,990
a zatim zamijeniti tu vrijednost s
Prvi element nerazvrstanog dijela.

22
00:01:11,990 --> 00:01:14,380
>> Upravo sada, opet, čitav
Niz je Nesortirano dio.

23
00:01:14,380 --> 00:01:16,534
Sve od crvenih elemenata Nesortirano.

24
00:01:16,534 --> 00:01:18,700
Tako smo i pretraživanje
nađemo najmanji vrijednost.

25
00:01:18,700 --> 00:01:20,533
Krećemo na početku,
idemo do kraja,

26
00:01:20,533 --> 00:01:23,630
nađemo najmanji vrijednost, jedan.

27
00:01:23,630 --> 00:01:24,860
Dakle, to je jedan dio.

28
00:01:24,860 --> 00:01:29,440
A onda je dio dva, mijenjati tu vrijednost s
Prvi element nerazvrstanog dijela,

29
00:01:29,440 --> 00:01:31,340
ili prvi crveni elementa.

30
00:01:31,340 --> 00:01:34,980
>> U tom slučaju bi se
pet, tako da smo zamijeniti jedan i pet.

31
00:01:34,980 --> 00:01:37,320
Kada smo to učinili, možemo
vizualno vidjeti da smo

32
00:01:37,320 --> 00:01:41,260
preselio najmanji vrijednosti elementa
od polja, na samom početku.

33
00:01:41,260 --> 00:01:43,920
Učinkovito sortiranje taj element.

34
00:01:43,920 --> 00:01:47,520
>> I tako smo doista može potvrditi
i tvrde da jedan, sortira.

35
00:01:47,520 --> 00:01:52,080
I tako ćemo navesti sortiran dio
naše ponude, bojanje plava.

36
00:01:52,080 --> 00:01:53,860
>> Sada mi samo ponoviti postupak opet.

37
00:01:53,860 --> 00:01:57,430
Mi tražimo kroz nerazvrstani dio
Niz pronaći najmanji element.

38
00:01:57,430 --> 00:01:59,000
U ovom slučaju, to dvoje.

39
00:01:59,000 --> 00:02:02,100
>> Mi mijenjati da s prvim
element nerazvrstani dio.

40
00:02:02,100 --> 00:02:05,540
U ovom slučaju dva također dogoditi da se
Prvi element nerazvrstanog dijela.

41
00:02:05,540 --> 00:02:08,650
Tako smo zamijeniti dva sa sebe,
koji zapravo samo ostavlja dva

42
00:02:08,650 --> 00:02:11,257
gdje je, i to je riješeno.

43
00:02:11,257 --> 00:02:13,840
Nastavljajući se na, mi pretraživanje
pronaći najmanji element.

44
00:02:13,840 --> 00:02:15,030
To je tri.

45
00:02:15,030 --> 00:02:17,650
Mi ga zamijeniti s prvim
element, koji je pet.

46
00:02:17,650 --> 00:02:19,450
A sada tri je riješeno.

47
00:02:19,450 --> 00:02:22,440
>> Mi pretraživanje opet, i mi
naći najmanji element je četiri.

48
00:02:22,440 --> 00:02:28,070
Mi ga zamijeniti s prvim elementom
nesortirani dio, a sada četiri sortira.

49
00:02:28,070 --> 00:02:29,910
>> Smatramo da je pet
najmanji element.

50
00:02:29,910 --> 00:02:32,900
Mi ga zamijeniti s prvim
element nerazvrstani dio.

51
00:02:32,900 --> 00:02:34,740
A sada pet je riješeno.

52
00:02:34,740 --> 00:02:36,660
>> I onda na kraju, naš
nesortiran dio sastoji

53
00:02:36,660 --> 00:02:38,576
od samo jednog elementa,
pa smo pretraživanje

54
00:02:38,576 --> 00:02:41,740
a mi da šest je
najmanji, i zapravo, jedini element.

55
00:02:41,740 --> 00:02:44,906
A onda možemo reći da je to riješeno.

56
00:02:44,906 --> 00:02:47,530
I sada smo prebacili našu niz
od toga da bude potpuno nerazvrstani

57
00:02:47,530 --> 00:02:52,660
crveno, potpuno razvrstani
u plavom, pomoću odabira vrste.

58
00:02:52,660 --> 00:02:54,920
>> Dakle, što je najgori mogući scenarij ovdje?

59
00:02:54,920 --> 00:02:57,830
Pa u apsolutno najgore
slučaju, moramo gledati preko

60
00:02:57,830 --> 00:03:02,170
svi elemenata polja za
Pronađi najmanji nesortiranog elementa,

61
00:03:02,170 --> 00:03:04,750
i moramo ponoviti
ovaj proces N puta.

62
00:03:04,750 --> 00:03:09,090
Jednom za svaki element polja
jer smo samo, u ovom algoritmu,

63
00:03:09,090 --> 00:03:12,180
sortirati jedan element na vrijeme.

64
00:03:12,180 --> 00:03:13,595
>> Koji je najbolji mogući scenarij?

65
00:03:13,595 --> 00:03:15,040
Pa to je točno isto, zar ne?

66
00:03:15,040 --> 00:03:18,440
Mi zapravo moramo još korak kroz
svaki element polja

67
00:03:18,440 --> 00:03:22,040
kako bi potvrdili da je,
u stvari, najmanji element.

68
00:03:22,040 --> 00:03:26,760
>> Dakle, u najgorem slučaju izvođenja smo
morati ponoviti postupak n puta,

69
00:03:26,760 --> 00:03:28,960
jednom za svaki od n elemenata.

70
00:03:28,960 --> 00:03:31,940
I u najboljem slučaju,
moramo učiniti isto.

71
00:03:31,940 --> 00:03:35,340
>> Dakle, razmišljam natrag u naš
računalna složenost alatni,

72
00:03:35,340 --> 00:03:39,250
Što mislite je najgore
Slučaj runtime za izbor vrste?

73
00:03:39,250 --> 00:03:41,840
Što mislite je najbolja
Slučaj runtime za izbor vrste?

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

75
00:03:44,760 --> 00:03:49,325
>> Jeste li pogoditi Big O n na kvadrat,
i Big Omega n na kvadrat?

76
00:03:49,325 --> 00:03:49,950
Ti bi biti u pravu.

77
00:03:49,950 --> 00:03:52,490
Oni su, u stvari,
najgorem slučaju i najboljem slucaju pokrenuti

78
00:03:52,490 --> 00:03:55,100
puta, za odabir vrste.

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

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

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