1
00:00:00,000 --> 00:00:05,726
>> [Музички]

2
00:00:05,726 --> 00:00:08,600
Даг LLOYD: Избор вид е
алгоритам кој, како што би очекувале,

3
00:00:08,600 --> 00:00:10,470
сортира е збир на елементи.

4
00:00:10,470 --> 00:00:12,470
И алгоритам се потсетиме
е збир чекор-по-чекор

5
00:00:12,470 --> 00:00:15,260
упатства за завршување на задачата.

6
00:00:15,260 --> 00:00:17,580
>> Во селекцијата сортирате
Основната идеја е ова,

7
00:00:17,580 --> 00:00:22,080
најде најмалиот несортиран елемент и
да го додадете на крајот на Подредена листа.

8
00:00:22,080 --> 00:00:26,970
Ефикасно Што тоа не е да се изгради
на сортирана листа, еден елемент во исто време.

9
00:00:26,970 --> 00:00:29,800
Тоа се урива за да се pseudocode
ние би можеле да се наведе овој алгоритам

10
00:00:29,800 --> 00:00:34,490
како што следува, повторете го овој до
Нема несортиран елементи остануваат.

11
00:00:34,490 --> 00:00:38,660
Пребарување низ несортиран
податоци за да ја најмалата вредност,

12
00:00:38,660 --> 00:00:44,130
тогаш трампа најмалата вредност со
Првиот елемент на несортиран дел.

13
00:00:44,130 --> 00:00:47,130
>> Тоа може да помогне да се визуелизира ова,
па ајде да ги разгледаме во тоа.

14
00:00:47,130 --> 00:00:49,710
Па ова, јас се соочат, е
несортиран низа и јас сум

15
00:00:49,710 --> 00:00:53,040
што е наведено од страна покажува дека сето
на елементите се обоени црвено,

16
00:00:53,040 --> 00:00:54,420
тие се уште не се подредени.

17
00:00:54,420 --> 00:00:57,670
Ова е целиот
несортиран дел од низата.

18
00:00:57,670 --> 00:01:02,020
>> Па ајде да одиме низ чекорите на
селекција вид да се најде решение за оваа низа.

19
00:01:02,020 --> 00:01:05,296
Значи, повторно, ние ќе отидеме повторување
додека не остане без несортиран елементи.

20
00:01:05,296 --> 00:01:07,920
Ние ќе пребарување преку
податоци за да ја најмалата вредност,

21
00:01:07,920 --> 00:01:11,990
а потоа се разменуваат таа вредност со
Првиот елемент на несортиран дел.

22
00:01:11,990 --> 00:01:14,380
>> Токму сега, повторно, целиот
Низа е несортиран дел.

23
00:01:14,380 --> 00:01:16,534
Сите црвени елементи се несортиран.

24
00:01:16,534 --> 00:01:18,700
За да можеме да пребарувате преку и
наоѓаме најмалата вредност.

25
00:01:18,700 --> 00:01:20,533
Се вклучуваме во почетокот,
ние одиме до крај,

26
00:01:20,533 --> 00:01:23,630
наоѓаме најмалата вредност е еден.

27
00:01:23,630 --> 00:01:24,860
Значи, тоа е еден дел.

28
00:01:24,860 --> 00:01:29,440
А потоа и втор дел, кои се разменуваат со вредност
првиот елемент на несортиран дел,

29
00:01:29,440 --> 00:01:31,340
или првиот црвено елемент.

30
00:01:31,340 --> 00:01:34,980
>> Во овој случај тоа би било
пет, па ние се разменуваат една и пет.

31
00:01:34,980 --> 00:01:37,320
Кога ќе го направите ова, ние може
визуелно да се види дека ние сме

32
00:01:37,320 --> 00:01:41,260
преселил најмалата вредност елемент
на низата, на самиот почеток.

33
00:01:41,260 --> 00:01:43,920
Ефективно подредување тој елемент.

34
00:01:43,920 --> 00:01:47,520
>> И така ние навистина може да се потврди
и велат дека еден, се подредени.

35
00:01:47,520 --> 00:01:52,080
И така ќе укаже на подредени дел
на нашата низа, со боење тоа сино.

36
00:01:52,080 --> 00:01:53,860
>> Сега ние само го повтори овој процес одново.

37
00:01:53,860 --> 00:01:57,430
Бараме преку несортиран дел
низата да се најде најмалиот елемент.

38
00:01:57,430 --> 00:01:59,000
Во овој случај, тоа е два.

