1
00:00:00,000 --> 00:00:02,826
>> [Грає музика]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> ДАГ Lloyd: Так вставки сортування інший
Алгоритм можна використовувати для сортування масиву.

4
00:00:09,370 --> 00:00:12,350
Ідея цього алгоритму
це, щоб побудувати свій відсортований масив

5
00:00:12,350 --> 00:00:19,670
в місці, переминаючись елементи з
спосіб, як ви йдете, щоб звільнити місце.

6
00:00:19,670 --> 00:00:22,240
Це трохи відрізняється
від вибору роду або міхура

7
00:00:22,240 --> 00:00:25,460
роду, наприклад, де
ми регулювання місцеположення,

8
00:00:25,460 --> 00:00:26,910
де ми робимо свопи.

9
00:00:26,910 --> 00:00:29,760
>> У цьому випадку те, що ми насправді
робите розсувні елементи

10
00:00:29,760 --> 00:00:31,390
більше, з шляху.

11
00:00:31,390 --> 00:00:34,030
Як це алгоритм
працювати в псевдокоді?

12
00:00:34,030 --> 00:00:37,646
Ну давайте просто довільно сказати, що
Перший елемент масиву сортується.

13
00:00:37,646 --> 00:00:38,770
Ми будуємо її на місці.

14
00:00:38,770 --> 00:00:42,660
>> Ми збираємося йти один елемент, у той час, і
будувати і тому перше, що ми бачимо,

15
00:00:42,660 --> 00:00:43,890
це масив один елемент.

16
00:00:43,890 --> 00:00:47,720
І за визначенням, один
елемент масиву сортується.

17
00:00:47,720 --> 00:00:50,850
>> Тоді ми будемо повторювати цей процес until--
ми будемо повторювати наступну процедуру

18
00:00:50,850 --> 00:00:52,900
поки всі елементи не сортуються.

19
00:00:52,900 --> 00:00:57,770
Подивіться на наступний несортованої елемента і
вставте його в відсортованому частини,

20
00:00:57,770 --> 00:01:01,209
шляхом зрушення необхідну кількість
елементів з шляху.

21
00:01:01,209 --> 00:01:03,750
Сподіваюся, ця візуалізація
допоможе вам побачити саме те, що

22
00:01:03,750 --> 00:01:05,980
відбувається з вставки роду.

23
00:01:05,980 --> 00:01:08,010
>> Отже, ще раз, ось наш
Весь масив несортовані,

24
00:01:08,010 --> 00:01:10,970
всі елементи відображаються в червоному кольорі.

25
00:01:10,970 --> 00:01:13,320
І давайте слідувати
кроки нашої псевдокоді.

26
00:01:13,320 --> 00:01:16,970
Перше, що ми робимо, є ми називаємо
Перший елемент масиву, відсортувати.

27
00:01:16,970 --> 00:01:20,920
Так що ми просто збираюся говорити
п'ять, ви тепер сортуються.

28
00:01:20,920 --> 00:01:24,570
>> Потім ми розглянемо на наступному
несортоване елемент масиву

29
00:01:24,570 --> 00:01:27,610
і ми хочемо, щоб вставити, що
в частині відсортовано,

30
00:01:27,610 --> 00:01:29,750
зрушуючи елементи старше.

31
00:01:29,750 --> 00:01:33,470
Так два це наступний несортоване
елемент масиву.

32
00:01:33,470 --> 00:01:36,250
Очевидно, він належить до
п'ять, так що ми збираємося зробити

