1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Chúng ta hãy xem xét lựa chọn loại, một thuật toán

2
00:00:09,980 --> 00:00:12,800
dành một danh sách các số và phân loại chúng.

3
00:00:12,800 --> 00:00:15,750
Một thuật toán, hãy nhớ, chỉ đơn giản là một bước-by-step

4
00:00:15,750 --> 00:00:18,370
thủ tục để hoàn thành một nhiệm vụ.

5
00:00:18,370 --> 00:00:21,470
Ý tưởng cơ bản đằng sau loại lựa chọn là để phân chia

6
00:00:21,470 --> 00:00:23,390
danh sách của chúng tôi thành hai phần -

7
00:00:23,390 --> 00:00:26,810
một phần được sắp xếp và một phần được phân loại.

8
00:00:26,810 --> 00:00:30,200
Tại mỗi bước của thuật toán, một số được chuyển từ

9
00:00:30,200 --> 00:00:33,800
phân loại phần phần được sắp xếp cho đến khi cuối cùng các

10
00:00:33,800 --> 00:00:35,880
toàn bộ danh sách được sắp xếp.

11
00:00:35,880 --> 00:00:38,510
Vì vậy, đây là danh sách sáu con số -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, và 15.

13
00:00:44,010 --> 00:00:47,680
Ngay bây giờ được coi là toàn bộ danh sách được phân loại.

14
00:00:47,680 --> 00:00:51,770
Mặc dù một số giống như 16 có thể đã được chính xác của nó

15
00:00:51,770 --> 00:00:56,040
vị trí, thuật toán của chúng tôi không có cách nào biết rằng cho đến khi

16
00:00:56,040 --> 00:00:57,980
toàn bộ danh sách được sắp xếp.

17
00:00:57,980 --> 00:01:01,355
Vì vậy, chúng tôi sẽ xem xét tất cả các số được được phân loại cho đến khi chúng tôi sắp xếp

18
00:01:01,355 --> 00:01:03,800
nó chính mình.

19
00:01:03,800 --> 00:01:06,890
Chúng tôi biết rằng chúng tôi muốn danh sách có thứ tự tăng dần.

20
00:01:06,890 --> 00:01:10,200
Vì vậy, chúng tôi sẽ muốn xây dựng phần sắp xếp danh sách của chúng tôi

21
00:01:10,200 --> 00:01:13,280
từ trái sang phải, nhỏ đến lớn.

22
00:01:13,280 --> 00:01:17,970
Để làm được điều đó, chúng tôi sẽ cần phải tìm thấy các yếu tố tối thiểu được phân loại

23
00:01:17,970 --> 00:01:21,350
và đặt nó ở cuối của phần được sắp xếp.

24
00:01:21,350 --> 00:01:25,370
Kể từ khi danh sách này không được sắp xếp, cách duy nhất để làm điều đó là để

25
00:01:25,370 --> 00:01:29,330
nhìn vào mỗi phần tử trong phần phân loại, ghi nhớ

26
00:01:29,330 --> 00:01:32,010
yếu tố là thấp nhất và so sánh

27
00:01:32,010 --> 00:01:33,770
mỗi yếu tố đó.

28
00:01:33,770 --> 00:01:36,150
Vì vậy, chúng tôi sẽ xem xét đầu tiên vào 23.

29
00:01:36,150 --> 00:01:38,650
Đây là yếu tố đầu tiên mà chúng tôi đã nhìn thấy, vì vậy chúng tôi sẽ nhớ

30
00:01:38,650 --> 00:01:40,050
nó như là tối thiểu.

31
00:01:40,050 --> 00:01:42,320
Tiếp theo chúng ta sẽ xem xét ở mức 42.

32
00:01:42,320 --> 00:01:46,720
42 là lớn hơn 23, do đó, 23 là tối thiểu.

33
00:01:46,720 --> 00:01:51,210
Tiếp theo là 4 mà là ít hơn 23, vì vậy chúng tôi sẽ nhớ 4

34
00:01:51,210 --> 00:01:52,880
như là tối thiểu mới.

35
00:01:52,880 --> 00:01:56,380
Tiếp theo là 16 mà là lớn hơn 4, 4

