1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> ДАГ Lloyd: Так в CS50 ми дізналися про
різноманітність сортування і пошуку

3
00:00:08,900 --> 00:00:09,442
алгоритми.

4
00:00:09,442 --> 00:00:11,400
І іноді це може бути
трохи складніше тримати

5
00:00:11,400 --> 00:00:14,161
трек, який алгоритм робить.

6
00:00:14,161 --> 00:00:15,910
Ми дійсно тільки
знежирене поверхня теж

7
00:00:15,910 --> 00:00:18,740
Є багато інших пошук
і алгоритми сортування.

8
00:00:18,740 --> 00:00:21,780
Таким чином, в цьому відео давайте
просто взяти кілька хвилин

9
00:00:21,780 --> 00:00:24,980
щоб спробувати відігнати кожен алгоритм
до його основних елементів

10
00:00:24,980 --> 00:00:27,810
так що ви можете пам'ятати, найбільш
важлива інформація про них

11
00:00:27,810 --> 00:00:31,970
і бути в змозі сформулювати
відмінності, якщо це необхідно.

12
00:00:31,970 --> 00:00:34,220
>> Перший вибір роду.

13
00:00:34,220 --> 00:00:38,210
Основна ідея вибору роду
це знайти найменший елемент несортоване

14
00:00:38,210 --> 00:00:42,890
в масиві і поміняти його з
в першу чергу несортоване елемент цього масиву.

15
00:00:42,890 --> 00:00:46,620
Ми сказали, що в гіршому випадку
запустити час, що був н квадраті.

16
00:00:46,620 --> 00:00:50,060
І якщо ви хочете, щоб згадати, чому, взяти
Подивіться на вибір роду відео.

17
00:00:50,060 --> 00:00:54,560
Час роботи кращому випадку
також п квадраті.

18
00:00:54,560 --> 00:00:58,910
>> Пузир роду, ідея, що
один, щоб поміняти сусідні пари.

19
00:00:58,910 --> 00:01:01,730
Так що це ключ, який допомагає вам
запам'ятати різницю тут.

20
00:01:01,730 --> 00:01:04,920
Вибір роду є, досі,
знайти smallest-- міхур

21
00:01:04,920 --> 00:01:06,790
Сортувати поза поміняти сусідні пари.

22
00:01:06,790 --> 00:01:08,710
Ми поміняти сусідні пари
елементів, якщо вони

23
00:01:08,710 --> 00:01:12,530
вийшли з ладу, який ефективно
бульбашки великі елементи права,

24
00:01:12,530 --> 00:01:17,060
і в той же час вона також починає
для переміщення дрібних елементів вліво.

25
00:01:17,060 --> 00:01:20,180
Час виконання випадок найгіршого випадку
міхура сортування п квадраті.

26
00:01:20,180 --> 00:01:23,476
Час роботи кращому випадку
міхура сортування п.

27
00:01:23,476 --> 00:01:25,350
Тому що в цій ситуації
ми не actually--

28
00:01:25,350 --> 00:01:27,141
ми, можливо, не потрібно
робити які-небудь свопи на всіх.

29
00:01:27,141 --> 00:01:31,026
У нас є тільки зробити один
пройти через всі п елементів.

30
00:01:31,026 --> 00:01:34,600
>> У вставки роду, то
Основна ідея тут змінюється.

31
00:01:34,600 --> 00:01:36,630
Це ключове слово для вставки роду.

32
00:01:36,630 --> 00:01:39,630
Ми збираємося вийти один раз через
масив зліва направо.

33
00:01:39,630 --> 00:01:41,670
І, як ми робимо, ми
збирається перенести елементи

34
00:01:41,670 --> 00:01:46,260
ми вже бачили, щоб звільнити місце для
дрібні, що потрібно, щоб відповідати десь

35
00:01:46,260 --> 00:01:48,080
тому в цій відсортовано частини.

36
00:01:48,080 --> 00:01:51,600
Так ми будуємо відсортований масив одним
елемент, у той час, зліва направо,

37
00:01:51,600 --> 00:01:54,740
і ми переходимо речі, щоб зробити кімнату.

38
00:01:54,740 --> 00:01:58,650
Найгірший час пробіг
вставка сортування п квадраті.

39
00:01:58,650 --> 00:02:02,380
Час кращий варіант запуску є н.

40
00:02:02,380 --> 00:02:05,380
>> Злиття sort-- ключового слова
тут розділення і злиття.

41
00:02:05,380 --> 00:02:08,949
Ми розділили повний спектр Чи
це шість елементів, восьми елементів,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- ми розділили його
скоротилася вдвічі, удвічі, удвічі,

43
00:02:13,790 --> 00:02:17,720
поки у нас під масив
н однієї масивів елементів.

44
00:02:17,720 --> 00:02:19,470
Набір N Один масивів елементів.

