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