36
00:01:56,380 --> 00:01:57,980
vẫn là tối thiểu.

37
00:01:57,980 --> 00:02:03,670
8 lớn hơn 4, và 15 là lớn hơn 4, do đó, 4 phải được

38
00:02:03,670 --> 00:02:05,980
yếu tố được phân loại nhỏ nhất.

39
00:02:05,980 --> 00:02:09,350
Vì vậy, mặc dù là con người, chúng tôi ngay lập tức có thể thấy, có 4 là

40
00:02:09,350 --> 00:02:12,300
các yếu tố tối thiểu, thuật toán của chúng tôi cần phải xem xét

41
00:02:12,300 --> 00:02:15,710
tất cả các yếu tố được phân loại, ngay cả sau khi chúng tôi đã tìm thấy 4 -

42
00:02:15,710 --> 00:02:16,860
tối thiểu yếu tố.

43
00:02:16,860 --> 00:02:19,900
Vì vậy, bây giờ mà chúng tôi đã tìm thấy các yếu tố tối thiểu, 4, chúng tôi sẽ muốn

44
00:02:19,900 --> 00:02:23,410
để di chuyển nó vào phần sắp xếp danh sách.

45
00:02:23,410 --> 00:02:27,320
Vì đây là bước đầu tiên, điều này có nghĩa là chúng tôi muốn đặt 4 tại

46
00:02:27,320 --> 00:02:29,680
đầu của danh sách.

47
00:02:29,680 --> 00:02:33,040
Ngay bây giờ 23 là lúc bắt đầu của danh sách, do đó,

48
00:02:33,040 --> 00:02:36,080
chúng ta hãy trao đổi 4 và số 23.

49
00:02:36,080 --> 00:02:38,870
Vì vậy, bây giờ danh sách của chúng tôi trông như thế này.

50
00:02:38,870 --> 00:02:42,710
Chúng ta biết rằng 4 phải được ở vị trí cuối cùng của nó, bởi vì nó là

51
00:02:42,710 --> 00:02:45,890
cả hai yếu tố nhỏ nhất và yếu tố đầu

52
00:02:45,890 --> 00:02:46,960
của danh sách.

53
00:02:46,960 --> 00:02:50,650
Vì vậy, điều này có nghĩa rằng chúng ta không bao giờ cần để di chuyển nó một lần nữa.

54
00:02:50,650 --> 00:02:53,910
Vì vậy, hãy lặp lại quá trình này để thêm một yếu tố để

55
00:02:53,910 --> 00:02:55,910
sắp xếp phần của danh sách.

56
00:02:55,910 --> 00:02:58,950
Chúng ta biết rằng chúng ta không cần phải nhìn vào 4, bởi vì nó

57
00:02:58,950 --> 00:03:00,000
đã được sắp xếp.

58
00:03:00,000 --> 00:03:03,540
Vì vậy, chúng ta có thể bắt đầu từ số 42, mà chúng ta sẽ nhớ

59
00:03:03,540 --> 00:03:05,290
tối thiểu yếu tố.

60
00:03:05,290 --> 00:03:08,700
Vì vậy, tiếp theo chúng ta sẽ nhìn vào 23 ít hơn 42, vì vậy chúng tôi

61
00:03:08,700 --> 00:03:11,620
hãy nhớ 23 là mức tối thiểu mới.

62
00:03:11,620 --> 00:03:14,870
Tiếp theo, chúng ta thấy số 16 là ít hơn 23, do đó,

63
00:03:14,870 --> 00:03:16,800
16 là tối thiểu mới.

64
00:03:16,800 --> 00:03:19,720
Bây giờ chúng ta nhìn vào 8 là ít hơn 16, vì vậy

65
00:03:19,720 --> 00:03:21,130
8 là tối thiểu mới.

66
00:03:21,130 --> 00:03:25,900
Và cuối cùng 8 là ít hơn 15, vì vậy chúng tôi biết rằng 8 là một tối thiểu

67
00:03:25,900 --> 00:03:27,780
phân loại yếu tố.

68
00:03:27,780 --> 00:03:30,660
Vì vậy, điều đó có nghĩa là chúng ta nên gắn thêm 8 để sắp xếp

