1
00:00:00,000 --> 00:00:05,726
>> [Musika jotzen]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Hautaketa moduko bat da
Algoritmo hori, agian, espero bezala,

3
00:00:08,600 --> 00:00:10,470
elementu multzo bat ordenatzen du.

4
00:00:10,470 --> 00:00:12,470
Eta algoritmoa abisuaren
Urrats-urrats multzo bat da

5
00:00:12,470 --> 00:00:15,260
zeregin bat betetzeko argibideak ere.

6
00:00:15,260 --> 00:00:17,580
>> Aukeraketa horrelakorik
Oinarrizko ideia hau da,

7
00:00:17,580 --> 00:00:22,080
Unsorted elementu txikiena aurkitu eta
gehitu du antolatu zerrenda amaierara arte.

8
00:00:22,080 --> 00:00:26,970
Eraginkortasunez zer honek eraikitze da
ordenatuko da zerrenda bat, aldi berean, elementu bat.

9
00:00:26,970 --> 00:00:29,800
Banatzea pseudocode den
Algoritmo hau baiezta genezake

10
00:00:29,800 --> 00:00:34,490
honela, errepikatu arte
no Sailkatu elementu geratzen.

11
00:00:34,490 --> 00:00:38,660
Sailkatu bidez bilatzeko
Datu balio txikiena aurkitu,

12
00:00:38,660 --> 00:00:44,130
ondoren trukatu balio txikiena batera
Unsorted zatia lehenengo elementua.

13
00:00:44,130 --> 00:00:47,130
>> Hau ikusteko programak lagundu ahal izango da,
beraz dezagun begirada bat.

14
00:00:47,130 --> 00:00:49,710
Beraz, hau, nire asmoa, da
Sailkatu array eta dut

15
00:00:49,710 --> 00:00:53,040
Adierazitako hori guztia adieraziz
elementuetako kolore gorria ematen zaie,

16
00:00:53,040 --> 00:00:54,420
azken horiek ez dira oraindik ordenatuta.

17
00:00:54,420 --> 00:00:57,670
Hau osoa da
array zati Unsorted.

18
00:00:57,670 --> 00:01:02,020
>> Beraz, goazen urrats bidez
aukeraketa ordenatu array hau ordenatzeko.

19
00:01:02,020 --> 00:01:05,296
Beraz, berriro ere, gonna errepikatu gaude
no Sailkatu elementu geratzen den arte.

20
00:01:05,296 --> 00:01:07,920
Gonna bilaketa bidez ari gara
Datu balio txikiena aurkitu,

21
00:01:07,920 --> 00:01:11,990
eta ondoren, trukatu batera balio duten
Unsorted zatia lehenengo elementua.

22
00:01:11,990 --> 00:01:14,380
>> Oraintxe bertan, berriro, osoa
array Unsorted zati da.

23
00:01:14,380 --> 00:01:16,534
Elementu gorri guztiak Sailkatu dira.

24
00:01:16,534 --> 00:01:18,700
Beraz bilatu bidez dugu eta
balio txikiena aurkitu dugu.

25
00:01:18,700 --> 00:01:20,533
Hasteko hasieran gaude,
Amaieran joan ginen,

26
00:01:20,533 --> 00:01:23,630
aurkitu dugu balio txikiena da, bat.

27
00:01:23,630 --> 00:01:24,860
Beraz, hori zati bat da.

28
00:01:24,860 --> 00:01:29,440
Eta gero, bi zati, trukatu dituzten balio duten
Unsorted zatia lehenengo elementua,

29
00:01:29,440 --> 00:01:31,340
edo lehen elementu gorria.

30
00:01:31,340 --> 00:01:34,980
>> Kasu honetan izango litzateke
bost, beraz, bat eta bost trukatzeko.

31
00:01:34,980 --> 00:01:37,320
Hori egiten dugunean, ezin ditugu
ikusmen ikusi ditudan dugu

32
00:01:37,320 --> 00:01:41,260
txikiena baloratzen elementu mugitu
Array, hasieratik nahi.

33
00:01:41,260 --> 00:01:43,920
Eraginkortasunez ordenatzen den elementu hori.

34
00:01:43,920 --> 00:01:47,520
>> Eta beraz, dugu, hain zuzen ere, baieztatu daiteke
eta egoera hori, ordenatuko da.

35
00:01:47,520 --> 00:01:52,080
Eta horrela adierazi beharko dugu ordenatzen zati
gure array, urdin margotu.

36
00:01:52,080 --> 00:01:53,860
>> Orain errepikatu besterik ez dugu prozesua berriro.

37
00:01:53,860 --> 00:01:57,430
Bilatu zati Unsorted bidez dugu
array elementu txikiena aurkitu.

38
00:01:57,430 --> 00:01:59,000
Kasu honetan, bi da.