39
00:01:59,000 --> 00:02:02,100
>> Ние трампа дека со првиот
елемент на несортиран дел.

40
00:02:02,100 --> 00:02:05,540
Во овој случај, исто така, две се случува да биде
првиот елемент на несортиран дел.

41
00:02:05,540 --> 00:02:08,650
Значи ние се разменуваат две со себе,
кои, навистина, само остава две

42
00:02:08,650 --> 00:02:11,257
каде што е, и тоа е се подредени.

43
00:02:11,257 --> 00:02:13,840
Кои и понатаму продолжуваат, бараме преку
да се најде најмалиот елемент.

44
00:02:13,840 --> 00:02:15,030
Тоа е три.

45
00:02:15,030 --> 00:02:17,650
Ние го трампа со првиот
елемент, кој е пет.

46
00:02:17,650 --> 00:02:19,450
А сега три се подредени.

47
00:02:19,450 --> 00:02:22,440
>> Бараме преку повторно, и ние
најде најмалиот елемент е четири.

48
00:02:22,440 --> 00:02:28,070
Ние го трампа со првиот елемент на
несортиран дел, а сега четири се подредени.

49
00:02:28,070 --> 00:02:29,910
>> Сметаме дека е пет
најмалиот елемент.

50
00:02:29,910 --> 00:02:32,900
Ние го трампа со првиот
елемент на несортиран дел.

51
00:02:32,900 --> 00:02:34,740
А сега пет се подредени.

52
00:02:34,740 --> 00:02:36,660
>> А потоа и на крај, нашата
несортиран дел се состои

53
00:02:36,660 --> 00:02:38,576
на само еден елемент,
па ние се бара преку

54
00:02:38,576 --> 00:02:41,740
и гледаме дека шест е
најмалиот, и всушност, единствениот елемент.

55
00:02:41,740 --> 00:02:44,906
И потоа можеме да наведе дека се подредени.

56
00:02:44,906 --> 00:02:47,530
И сега ние сме вклучен нашата низа
од тоа да биде целосно вон едиции

57
00:02:47,530 --> 00:02:52,660
во црвена, целосно да се решат
со сина боја, со користење на селекција кој вид.

58
00:02:52,660 --> 00:02:54,920
>> Значи, што е најлошото сценарио во оваа ситуација?

59
00:02:54,920 --> 00:02:57,830
И во апсолутна најлош
случај, ние треба да се погледне во текот на

60
00:02:57,830 --> 00:03:02,170
сите елементи на низата да
најде најмалиот несортиран елемент,

61
00:03:02,170 --> 00:03:04,750
и ние треба да се повторува
овој процес n пати.

62
00:03:04,750 --> 00:03:09,090
Еднаш за секој елемент од низата
затоа што само во овој алгоритам,

63
00:03:09,090 --> 00:03:12,180
вид еден елемент на времето.

64
00:03:12,180 --> 00:03:13,595
>> Што е најдоброто сценарио?

65
00:03:13,595 --> 00:03:15,040
Па тоа е токму истото, нели?

66
00:03:15,040 --> 00:03:18,440
Ние всушност треба да се уште да влезете низ
секој елемент од низата

67
00:03:18,440 --> 00:03:22,040
со цел да се потврди дека тоа е,
всушност, најмалиот елемент.

68
00:03:22,040 --> 00:03:26,760
>> Па најлош случај траење, ние
треба да се повторува процесот n пати,

69
00:03:26,760 --> 00:03:28,960
еднаш за секој од n елементи.

70
00:03:28,960 --> 00:03:31,940
И во најдобар случај,
ние треба да го стори истото.

71
00:03:31,940 --> 00:03:35,340
>> Толку размислување назад кон нашите
компјутерската комплексност алатникот,

72
00:03:35,340 --> 00:03:39,250
она што мислите дека е најлошото
случај траење за избор на вид?

73
00:03:39,250 --> 00:03:41,840
Што мислите дека е најдобар
случај траење за избор на вид?

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

75
00:03:44,760 --> 00:03:49,325
>> Ми го погоди Биг О од n квадрат,
Големи и Омега на n квадрат?

76
00:03:49,325 --> 00:03:49,950
Ќе бидете во право.

77
00:03:49,950 --> 00:03:52,490
Тоа се, всушност,
најлош случај и најдобар случај бегство

78
00:03:52,490 --> 00:03:55,100
Понекогаш, за избор на вид.

79
00:03:55,100 --> 00:03:56,260
>> Јас сум Даг Лојд.

80
00:03:56,260 --> 00:03:58,600
Ова е CS50.

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