1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Здравейте, аз съм Марк
Grozen-Смит, и това е QUICKSORT.

3
00:00:10,390 --> 00:00:13,520
Точно като вмъкване на сортиране и балон
сортиране, QUICKSORT е алгоритъм за

4
00:00:13,520 --> 00:00:15,720
сортиране на списък или масив на нещата.

5
00:00:15,720 --> 00:00:19,080
За простота, нека приемем, че тези,
неща са просто числа, но

6
00:00:19,080 --> 00:00:22,060
Знам, че QUICKSORT работи за
повече от просто числа.

7
00:00:22,060 --> 00:00:24,720
Quickstart е малко по-сложно
от момента на вкарване или балон, но това е

8
00:00:24,720 --> 00:00:27,560
също така много по-ефективно
в повечето случаи.

9
00:00:27,560 --> 00:00:28,150
Чакай малко.

10
00:00:28,150 --> 00:00:30,760
Каза само да кажа "най-
случаи ", а не" всички "?

11
00:00:30,760 --> 00:00:31,710
Интересното е, че не.

12
00:00:31,710 --> 00:00:33,560
Не всички случаи са едни и същи.

13
00:00:33,560 --> 00:00:36,650
Не се притеснявайте за тази подробност, ако
Не съм виждал голям O нотация все още, но

14
00:00:36,650 --> 00:00:39,730
QUICKSORT е О (п квадрат) алгоритъм
в най-лошия, точно като

15
00:00:39,730 --> 00:00:41,430
вмъкване или балон вид.

16
00:00:41,430 --> 00:00:44,950
Въпреки това, обикновено действа много повече
като стара m алгоритъм аналогов.

17
00:00:44,950 --> 00:00:45,750
Защо?

18
00:00:45,750 --> 00:00:46,810
Ние ще се върнем към това по-късно.

19
00:00:46,810 --> 00:00:49,610
Но за сега, нека просто да се научат
как работи QUICKSORT.

20
00:00:49,610 --> 00:00:53,080
>> Така че нека да преминете през този Quicksorting
набор от числа от малката

21
00:00:53,080 --> 00:00:54,260
до най-големия.

22
00:00:54,260 --> 00:01:00,110
Тук имаме числата 6,
5, 1, 3, 8, 4, 7, 9, и 2.

23
00:01:00,110 --> 00:01:03,480
Първо, ние вземем крайния елемент на
този масив - в този случай, два -

24
00:01:03,480 --> 00:01:06,870
и се обадете, че "оста." След това ние
започнете да се оглеждате в две неща -

25
00:01:06,870 --> 00:01:10,220
един, най-ниската индекса, които ще се отнасят
като пребиваващи на правото на

26
00:01:10,220 --> 00:01:13,970
стената, и две, най-лявата
елемент, който ще се обадя в "ток

27
00:01:13,970 --> 00:01:17,260
елемент. "Това, което ще направя, е
гледам всички други елементи, други

28
00:01:17,260 --> 00:01:20,930
от центъра на въртене, и постави всички елементи
по-малък от въртене към

29
00:01:20,930 --> 00:01:24,140
остави на стената и всички онези,
по-голяма от въртене към

30
00:01:24,140 --> 00:01:25,570
дясно на стената.

31
00:01:25,570 --> 00:01:29,560
След това, най-накрая, ще се откажа от въртене
точно на тази стена, за да го поставиш между

32
00:01:29,560 --> 00:01:32,970
всички номера по-малки, отколкото
и всички числа, по-големи.

33
00:01:32,970 --> 00:01:34,460
>> Така че нека да направим това.

34
00:01:34,460 --> 00:01:38,540
Вземете 2, сложи на стената в
започваше, и се обадете на 6 "ток

35
00:01:38,540 --> 00:01:41,590
елемент. "Така че ние искаме да разгледаме
сегашната ни елемент, на 6.

36
00:01:41,590 --> 00:01:44,200
И тъй като това е по-голям от
2, ние го остави там до

37
00:01:44,200 --> 00:01:45,610
дясно на стената.

38
00:01:45,610 --> 00:01:48,980
След това, да преминем към погледнем в 5 като ни
текущия елемент и да видим, че това

39
00:01:48,980 --> 00:01:51,840
отново е по-голям от въртене, така че
го оставите, където тя е от дясната страна

