1
00:00:00,000 --> 00:00:05,726
>> [Мусиц плаиинг]

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

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
Бреакинг га да псеудокоду
можемо навести овај алгоритам

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
и морамо да поновимо
овај процес н пута.

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
>> Дакле најгорем случају рунтиме смо
морам да поновим процес н пута,

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

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
>> Да ли сте погодите Биг О од н на квадрат,
Велики и омега н на квадрат?

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
Ово је ЦС50.

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