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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Xin chào, tôi Đánh
Grozen-Smith, và đây là Sắp xếp nhanh.

3
00:00:10,390 --> 00:00:13,520
Cũng giống như sắp xếp chèn và bong bóng
sắp xếp, Sắp xếp nhanh là một thuật toán cho

4
00:00:13,520 --> 00:00:15,720
sắp xếp một danh sách hoặc một mảng của sự vật.

5
00:00:15,720 --> 00:00:19,080
Để đơn giản, chúng ta hãy giả sử rằng những
mọi thứ chỉ là số nguyên, nhưng

6
00:00:19,080 --> 00:00:22,060
biết rằng Sắp xếp nhanh làm việc cho
hơn chỉ số.

7
00:00:22,060 --> 00:00:24,720
QuickStart là phức tạp hơn một chút
hơn chèn hoặc bong bóng, nhưng nó

8
00:00:24,720 --> 00:00:27,560
cũng hiệu quả hơn
trong nhiều trường hợp.

9
00:00:27,560 --> 00:00:28,150
Chờ đợi một giây.

10
00:00:28,150 --> 00:00:30,760
Anh ta chỉ cần nói "nhất
trường hợp, "không phải là" tất cả "?

11
00:00:30,760 --> 00:00:31,710
Điều thú vị là không có.

12
00:00:31,710 --> 00:00:33,560
Không phải tất cả các trường hợp là như nhau.

13
00:00:33,560 --> 00:00:36,650
Đừng lo lắng về chi tiết này nếu bạn
không nhìn thấy ký hiệu O lớn, nhưng

14
00:00:36,650 --> 00:00:39,730
Sắp xếp nhanh là một O (n bình phương) thuật toán
lúc tồi tệ nhất, giống như

15
00:00:39,730 --> 00:00:41,430
chèn hay bong bóng sắp xếp.

16
00:00:41,430 --> 00:00:44,950
Tuy nhiên, nó thường hoạt động nhiều hơn nữa
như một thuật toán m tương tự cũ.

17
00:00:44,950 --> 00:00:45,750
Tại sao?

18
00:00:45,750 --> 00:00:46,810
Chúng tôi sẽ lấy lại cho rằng sau này.

19
00:00:46,810 --> 00:00:49,610
Nhưng bây giờ, chúng ta hãy tìm hiểu
Sắp xếp nhanh như thế nào hoạt động.

20
00:00:49,610 --> 00:00:53,080
>> Vì vậy, hãy đi bộ qua Quicksorting này
mảng các số nguyên từ nhỏ nhất

21
00:00:53,080 --> 00:00:54,260
để lớn nhất.

22
00:00:54,260 --> 00:01:00,110
Ở đây chúng tôi có các số nguyên 6,
5, 1, 3, 8, 4, 7, 9, và 2.

23
00:01:00,110 --> 00:01:03,480
Đầu tiên, chúng ta chọn các yếu tố cuối cùng của
mảng này - trong trường hợp này, hai -

24
00:01:03,480 --> 00:01:06,870
và gọi đó là "trục". Tiếp theo, chúng tôi
bắt đầu nhìn vào hai điều -

25
00:01:06,870 --> 00:01:10,220
một, chỉ số thấp nhất, mà tôi sẽ tham khảo
là ở bên phải của

26
00:01:10,220 --> 00:01:13,970
tường, và, hai, tận cùng bên trái
yếu tố, mà tôi sẽ gọi là "hiện tại

27
00:01:13,970 --> 00:01:17,260
yếu tố. "Những gì chúng tôi sẽ làm là
xem xét tất cả các yếu tố khác, khác

28
00:01:17,260 --> 00:01:20,930
so với trục, và đặt tất cả các yếu tố
nhỏ hơn pivot đến

29
00:01:20,930 --> 00:01:24,140
bên trái của bức tường và tất cả những
lớn hơn pivot đến

30
00:01:24,140 --> 00:01:25,570
phải bức tường.