33
00:01:36,250 --> 00:01:41,580
є свого роду проведе два в сторону на секунду,
перекласти п`ять над, а потім вставте дві

34
00:01:41,580 --> 00:01:43,210
до п'яти, де повинні йти.

35
00:01:43,210 --> 00:01:45,280
І тепер ми можемо сказати, що два сортується.

36
00:01:45,280 --> 00:01:48,400
>> Отже, як ви бачите, ми тільки поки
подивився на двох елементів масиву.

37
00:01:48,400 --> 00:01:50,600
Ми не дивилися на
відпочинок на всіх, але ми

38
00:01:50,600 --> 00:01:54,582
отримав ці два елементи упорядковано
Спосіб механізму перемикання.

39
00:01:54,582 --> 00:01:56,410
>> Таким чином, ми повторюємо процес знову.

40
00:01:56,410 --> 00:01:58,850
Подивіться на наступний несортоване
елемент, що одна.

41
00:01:58,850 --> 00:02:04,010
Давайте вважати, що в сторону на секунду,
перекласти все закінчилося, і покласти один

42
00:02:04,010 --> 00:02:05,570
де вона повинна йти.

43
00:02:05,570 --> 00:02:08,110
>> Знову ж, досі, ми тільки коли-небудь
подивився на один, два і п'ять.

44
00:02:08,110 --> 00:02:12,480
Ми не знаємо, що ще йде,
але ми упорядковано ці три елементи.

45
00:02:12,480 --> 00:02:16,030
>> Наступна несортоване елемент
зо три, так що ми будемо встановлювати його в сторону.

46
00:02:16,030 --> 00:02:18,200
Ми поступово зміщувати те, що ми
потрібно, який, на цей раз

47
00:02:18,200 --> 00:02:21,820
це ще не все, як і в попередньому
два випадки, це просто п'ять.

48
00:02:21,820 --> 00:02:25,440
І тоді ми будемо дотримуватися три в,
між двома і п'ятьма.

49
00:02:25,440 --> 00:02:27,849
>> Шість є наступним несортоване
елемент до масиву.

50
00:02:27,849 --> 00:02:31,140
І справді шести більше п'яти, так
ми навіть не потрібно робити які-небудь заміни.

51
00:02:31,140 --> 00:02:35,710
Ми можемо просто лавірувати шостій право на
кінець відсортованого частини.

52
00:02:35,710 --> 00:02:38,270
>> Нарешті, чотири є
Останнє несортоване елемент.

53
00:02:38,270 --> 00:02:42,060
Таким чином, ми будемо встановлювати його в сторону, перейти по
елементи, які ми повинні перенести протягом,

54
00:02:42,060 --> 00:02:43,780
а потім покласти чотирьох, де вона належить.

55
00:02:43,780 --> 00:02:46,400
А тепер подивіться, ми начебто
з усіх елементів.

56
00:02:46,400 --> 00:02:48,150
Зверніть увагу, з введенням
сортувати, у нас не було

57
00:02:48,150 --> 00:02:50,240
щоб йти вперед і назад через масив.

58
00:02:50,240 --> 00:02:54,720
Ми тільки пішли через масив
один час, і ми перейшли речі

59
00:02:54,720 --> 00:02:59,870
що ми вже стикалися в порядок
щоб звільнити місце для нових елементів.

60
00:02:59,870 --> 00:03:02,820
>> Так що в гіршому випадку
Сценарій з вставки роду?

61
00:03:02,820 --> 00:03:05,090
У гіршому разі,
масив у зворотному порядку.

62
00:03:05,090 --> 00:03:11,180
Ви повинні перейти кожного з п елементів
до н позицій, кожен раз, коли ми

63
00:03:11,180 --> 00:03:12,880
зробити вставку.

64
00:03:12,880 --> 00:03:15,720
Це багато змінюється.

65
00:03:15,720 --> 00:03:18,014
>> У кращому випадку,
Масив прекрасно відсортовані.

66
00:03:18,014 --> 00:03:20,680
І ніби як те, що відбулося
з п'ятьма і шістьма у прикладі,

67
00:03:20,680 --> 00:03:23,779
де ми могли б просто лавірувати її на
без того, щоб зробити будь-який зрушення,

68
00:03:23,779 --> 00:03:24,820
ми, по суті, що робити.

69
00:03:24,820 --> 00:03:27,560
>> Якщо уявити, що наші
Масив був один через шість,

70
00:03:27,560 --> 00:03:29,900
ми б почати з
заявивши, один сортується.

71
00:03:29,900 --> 00:03:33,300
Два приходить після одного, щоб ми могли просто
кажуть, добре, добре один і два сортуються.

72
00:03:33,300 --> 00:03:36,190
Три приходить після двох, так, добре,
один і два, і три сортуються.

73
00:03:36,190 --> 00:03:39,590
>> Ми не робимо ніяких свопи, ми
просто переміщення цю довільну лінію

74
00:03:39,590 --> 00:03:42,460
між сортуються і несортовані, як ми йдемо.

75
00:03:42,460 --> 00:03:46,646
Як ефективно, як ми це робили в прикладі,
повертаючи елементи синій, як ми далі.

76
00:03:46,646 --> 00:03:48,270
Так що в гіршому випадку виконання, то?

77
00:03:48,270 --> 00:03:51,854
Пам'ятайте, що якщо у нас є перекласти кожен з
російські елементи, можливо, N позицій,

78
00:03:51,854 --> 00:03:54,020
ми сподіваємося, що дає вам
ідея, що в гіршому випадку

79
00:03:54,020 --> 00:03:57,770
виконання є Великий О п квадраті.

80
00:03:57,770 --> 00:04:00,220
>> Якщо масив прекрасно
сортувати, все, що ми повинні зробити,

81
00:04:00,220 --> 00:04:04,480
це подивитися на кожного елемента
один раз, а потім ми зробили.

82
00:04:04,480 --> 00:04:08,440
Таким чином, в кращому випадку, це омега п.

83
00:04:08,440 --> 00:04:09,490
>> Я Дуг Ллойд.

84
00:04:09,490 --> 00:04:11,760
Це CS50.

85
00:04:11,760 --> 00:04:13,119