45
00:02:19,470 --> 00:02:22,640
Отже, ми почали з одного
Масив +1000 елемент,

46
00:02:22,640 --> 00:02:26,550
і ми дістатися до точки, де ми
є 1000 масивів одноелементні.

47
00:02:26,550 --> 00:02:30,990
Тоді ми починаємо об'єднати ці суб масиви
разом в правильному порядку.

48
00:02:30,990 --> 00:02:34,860
Таким чином, ми прийняти два масиви одноелементні
і створити масив з двох елементів.

49
00:02:34,860 --> 00:02:38,180
Візьмемо два масиви двох елементів
і створити масив з чотирьох елементів

50
00:02:38,180 --> 00:02:43,900
і так далі, і так далі, поки ми не
знову відновлений один масив п елементів.

51
00:02:43,900 --> 00:02:48,410
>> Найгірший час пробіг
сортування злиттям п раз увійти н.

52
00:02:48,410 --> 00:02:52,390
У нас є п елементів, але
цей процес рекомбінуючих

53
00:02:52,390 --> 00:02:56,960
приймає увійти п кроків, щоб отримати
повернутися до повної масиву.

54
00:02:56,960 --> 00:03:01,160
У кращому випадку час виконання також п журналу
п тому що цей процес не має великого

55
00:03:01,160 --> 00:03:04,090
піклуватися, чи був масив
сортування або не починати.

56
00:03:04,090 --> 00:03:07,590
Процес той же, є
немає спосіб коротких речей вимикачів.

57
00:03:07,590 --> 00:03:11,610
Так п п увійти в гіршому випадку,
п п увійти в кращому випадку.

58
00:03:11,610 --> 00:03:13,960
>> Ми говорили про двох
алгоритми пошуку.

59
00:03:13,960 --> 00:03:16,230
Так лінійний пошук про ітерації.

60
00:03:16,230 --> 00:03:19,500
Перейдемо через масив
один раз, зліва направо,

61
00:03:19,500 --> 00:03:21,950
намагаючись знайти номер
що ми шукаємо.

62
00:03:21,950 --> 00:03:24,550
Час найгірший запустити великий виведення п.

63
00:03:24,550 --> 00:03:27,610
Це може зайняти нам ітерації
по кожній елемента

64
00:03:27,610 --> 00:03:30,660
щоб знайти елемент ми шукаємо
для, або в останній позиції,

65
00:03:30,660 --> 00:03:31,630
або не на всіх.

66
00:03:31,630 --> 00:03:34,720
Але ми не можемо підтвердити, що до тих пір,
ми дивилися на все.

67
00:03:34,720 --> 00:03:36,730
м кращому випадку, ми відразу знайти.

68
00:03:36,730 --> 00:03:41,060
Кращий випадку час пробіг
лінійний пошук омега 1.

69
00:03:41,060 --> 00:03:43,689
>> Нарешті, було бінарний пошук,
який вимагає асорті масив.

70
00:03:43,689 --> 00:03:45,605
Пам'ятайте, що це дуже
важливим фактором

71
00:03:45,605 --> 00:03:47,155
при роботі з бінарного пошуку.

72
00:03:47,155 --> 00:03:50,180
Це є необхідною умовою для допомоги it--
масив, що ви шукаєте через

73
00:03:50,180 --> 00:03:52,160
повинні бути відсортовані.

74
00:03:52,160 --> 00:03:54,500
В іншому випадку, ключове слово
це розділяй і володарюй.

75
00:03:54,500 --> 00:03:58,310
Спліт масив навпіл і
усунення половина елементів

76
00:03:58,310 --> 00:04:00,780
кожен раз, як ви пройти через.

77
00:04:00,780 --> 00:04:04,330
Через це розділяй і володарюй
і поділ речей у половині підходу,

78
00:04:04,330 --> 00:04:07,450
в гіршому випадку час виконання
бінарних пошук

79
00:04:07,450 --> 00:04:11,730
увійти н, який, по суті
краще, ніж лінійний пошук у п.

80
00:04:11,730 --> 00:04:13,570
Час кращому випадку працювати як і раніше один.

81
00:04:13,570 --> 00:04:17,010
>> Ми могли б відразу ж знайти
Перший раз ми робимо поділ, але,

82
00:04:17,010 --> 00:04:19,339
знову, пам'ятайте, що
хоча двійковий пошук

83
00:04:19,339 --> 00:04:24,030
значно краще, ніж лінійний пошук
в силу того, журнал N в порівнянні з п,

84
00:04:24,030 --> 00:04:27,110
Ви, можливо, доведеться пройти через роботу
сортування свій масив першою,

85
00:04:27,110 --> 00:04:32,010
може зробити його менш ефективним в залежності
на розмір ітерації відсортовані.

86
00:04:32,010 --> 00:04:35,250
>> Я Дуг Ллойд, це CS50.

87
00:04:35,250 --> 00:04:36,757