31
00:01:25,570 --> 00:01:29,560
Sau đó, cuối cùng, chúng tôi sẽ thả các trục
ngay trên bức tường để đặt nó giữa

32
00:01:29,560 --> 00:01:32,970
tất cả các số nhỏ hơn nó
và tất cả các số lớn hơn.

33
00:01:32,970 --> 00:01:34,460
>> Vì vậy, hãy làm điều đó.

34
00:01:34,460 --> 00:01:38,540
Lấy 2, đặt tường ở
bắt đầu, và gọi 6 "hiện tại

35
00:01:38,540 --> 00:01:41,590
yếu tố. "Vì vậy, chúng tôi muốn xem xét
phần tử hiện tại của chúng tôi, 6.

36
00:01:41,590 --> 00:01:44,200
Và kể từ khi nó lớn hơn
2, chúng ta để nó ở đó cho

37
00:01:44,200 --> 00:01:45,610
phải bức tường.

38
00:01:45,610 --> 00:01:48,980
Sau đó, chúng tôi chuyển sang nhìn vào 5 như của chúng tôi
phần tử hiện tại và thấy rằng điều này

39
00:01:48,980 --> 00:01:51,840
là, một lần nữa, lớn hơn so với trục, vì vậy chúng tôi
để ở những nơi nó ở bên phải

40
00:01:51,840 --> 00:01:53,190
bên của bức tường.

41
00:01:53,190 --> 00:01:53,880
Chúng tôi di chuyển trên.

42
00:01:53,880 --> 00:01:56,750
Phần tử hiện tại của chúng tôi là
bây giờ 1, và - oh.

43
00:01:56,750 --> 00:01:58,030
Điều này khác với bây giờ.

44
00:01:58,030 --> 00:02:00,890
Các yếu tố hiện tại là nhỏ hơn
trục, vì vậy chúng tôi muốn đặt nó

45
00:02:00,890 --> 00:02:02,570
bên trái của bức tường.

46
00:02:02,570 --> 00:02:06,555
Để làm điều này, chúng ta hãy chuyển đổi
phần tử hiện tại với chỉ số thấp nhất

47
00:02:06,555 --> 00:02:07,970
ngồi ngay bên phải của bức tường.

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

49
00:02:14,050 --> 00:02:17,570
Bây giờ, chúng tôi di chuyển bức tường lên một chỉ số
vì vậy 1 là bên trái

50
00:02:17,570 --> 00:02:19,750
bên của bức tường bây giờ.

51
00:02:19,750 --> 00:02:20,310
>> Chờ đợi.

52
00:02:20,310 --> 00:02:23,450
Tôi chỉ pha trộn các yếu tố trên
phía bên phải của bức tường, đúng không?

53
00:02:23,450 --> 00:02:23,890
Đừng lo lắng.

54
00:02:23,890 --> 00:02:24,930
Đó là tốt.

55
00:02:24,930 --> 00:02:27,570
Điều duy nhất chúng tôi quan tâm bây giờ
là tất cả những yếu tố để các

56
00:02:27,570 --> 00:02:29,570
bên phải của bức tường có kích thước lớn
so với trục.

57
00:02:29,570 --> 00:02:31,760
Không có thứ tự thực tế là giả định được nêu ra.

58
00:02:31,760 --> 00:02:33,200
>> Bây giờ, trở lại để phân loại.

59
00:02:33,200 --> 00:02:35,840
Vì vậy, chúng tôi tiếp tục nhìn
phần còn lại của các yếu tố.

60
00:02:35,840 --> 00:02:39,075
Và trong trường hợp này, chúng ta thấy rằng có
không có các yếu tố khác ít hơn

61
00:02:39,075 --> 00:02:42,100
trục, vì vậy chúng tôi để lại cho họ tất cả các ngày
phía bên phải của bức tường.

62
00:02:42,100 --> 00:02:45,980
Cuối cùng, chúng tôi đến được với các yếu tố hiện tại
và thấy rằng nó là trục.

