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
Парушэнне яго да псевдокоде
мы маглі б сцвярджаць, гэты алгарытм

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
>> Вы здагадаліся Big O н квадрат,
і Вялікі Амега п квадраце?

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