39
00:01:59,000 --> 00:02:02,100
>> Trukatu dugun lehenengo batera
Unsorted zati elementu.

40
00:02:02,100 --> 00:02:05,540
Kasu honetan bi ere gertatzen den izan
Unsorted zatia lehenengo elementua.

41
00:02:05,540 --> 00:02:08,650
Beraz, bi berez trukatu dugu,
horrek benetan bi hostoak

42
00:02:08,650 --> 00:02:11,257
Non da, eta ordenatuko da.

43
00:02:11,257 --> 00:02:13,840
Etengabeko on, bidez bilatzen dugu
elementu txikiena aurkitu.

44
00:02:13,840 --> 00:02:15,030
It hiru da.

45
00:02:15,030 --> 00:02:17,650
Egiten dugu trukatu lehenengoarekin
elementu, bost da.

46
00:02:17,650 --> 00:02:19,450
Eta orain hiru ordenatuko da.

47
00:02:19,450 --> 00:02:22,440
>> Non bilatzen dugu bidez berriro, eta guk
aurkituko elementu txikiena lau da.

48
00:02:22,440 --> 00:02:28,070
Bertan trukatu dugu lehen elementu batera
Sailkatu parte, eta, orain, lau ordenatuko da.

49
00:02:28,070 --> 00:02:29,910
>> Aurkituko dugu, bost da
elementu txikiena.

50
00:02:29,910 --> 00:02:32,900
Egiten dugu trukatu lehenengoarekin
Unsorted zati elementu.

51
00:02:32,900 --> 00:02:34,740
Eta orain bost ordenatuko da.

52
00:02:34,740 --> 00:02:36,660
>> Eta gero, azkenik, gure
Sailkatu parte osatzen

53
00:02:36,660 --> 00:02:38,576
elementu bakar bat besterik ez da,
beraz bilatu bidez dugu

54
00:02:38,576 --> 00:02:41,740
eta aurkitu ditugun sei da
txikiena, eta hain zuzen ere, soilik elementu.

55
00:02:41,740 --> 00:02:44,906
Eta gero, esan daiteke dela ordenatuko da.

56
00:02:44,906 --> 00:02:47,530
Eta orain, gure array pizten ditugu
Ari erabat Unsorted bertatik

57
00:02:47,530 --> 00:02:52,660
Gorriz, erabat ordenatuko
urdina, hautaketa ordena erabiliz.

58
00:02:52,660 --> 00:02:54,920
>> Beraz, zein da kasu okerrena hemen?

59
00:02:54,920 --> 00:02:57,830
Beno absolutua txarrenean
Kasu, baino gehiago begiratu behar dugu

60
00:02:57,830 --> 00:03:02,170
array elementu den guztia
Unsorted elementu txikiena aurkitu,

61
00:03:02,170 --> 00:03:04,750
eta errepikatu behar dugu
Prozesu honek n aldiz.

62
00:03:04,750 --> 00:03:09,090
Array elementu bakoitzeko behin
dugun bakarra delako, algoritmo honetan,

63
00:03:09,090 --> 00:03:12,180
moduko elementu bat aldi berean.

64
00:03:12,180 --> 00:03:13,595
>> Zer da kasurik onenean?

65
00:03:13,595 --> 00:03:15,040
Beno berdin da, ezta?

66
00:03:15,040 --> 00:03:18,440
Benetan daukagu ​​bidez oraindik zapalduta
array elementu bakar behin

67
00:03:18,440 --> 00:03:22,040
ordena dela baieztatzeko,
hain zuzen ere, elementu txikiena.

68
00:03:22,040 --> 00:03:26,760
>> Beraz, kasu exekuzio txarrena, dugu
Prozesu n aldiz errepikatu behar,

69
00:03:26,760 --> 00:03:28,960
n elementu bakoitzari behin.

70
00:03:28,960 --> 00:03:31,940
Eta kasurik onenean ere,
Gauza bera egin behar dugu.

71
00:03:31,940 --> 00:03:35,340
>> Beraz, atzera pentsatzen gure
konputazional konplexutasunaren laukitik,

72
00:03:35,340 --> 00:03:39,250
zer uste duzu dela txarrena
Kasu aukeraketa sort exekuzio?

73
00:03:39,250 --> 00:03:41,840
Zure ustez, zer da onena
Kasu aukeraketa sort exekuzio?

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

75
00:03:44,760 --> 00:03:49,325
>> Ba asmatzen duzu Big n O karratu,
eta Big Omega n karratu?

76
00:03:49,325 --> 00:03:49,950
Eskubidea litzaidake.

77
00:03:49,950 --> 00:03:52,490
Horiek dira, hain zuzen ere,
txarrena kasuan eta onena kasu run

78
00:03:52,490 --> 00:03:55,100
aldiz, hautaketa ordena da.

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

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

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