63
00:02:45,980 --> 00:02:48,830
Bây giờ, điều đó có nghĩa rằng chúng tôi có hai
phần của mảng, đầu tiên là

64
00:02:48,830 --> 00:02:51,820
nhỏ trên trục và ở phía bên trái
của bức tường, và con thứ hai

65
00:02:51,820 --> 00:02:54,500
lớn hơn pivot đến
phía bên phải của bức tường.

66
00:02:54,500 --> 00:02:57,040
Chúng tôi muốn đưa các yếu tố trục giữa
hai, và sau đó chúng ta sẽ biết

67
00:02:57,040 --> 00:03:01,000
rằng pivot là ở bên phải của nó
thức nơi được sắp xếp.

68
00:03:01,000 --> 00:03:04,980
Vì vậy, chúng tôi chuyển đổi phần tử đầu tiên trên
phía bên phải của bức tường với các trục,

69
00:03:04,980 --> 00:03:06,410
và chúng ta biết của trục
trong đúng vị trí của nó.

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

71
00:03:11,130 --> 00:03:15,650
>> Sau đó chúng ta lặp lại quá trình này cho các
subarrays trái và bên phải của trục.

72
00:03:15,650 --> 00:03:18,700
Kể từ khi mảng con cuối cùng là chỉ có một
yếu tố dài, chúng tôi biết đó là đã có

73
00:03:18,700 --> 00:03:22,480
sắp xếp bởi làm sao bạn có thể được ra khỏi
đặt hàng nếu bạn chỉ có một phần tử?

74
00:03:22,480 --> 00:03:28,860
Cho phía bên phải của mảng con, chúng tôi
thấy rằng trục là 5, và tường

75
00:03:28,860 --> 00:03:32,250
chỉ là bên trái của 6.

76
00:03:32,250 --> 00:03:34,970
Và các yếu tố hiện tại cũng
bắt đầu ra như là 6.

77
00:03:34,970 --> 00:03:36,200
Vì vậy, 6 là lớn hơn 5.

78
00:03:36,200 --> 00:03:38,590
Chúng tôi để ở những nơi đó là trên
phía bên phải của bức tường.

79
00:03:38,590 --> 00:03:41,060
Bây giờ, di chuyển trên, 3 dưới 5.

80
00:03:41,060 --> 00:03:44,160
Vì vậy, chúng tôi chuyển đổi nó với phần tử đầu tiên
vừa phải của bức tường.

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

82
00:03:47,944 --> 00:03:50,750
Bây giờ, tôi chuyển bức tường lên một.

83
00:03:50,750 --> 00:03:53,010
Bây giờ, chuyển sang 8.

84
00:03:53,010 --> 00:03:56,480
8 lớn hơn 5,
và vì vậy chúng tôi rời khỏi nó.

85
00:03:56,480 --> 00:03:58,720
4 nhỏ hơn 5, vì vậy chúng tôi chuyển đổi nó.

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

87
00:04:02,950 --> 00:04:03,570
Và trên.

88
00:04:03,570 --> 00:04:04,820
Và trên.

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

90
00:04:10,190 --> 00:04:13,670
>> Mỗi lần chúng ta lặp lại quá trình trên
bên trái và bên phải của mảng. chúng tôi

91
00:04:13,670 --> 00:04:17,010
chọn một trục và làm so sánh
và tạo ra một mức độ trái và

92
00:04:17,010 --> 00:04:18,240
subarrays ngay.

93
00:04:18,240 --> 00:04:21,500
Gọi đệ quy này sẽ tiếp tục cho đến khi
chúng tôi đạt được kết thúc khi chúng tôi đã

94
00:04:21,500 --> 00:04:25,290
phân chia các mảng tổng thể vào
chỉ subarrays chiều dài 1.

95
00:04:25,290 --> 00:04:28,060
Từ đó, chúng ta biết mảng được sắp xếp
bởi vì mỗi yếu tố có, tại