69
00:03:30,660 --> 00:03:32,450
phần của danh sách.

70
00:03:32,450 --> 00:03:35,990
Ngay bây giờ 4 là yếu tố duy nhất được sắp xếp, vì vậy chúng tôi muốn đặt

71
00:03:35,990 --> 00:03:38,410
sau 8 cho 4.

72
00:03:38,410 --> 00:03:41,920
Kể từ khi 42 là yếu tố đầu tiên trong phần phân loại của

73
00:03:41,920 --> 00:03:47,260
danh sách, chúng tôi sẽ muốn trao đổi 42 và 8.

74
00:03:47,260 --> 00:03:49,680
Vì vậy, bây giờ danh sách của chúng tôi trông như thế này.

75
00:03:49,680 --> 00:03:53,830
4 và 8 đại diện cho phần sắp xếp danh sách, và

76
00:03:53,830 --> 00:03:56,440
số còn lại đại diện cho các phân loại

77
00:03:56,440 --> 00:03:58,260
phần của danh sách.

78
00:03:58,260 --> 00:04:00,630
Vì vậy, chúng ta hãy tiếp tục lặp đi lặp lại khác.

79
00:04:00,630 --> 00:04:03,850
Chúng tôi bắt đầu với 23 thời gian này, vì chúng ta không cần phải nhìn vào

80
00:04:03,850 --> 00:04:05,770
4 và 8 nữa bởi vì họ đã

81
00:04:05,770 --> 00:04:07,660
đã được sắp xếp.

82
00:04:07,660 --> 00:04:10,270
16 là ít hơn 23, vì vậy chúng tôi sẽ nhớ

83
00:04:10,270 --> 00:04:12,070
16 là tối thiểu mới.

84
00:04:12,070 --> 00:04:18,149
16 là ít hơn 42, nhưng 15 là ít hơn 16, 15 phải

85
00:04:18,149 --> 00:04:20,480
tối thiểu được phân loại thành phần.

86
00:04:20,480 --> 00:04:24,580
Vì vậy, bây giờ chúng tôi muốn trao đổi 15 và 23 đến

87
00:04:24,580 --> 00:04:26,310
cung cấp cho chúng tôi danh sách này.

88
00:04:26,310 --> 00:04:30,500
Phần sắp xếp danh sách bao gồm 4, 8 và 15, và

89
00:04:30,500 --> 00:04:33,210
những yếu tố này vẫn còn được phân loại.

90
00:04:33,210 --> 00:04:36,900
Nhưng nó chỉ như vậy sẽ xảy ra rằng yếu tố được phân loại tiếp theo, 16,

91
00:04:36,900 --> 00:04:38,480
đã được sắp xếp.

92
00:04:38,480 --> 00:04:42,060
Tuy nhiên, không có cách nào cho các thuật toán của chúng tôi biết rằng 16

93
00:04:42,060 --> 00:04:45,230
là đã có trong vị trí chính xác của nó, do đó, chúng ta vẫn cần

94
00:04:45,230 --> 00:04:47,870
lặp lại chính xác cùng một quá trình.

95
00:04:47,870 --> 00:04:53,750
Vì vậy, chúng ta thấy rằng 16 là ít hơn 42, và 16 là ít hơn 23, vì vậy

96
00:04:53,750 --> 00:04:56,230
16 phải là yếu tố tối thiểu.

97
00:04:56,230 --> 00:04:59,010
Nó không thể trao đổi yếu tố này với chính nó, vì vậy chúng tôi có thể

98
00:04:59,010 --> 00:05:01,780
chỉ đơn giản là để nó ở vị trí này.

99
00:05:01,780 --> 00:05:04,660
Vì vậy, chúng ta cần phải vượt qua thêm một thuật toán của chúng tôi.

100
00:05:04,660 --> 00:05:09,370
42 là lớn hơn 23, vì vậy 23 phải là

101
00:05:09,370 --> 00:05:10,970
tối thiểu được phân loại yếu tố.

102
00:05:10,970 --> 00:05:17,410
Sau khi chúng tôi trao đổi số 23 và số 42, chúng tôi kết thúc với cuối cùng của chúng

