1
00:00:00,000 --> 00:00:05,726
>> [MUSIC PLAYING]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Seçim sort bir deyil
Siz gözləyə bilər kimi, alqoritm,

3
00:00:08,600 --> 00:00:10,470
elementlərin bir sıra növ.

4
00:00:10,470 --> 00:00:12,470
Və alqoritm geri
bir addım-addım müəyyən edilir

5
00:00:12,470 --> 00:00:15,260
bir vəzifə doldurulması təlimatlar.

6
00:00:15,260 --> 00:00:17,580
>> Seçimi sort
Əsas ideyası, bu

7
00:00:17,580 --> 00:00:22,080
kiçik çeşidlənməmiş element tapmaq və
sorted siyahısı sonuna əlavə edin.

8
00:00:22,080 --> 00:00:26,970
Səmərəli, bu nə build edir
bir sıralanır siyahısı bir-bir element.

9
00:00:26,970 --> 00:00:29,800
Pseudocode onu Breaking
bu alqoritm bəyan edə bilər

10
00:00:29,800 --> 00:00:34,490
aşağıdakı qədər bu təkrar
heç bir çeşidlənməmiş elementləri qalır.

11
00:00:34,490 --> 00:00:38,660
Çeşidlənməmiş vasitəsilə axtarış
data kiçik dəyər tapmaq üçün,

12
00:00:38,660 --> 00:00:44,130
sonra ilə kiçik dəyər dəyişdirmək
çeşidlənməmiş hissəsi ilk element.

13
00:00:44,130 --> 00:00:47,130
>> Bu, bu görüntüləmək kömək edə bilər
Belə ki, bu nəzər salaq.

14
00:00:47,130 --> 00:00:49,710
Belə ki, bu, I yarışmaq, bir deyil
çeşidlənməmiş array və mən var

15
00:00:49,710 --> 00:00:53,040
bütün olduğunu ifadə edən tərəfindən göstərilən
elementləri qırmızı rəngli

16
00:00:53,040 --> 00:00:54,420
onlar hələ sıralanır deyil.

17
00:00:54,420 --> 00:00:57,670
Bu, bütün deyil
serialın çeşidlənməmiş hissəsi.

18
00:00:57,670 --> 00:01:02,020
>> Belə ki, addımlar vasitəsilə getmək imkan
seçim sort bu array sort.

19
00:01:02,020 --> 00:01:05,296
Belə ki, yenə, biz edəcəyimizi təkrar edirik
heç bir çeşidlənməmiş elementləri qalır qədər.

20
00:01:05,296 --> 00:01:07,920
Biz vasitəsilə mý axtarış etdiyiniz
data kiçik dəyər tapmaq üçün,

21
00:01:07,920 --> 00:01:11,990
və sonra ki, dəyəri dəyişdirmək
çeşidlənməmiş hissəsi ilk element.

22
00:01:11,990 --> 00:01:14,380
>> Hal-hazırda, yenə bütün
array çeşidlənməmiş hissəsidir.

23
00:01:14,380 --> 00:01:16,534
Qırmızı elementləri bütün çeşidlənməmiş var.

24
00:01:16,534 --> 00:01:18,700
Beləliklə, biz vasitəsilə axtarış və
biz kiçik dəyər tapmaq.

25
00:01:18,700 --> 00:01:20,533
Biz başında
Biz sonuna qədər getmək

26
00:01:20,533 --> 00:01:23,630
biz kiçik dəyər, bir tapa bilərsiniz.

27
00:01:23,630 --> 00:01:24,860
Belə ki, bir hissəsi biridir.

28
00:01:24,860 --> 00:01:29,440
Və sonra hissəsi iki, ilə ki, dəyəri dəyişdirmək
çeşidlənməmiş hissəsi ilk element,

29
00:01:29,440 --> 00:01:31,340
və ya ilk qırmızı element.

30
00:01:31,340 --> 00:01:34,980
>> Bu halda ola bilər ki,
beş, belə ki, biz bir və beş dəyişdirmək.

31
00:01:34,980 --> 00:01:37,320
Bunu zaman, biz
vizual biz ki, görəcəksiniz

32
00:01:37,320 --> 00:01:41,260
kiçik qiymətli element köçürülüb
serialın çox əvvəlinə.

33
00:01:41,260 --> 00:01:43,920
Səmərəli element çeşidlənməsi.

34
00:01:43,920 --> 00:01:47,520
>> Və belə ki, biz, həqiqətən, təsdiq edə bilər
və dövlət var, çeşidlənir.

35
00:01:47,520 --> 00:01:52,080
Və belə ki, biz sıralanır hissəsi göstərir lazımdır
bizim serialın, mavi boyayıcı.

36
00:01:52,080 --> 00:01:53,860
>> İndi biz yalnız yenidən prosesi təkrar edin.

37
00:01:53,860 --> 00:01:57,430
Biz çeşidlənməmiş hissəsi vasitəsilə axtarış
array ən kiçik element tapmaq.