96
00:04:28,060 --> 00:04:29,330
một số điểm, là một trục.

97
00:04:29,330 --> 00:04:32,720
Nói cách khác, cho mỗi yếu tố, tất cả
các con số bên trái là ít hơn

98
00:04:32,720 --> 00:04:36,420
giá trị và tất cả các con số để các
ngay có giá trị lớn hơn.

99
00:04:36,420 --> 00:04:38,980
>> Phương pháp này hoạt động rất tốt nếu
giá trị của trục được lựa chọn là

100
00:04:38,980 --> 00:04:41,930
khoảng ở giữa
phạm vi của các giá trị danh sách.

101
00:04:41,930 --> 00:04:45,630
Điều này có nghĩa rằng, sau khi chúng tôi di chuyển
các yếu tố xung quanh, có khoảng bao nhiêu

102
00:04:45,630 --> 00:04:48,390
các yếu tố bên trái của trục
như có bên phải.

103
00:04:48,390 --> 00:04:52,380
Và tính chất chia-và-chinh phục của
Thuật toán Sắp xếp nhanh sau đó được đưa

104
00:04:52,380 --> 00:04:53,850
tận dụng tối đa.

105
00:04:53,850 --> 00:04:57,500
Điều này tạo ra một thời gian chạy của O (n log n,)
n vì chúng ta phải làm n trừ đi 1

106
00:04:57,500 --> 00:05:01,640
so sánh trên mỗi thế hệ và đăng nhập
n vì chúng ta phải phân chia danh sách

107
00:05:01,640 --> 00:05:03,210
log n lần.

108
00:05:03,210 --> 00:05:06,160
Tuy nhiên, trong trường hợp xấu nhất, điều này
thuật toán thực sự có thể là O (n

109
00:05:06,160 --> 00:05:09,850
bình phương.) Giả sử trên mỗi thế hệ,
trục chỉ để xảy ra là

110
00:05:09,850 --> 00:05:12,520
nhỏ nhất hoặc lớn nhất của
số chúng tôi đang phân loại.

111
00:05:12,520 --> 00:05:15,870
Điều này có nghĩa phá vỡ danh sách
n lần và ra n trừ đi 1

112
00:05:15,870 --> 00:05:17,690
so sánh mỗi lần duy nhất.

113
00:05:17,690 --> 00:05:20,490
Vì vậy, o n bình phương.

114
00:05:20,490 --> 00:05:22,000
>> Làm thế nào chúng ta có thể cải thiện phương pháp?

115
00:05:22,000 --> 00:05:25,100
Một cách tốt để cải thiện phương pháp này là
cắt giảm xác suất mà

116
00:05:25,100 --> 00:05:28,150
thời gian chạy là bao giờ thực sự
o n bình phương.

117
00:05:28,150 --> 00:05:31,860
Nhớ tồi tệ nhất kịch bản này, trường hợp xấu nhất
chỉ có thể xảy ra khi

118
00:05:31,860 --> 00:05:35,320
trục lựa chọn luôn luôn là cao nhất
hoặc giá trị thấp nhất trong mảng.

119
00:05:35,320 --> 00:05:38,630
Để đảm bảo điều này ít có khả năng xảy ra,
chúng ta có thể tìm thấy những trục bằng

120
00:05:38,630 --> 00:05:42,610
lựa chọn nhiều yếu tố và
lấy giá trị trung bình.

121
00:05:42,610 --> 00:05:44,650
>> Tên tôi là Mark Grozen-Smith,
và đây là CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Để đơn giản, chúng ta hãy giả sử rằng những
mọi thứ chỉ là số nguyên, nhưng

124
00:05:50,930 --> 00:05:51,970
biết rằng Quicksert -

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

126
00:05:53,160 --> 00:05:55,200
Xin lôi.

127
00:05:55,200 --> 00:06:02,000
>> Ở đây chúng tôi có các số nguyên
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Thật sao?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Không dừng lại ở đó.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: Thật sao?

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