103
00:05:17,410 --> 00:05:18,530
sắp xếp danh sách -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Chúng tôi biết 42 phải được địa điểm chính xác vì đó là

106
00:05:26,830 --> 00:05:30,210
chỉ có yếu tố còn lại, và đó là lựa chọn loại.

107
00:05:30,210 --> 00:05:32,100
Bây giờ chúng ta chính thức hóa thuật toán của chúng tôi với một số

108
00:05:32,100 --> 00:05:34,540
giả.

109
00:05:34,540 --> 00:05:37,760
Trên một dòng, chúng ta có thể thấy rằng chúng ta cần phải tích hợp trên

110
00:05:37,760 --> 00:05:39,530
mọi phần tử của danh sách.

111
00:05:39,530 --> 00:05:42,150
Ngoại trừ yếu tố cuối cùng, vì các yếu tố 1

112
00:05:42,150 --> 00:05:44,230
danh sách đã được sắp xếp.

113
00:05:44,230 --> 00:05:48,100
On line hai, chúng tôi xem xét các yếu tố đầu tiên của phân loại

114
00:05:48,100 --> 00:05:51,080
phần của danh sách để là tối thiểu, như chúng ta đã làm với chúng tôi

115
00:05:51,080 --> 00:05:53,750
Ví dụ, vì vậy chúng tôi có một cái gì đó để so sánh với.

116
00:05:53,750 --> 00:05:57,260
Dòng 3 bắt đầu một vòng lặp thứ hai mà chúng ta lặp qua

117
00:05:57,260 --> 00:05:59,170
mỗi phần tử được phân loại.

118
00:05:59,170 --> 00:06:02,150
Chúng ta biết rằng sau khi tôi lặp đi lặp lại, phần sắp xếp

119
00:06:02,150 --> 00:06:05,330
danh sách của chúng tôi phải có i yếu tố trong nó kể từ khi mỗi bước

120
00:06:05,330 --> 00:06:06,890
các loại một phần tử.

121
00:06:06,890 --> 00:06:11,770
Vì vậy, các phân loại yếu tố đầu tiên phải được ở vị trí của tôi cộng với 1.

122
00:06:11,770 --> 00:06:15,440
On line 4, chúng ta so sánh các yếu tố hiện ở mức tối thiểu

123
00:06:15,440 --> 00:06:17,750
yếu tố mà chúng tôi đã thấy cho đến nay.

124
00:06:17,750 --> 00:06:20,560
Nếu phần tử hiện tại nhỏ hơn mức tối thiểu

125
00:06:20,560 --> 00:06:23,870
phần tử, sau đó chúng ta nhớ đến yếu tố mới hiện nay

126
00:06:23,870 --> 00:06:26,250
tối thiểu trên dòng 5.

127
00:06:26,250 --> 00:06:29,900
Cuối cùng, trên các tuyến đường sáu và bảy, chúng tôi trao đổi tối thiểu

128
00:06:29,900 --> 00:06:33,080
phần tử với các yếu tố được phân loại đầu tiên, do đó

129
00:06:33,080 --> 00:06:36,990
thêm nó vào phần sắp xếp danh sách.

130
00:06:36,990 --> 00:06:40,030
Một khi chúng ta có một thuật toán, một câu hỏi quan trọng để hỏi

131
00:06:40,030 --> 00:06:43,370
mình là lập trình viên được bao lâu đã làm điều đó?

132
00:06:43,370 --> 00:06:46,970
Đầu tiên chúng ta sẽ đặt câu hỏi làm thế nào lâu cho điều này

133
00:06:46,970 --> 00:06:50,070
thuật toán để chạy trong trường hợp xấu nhất?

134
00:06:50,070 --> 00:06:51,640
Nhớ lại chúng tôi đại diện cho điều này đang chạy

135
00:06:51,640 --> 00:06:55,060
thời gian bằng các ký hiệu O lớn.

136
00:06:55,060 --> 00:06:58,650
Để xác định các yếu tố tối thiểu được phân loại,

137
00:06:58,650 --> 00:07:01,880
về cơ bản đã có để so sánh từng phần tử trong danh sách để

138
00:07:01,880 --> 00:07:04,040
mọi phần tử khác trong danh sách.