38
00:01:57,430 --> 00:01:59,000
Bu halda, iki deyil.

39
00:01:59,000 --> 00:02:02,100
>> Biz ilk ilə dəyişdirmək
çeşidlənməmiş hissəsi element.

40
00:02:02,100 --> 00:02:05,540
Bu halda iki də olur
çeşidlənməmiş hissəsi ilk element.

41
00:02:05,540 --> 00:02:08,650
Belə ki, biz özü ilə iki dəyişdirmək,
həqiqətən yalnız iki yaradır

42
00:02:08,650 --> 00:02:11,257
Bu və bu sıralanır harada.

43
00:02:11,257 --> 00:02:13,840
Davam, biz vasitəsilə axtarış
kiçik element tapmaq üçün.

44
00:02:13,840 --> 00:02:15,030
Bu üç var.

45
00:02:15,030 --> 00:02:17,650
Biz ilk ilə dəyişdirmək
Beş edir element.

46
00:02:17,650 --> 00:02:19,450
İndi üç çeşidlənir.

47
00:02:19,450 --> 00:02:22,440
>> Biz yenə vasitəsilə axtarış və biz
kiçik element dörd tapa bilərsiniz.

48
00:02:22,440 --> 00:02:28,070
Biz ilk element ilə dəyişdirmək
çeşidlənməmiş hissəsi, indi dörd çeşidlənir.

49
00:02:28,070 --> 00:02:29,910
>> Biz beş olduğunu tapmaq
kiçik element.

50
00:02:29,910 --> 00:02:32,900
Biz ilk ilə dəyişdirmək
çeşidlənməmiş hissəsi element.

51
00:02:32,900 --> 00:02:34,740
İndi beş çeşidlənir.

52
00:02:34,740 --> 00:02:36,660
>> Və sonra nəhayət, bizim
çeşidlənməmiş hissəsi ibarətdir

53
00:02:36,660 --> 00:02:38,576
yalnız bir element,
belə ki, biz vasitəsilə axtarış

54
00:02:38,576 --> 00:02:41,740
və biz altı olduğunu tapmaq
kiçik və əslində, yalnız element.

55
00:02:41,740 --> 00:02:44,906
Və sonra biz bu çeşidlənir ki, olar.

56
00:02:44,906 --> 00:02:47,530
İndi biz array geçtiğinizi
tamamilə çeşidlənməmiş olan

57
00:02:47,530 --> 00:02:52,660
qırmızı, tamamilə sıralanır üçün
mavi, seçki növ istifadə.

58
00:02:52,660 --> 00:02:54,920
>> Belə ki, ən pis ssenari burada nə var?

59
00:02:54,920 --> 00:02:57,830
Yaxşı mütləq pis
halda, biz artıq baxmaq

60
00:02:57,830 --> 00:03:02,170
serialın elementləri bütün
kiçik çeşidlənməmiş element tapmaq,

61
00:03:02,170 --> 00:03:04,750
və biz təkrar var
bu proses n dəfə.

62
00:03:04,750 --> 00:03:09,090
Serialın hər bir element üçün Once
biz yalnız, çünki bu alqoritm,

63
00:03:09,090 --> 00:03:12,180
vaxt sort bir element.

64
00:03:12,180 --> 00:03:13,595
>> Ən yaxşı ssenari nədir?

65
00:03:13,595 --> 00:03:15,040
Yaxşı doğru, eyni var?

66
00:03:15,040 --> 00:03:18,440
Biz, həqiqətən, hələ gezinmek üçün var
serialın hər bir element

67
00:03:18,440 --> 00:03:22,040
üçün, bu olduğunu təsdiq etmək
əslində, kiçik element.

68
00:03:22,040 --> 00:03:26,760
>> Belə ki, ən pis halda uzunluğu, biz
bir proses n dəfə təkrar etmək lazımdır,

69
00:03:26,760 --> 00:03:28,960
n elementlərin hər biri üçün bir dəfə.

70
00:03:28,960 --> 00:03:31,940
Və ən yaxşı halda,
biz eyni var.

71
00:03:31,940 --> 00:03:35,340
>> Belə ki, geri düşüncə bizim
hesablama mürəkkəblik qutusu,

72
00:03:35,340 --> 00:03:39,250
nə düşünürsünüz pis
seçim sort üçün işi uzunluğu?

73
00:03:39,250 --> 00:03:41,840
Nə düşünürsünüz ən yaxşı
seçim sort üçün işi uzunluğu?

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

75
00:03:44,760 --> 00:03:49,325
>> N kvadrat siz Big O tahmin mi,
Böyük Omega n kvadrat?

76
00:03:49,325 --> 00:03:49,950
Siz doğru olarıq.

77
00:03:49,950 --> 00:03:52,490
Həmin, əslində,
ən pis halda və ən yaxşı halda run

78
00:03:52,490 --> 00:03:55,100
seçim sort üçün dəfə.

79
00:03:55,100 --> 00:03:56,260
>> Mən Doug Lloyd edirəm.

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

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