40
00:01:51,840 --> 00:01:53,190
страна на стената.

41
00:01:53,190 --> 00:01:53,880
Продължаваме напред.

42
00:01:53,880 --> 00:01:56,750
Сегашната ни елемент е
сега 1, и - о.

43
00:01:56,750 --> 00:01:58,030
Това е различно сега.

44
00:01:58,030 --> 00:02:00,890
Настоящото елемент сега е по-малък от
на въртене, така че ние искаме да го кажем

45
00:02:00,890 --> 00:02:02,570
отляво на стената.

46
00:02:02,570 --> 00:02:06,555
За да направите това, нека просто да превключите
текущия елемент с най-нисък индекс

47
00:02:06,555 --> 00:02:07,970
седнал точно отдясно на стената.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Сега, ние се движат на стената до един форум
така че един е в ляво

50
00:02:17,570 --> 00:02:19,750
страна на стената сега.

51
00:02:19,750 --> 00:02:20,310
>> Изчакайте.

52
00:02:20,310 --> 00:02:23,450
Аз просто смесва на елементи на
дясната страна на стената, нали?

53
00:02:23,450 --> 00:02:23,890
Не се притеснявайте.

54
00:02:23,890 --> 00:02:24,930
Това е добре.

55
00:02:24,930 --> 00:02:27,570
Единственото нещо, което ни интересува за сега
е, че всички тези елементи към

56
00:02:27,570 --> 00:02:29,570
право на стената са по-големи
от оста.

57
00:02:29,570 --> 00:02:31,760
Не действителната цел се приема, все още.

58
00:02:31,760 --> 00:02:33,200
>> Сега, обратно към сортиране.

59
00:02:33,200 --> 00:02:35,840
Така че ние продължаваме да търсим най-
останалите елементи.

60
00:02:35,840 --> 00:02:39,075
И в този случай, ние виждаме, че има
няма други елементи, по-малко от

61
00:02:39,075 --> 00:02:42,100
въртене, така че можем да ги оставим всичко на
от дясната страна на стената.

62
00:02:42,100 --> 00:02:45,980
Накрая стигаме до текущия елемент
и да видим, че тя е на въртене.

63
00:02:45,980 --> 00:02:48,830
Сега, това означава, че имаме две
части от масива, първата същество

64
00:02:48,830 --> 00:02:51,820
малък на въртене и на лявата страна
на стената, и второ същество

65
00:02:51,820 --> 00:02:54,500
по-голяма от въртене към
дясната страна на стената.

66
00:02:54,500 --> 00:02:57,040
Ние искаме да се сложи на въртене елемент между
на две, а след това ние ще знаем

67
00:02:57,040 --> 00:03:01,000
че оста е в правото си
крайния сортиран място.

68
00:03:01,000 --> 00:03:04,980
Така че ние превключите в първия елемент, на базата на
дясната страна на стената с шарнир,

69
00:03:04,980 --> 00:03:06,410
и ние знаем, шарнира е
в правото си положение.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Ние след това повторете този процес за
subarrays вляво и вдясно от центъра на въртене.

72
00:03:15,650 --> 00:03:18,700
След последния subarray е само един
дълго елемент, ние знаем, че това е вече

73
00:03:18,700 --> 00:03:22,480
сортираните, защото как може да бъдат изложени на
поръчате ако сте само един елемент?

74
00:03:22,480 --> 00:03:28,860
За дясната страна на subarray, ние
се види, че оста е 5, и стената

75
00:03:28,860 --> 00:03:32,250
е току-що излезе на 6.

76
00:03:32,250 --> 00:03:34,970
И текущия елемент също
започва като 6.

77
00:03:34,970 --> 00:03:36,200
Така 6 е по-голямо от 5.

78
00:03:36,200 --> 00:03:38,590
Ние го оставите, където тя е на
дясната страна на стената.

79
00:03:38,590 --> 00:03:41,060
Сега, напред, 3 е по-малко от 5.

80
00:03:41,060 --> 00:03:44,160
Така че ние го включите с първия елемент
точно на стената.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Сега, аз се премества на стената до един.

83
00:03:50,750 --> 00:03:53,010
Сега, да преминат към 8.