139
00:07:04,040 --> 00:07:08,430
Bằng trực giác, âm thanh này giống như một O hoạt động bình n.

140
00:07:08,430 --> 00:07:12,050
Nhìn giả của chúng tôi, chúng tôi cũng có một vòng lặp lồng vào bên trong

141
00:07:12,050 --> 00:07:14,420
một vòng lặp, mà thực sự âm thanh như một O

142
00:07:14,420 --> 00:07:16,480
hoạt động bình n.

143
00:07:16,480 --> 00:07:19,250
Tuy nhiên, hãy nhớ rằng chúng tôi không cần phải xem qua

144
00:07:19,250 --> 00:07:23,460
toàn bộ danh sách khi xác định các yếu tố tối thiểu được phân loại?

145
00:07:23,460 --> 00:07:26,600
Một khi chúng ta biết rằng 4 đã được sắp xếp, ví dụ, chúng tôi đã không

146
00:07:26,600 --> 00:07:28,170
cần phải nhìn vào nó một lần nữa.

147
00:07:28,170 --> 00:07:31,020
Vì vậy, thực hiện điều này thấp hơn thời gian chạy?

148
00:07:31,020 --> 00:07:34,510
Đối với danh sách của chúng tôi có chiều dài 6, chúng tôi cần thiết để làm cho 5

149
00:07:34,510 --> 00:07:37,990
so sánh các yếu tố đầu tiên, bốn so sánh cho

150
00:07:37,990 --> 00:07:40,750
Yếu tố thứ hai, và như vậy.

151
00:07:40,750 --> 00:07:44,690
Điều đó có nghĩa là tổng số của các bước là tổng của

152
00:07:44,690 --> 00:07:49,160
các số nguyên từ 1 đến chiều dài của danh sách trừ đi 1.

153
00:07:49,160 --> 00:07:51,005
Chúng tôi có thể đại diện cho điều này với một tổng kết.

154
00:07:57,980 --> 00:07:59,910
Chúng tôi sẽ không đi vào summations ở đây.

155
00:07:59,910 --> 00:08:04,900
Nhưng nó quay ra rằng tổng kết này là bằng n lần

156
00:08:04,900 --> 00:08:07,540
n trừ đi 1 trên 2.

157
00:08:07,540 --> 00:08:14,220
Hoặc tương đương, n bình phương hơn 2 trừ đi n hơn 2.

158
00:08:14,220 --> 00:08:18,860
Khi nói về thời gian chạy tiệm cận, điều này hạn bình n

159
00:08:18,860 --> 00:08:22,070
sẽ chi phối hạn n.

160
00:08:22,070 --> 00:08:27,850
Vì vậy, lựa chọn loại O n bình phương.

161
00:08:27,850 --> 00:08:31,460
Nhớ lại rằng trong ví dụ của chúng tôi, lựa chọn loại vẫn cần thiết để

162
00:08:31,460 --> 00:08:33,850
kiểm tra xem một số đã được đã được sắp xếp

163
00:08:33,850 --> 00:08:35,450
cần thiết để được di chuyển.

164
00:08:35,450 --> 00:08:38,929
Vì vậy, đó có nghĩa là nếu chúng ta chạy lựa chọn Sắp xếp trên một đã

165
00:08:38,929 --> 00:08:43,070
sắp xếp danh sách, nó sẽ yêu cầu số lượng tương tự các bước như

166
00:08:43,070 --> 00:08:46,340
sẽ khi chạy trên một danh sách hoàn toàn được phân loại.

167
00:08:46,340 --> 00:08:51,470
Vì vậy, lựa chọn loại có hiệu suất trường hợp tốt nhất của n bình phương,

168
00:08:51,470 --> 00:08:56,820
mà chúng tôi đại diện với omega n bình phương.

169
00:08:56,820 --> 00:08:58,600
Và đó là nó để sắp xếp lựa chọn.

170
00:08:58,600 --> 00:09:00,630
Chỉ là một trong rất nhiều các thuật toán chúng ta có thể

171
00:09:00,630 --> 00:09:02,390
sử dụng để sắp xếp một danh sách.

172
00:09:02,390 --> 00:09:05,910
Tên tôi là Tommy, và điều này là CS50.