84
00:03:53,010 --> 00:03:56,480
8 е по-голяма от 5,
и така ние го напусне.

85
00:03:56,480 --> 00:03:58,720
The 4 е по-малко от 5, така че ние го включите.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
И нататък.

88
00:04:03,570 --> 00:04:04,820
И нататък.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Всеки път, когато се повтаря същата процедура и
Лявата и дясната част на масива. ние

91
00:04:13,670 --> 00:04:17,010
изберете въртене и да направим сравненията
и да се създаде ново ниво на ляво и

92
00:04:17,010 --> 00:04:18,240
правилните subarrays.

93
00:04:18,240 --> 00:04:21,500
Това рекурсивно повикване ще продължи до
стигаме до края, когато ние имаме

94
00:04:21,500 --> 00:04:25,290
разделен на общия масив в
само subarrays с дължина 1.

95
00:04:25,290 --> 00:04:28,060
От там, ние знаем, масивът е сортиран
защото всеки елемент има, при

96
00:04:28,060 --> 00:04:29,330
някакъв момент, бил ос.

97
00:04:29,330 --> 00:04:32,720
С други думи, за всеки елемент, всички
Числата в ляво са по-малки

98
00:04:32,720 --> 00:04:36,420
ценности и всички номера към
нали имат по-големи стойности.

99
00:04:36,420 --> 00:04:38,980
>> Този метод работи много добре, ако
стойност на избрания Оста

100
00:04:38,980 --> 00:04:41,930
приблизително в средата
диапазон на списък ценности.

101
00:04:41,930 --> 00:04:45,630
Това би означавало, че след като ние се движат
елементи около, има толкова много

102
00:04:45,630 --> 00:04:48,390
елементи в ляво на въртене
като има надясно.

103
00:04:48,390 --> 00:04:52,380
И разделяй и владей естеството на
Тогава QUICKSORT алгоритъм е взета

104
00:04:52,380 --> 00:04:53,850
възползват напълно от.

105
00:04:53,850 --> 00:04:57,500
Това създава по време на работа на O (п влезете п)
н, защото ние трябва да направим п минус 1

106
00:04:57,500 --> 00:05:01,640
сравнения на всяко поколение и дневник
н, защото ние трябва да се разделят на списъка

107
00:05:01,640 --> 00:05:03,210
влезете N пъти.

108
00:05:03,210 --> 00:05:06,160
Въпреки това, в най-лошия случай, този
алгоритъм може действително да бъде O (N

109
00:05:06,160 --> 00:05:09,850
квадрат.) Да предположим, на всяко поколение,
шарнира просто така се случва да бъде най-

110
00:05:09,850 --> 00:05:12,520
най-малкото или най-голямото от
номера сме сортиране.

111
00:05:12,520 --> 00:05:15,870
Това би означавало да се счупи списъка
N пъти и Правене N минус 1

112
00:05:15,870 --> 00:05:17,690
сравнения всеки път.

113
00:05:17,690 --> 00:05:20,490
По този начин, о п квадрат.

114
00:05:20,490 --> 00:05:22,000
>> Как можем да подобрим метода?

115
00:05:22,000 --> 00:05:25,100
Един добър начин за подобряване на метода е
за ограничаване на вероятността, че

116
00:05:25,100 --> 00:05:28,150
по време на работа е някога действително
о п квадрат.

117
00:05:28,150 --> 00:05:31,860
Запомнете това най-лошия, най-лошия сценарий
може да се случи само когато

118
00:05:31,860 --> 00:05:35,320
въртене избран е винаги най-високите
или най-ниската стойност в масива.

119
00:05:35,320 --> 00:05:38,630
За да се гарантира, че това е по-малко вероятно да се случи,
ние можем да намерим на въртене от

120
00:05:38,630 --> 00:05:42,610
избирате множество елементи и
като средната стойност.

121
00:05:42,610 --> 00:05:44,650
>> Моето име е Марк Grozen-Smith,
и това е CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> За простота, нека приемем, че тези,
неща са просто числа, но

124
00:05:50,930 --> 00:05:51,970
Знам, че Quicksert -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
Извинете.

127
00:05:55,200 --> 00:06:02,000
>> Тук имаме числа
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Наистина ли?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Да не се спира дотук.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: Наистина ли?

131
00:06:06,100 --> 00:06:08,491