1
00:00:00,000 --> 00:00:05,726
>> [MUSIC CHƠI]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: sắp xếp lựa chọn là một
thuật toán đó, như bạn mong đợi,

3
00:00:08,600 --> 00:00:10,470
sắp xếp một tập các phần tử.

4
00:00:10,470 --> 00:00:12,470
Và thuật toán thu hồi
là một tập hợp các bước theo các bước

5
00:00:12,470 --> 00:00:15,260
các hướng dẫn để hoàn thành một nhiệm vụ.

6
00:00:15,260 --> 00:00:17,580
>> Trong lựa chọn sắp xếp
Ý tưởng cơ bản là điều này,

7
00:00:17,580 --> 00:00:22,080
tìm các phần tử nhỏ nhất và không được phân loại
thêm vào cuối danh sách được sắp xếp.

8
00:00:22,080 --> 00:00:26,970
Có hiệu quả những gì điều này là xây dựng
một danh sách được sắp xếp, một trong những yếu tố tại một thời điểm.

9
00:00:26,970 --> 00:00:29,800
Phá vỡ nó xuống để giả
chúng ta có thể nêu thuật toán này

10
00:00:29,800 --> 00:00:34,490
như sau, lặp lại cho đến khi
không có các yếu tố không được phân loại vẫn còn.

11
00:00:34,490 --> 00:00:38,660
Tìm kiếm thông qua các không được phân loại
dữ liệu để tìm giá trị nhỏ nhất,

12
00:00:38,660 --> 00:00:44,130
sau đó trao đổi các giá trị nhỏ nhất với các
Yếu tố đầu tiên của phần được phân loại.

13
00:00:44,130 --> 00:00:47,130
>> Nó có thể giúp hình dung này,
vì vậy chúng ta hãy nhìn vào điều này.

14
00:00:47,130 --> 00:00:49,710
Vì vậy, tôi tranh, là một
mảng được phân loại và tôi đã

15
00:00:49,710 --> 00:00:53,040
chỉ ra nó bằng cách chỉ ra rằng tất cả
của các yếu tố có màu đỏ,

16
00:00:53,040 --> 00:00:54,420
họ chưa được sắp xếp.

17
00:00:54,420 --> 00:00:57,670
Đây là toàn bộ
phần chưa phân loại của mảng.

18
00:00:57,670 --> 00:01:02,020
>> Vì vậy, chúng ta hãy đi qua các bước của
sắp xếp chọn để sắp xếp mảng này.

19
00:01:02,020 --> 00:01:05,296
Vì vậy, một lần nữa, chúng ta sẽ lặp lại
đến khi không còn những yếu tố không được phân loại vẫn còn.

20
00:01:05,296 --> 00:01:07,920
Chúng tôi đang tìm kiếm sẽ qua
dữ liệu để tìm giá trị nhỏ nhất,

21
00:01:07,920 --> 00:01:11,990
và sau đó trao đổi giá trị đó với các
Yếu tố đầu tiên của phần được phân loại.

22
00:01:11,990 --> 00:01:14,380
>> Ngay bây giờ, một lần nữa, toàn bộ
mảng là phần được phân loại.

23
00:01:14,380 --> 00:01:16,534
Tất cả các yếu tố màu đỏ là không được phân loại.

24
00:01:16,534 --> 00:01:18,700
Vì vậy, chúng tôi tìm kiếm thông qua và
chúng ta tìm giá trị nhỏ nhất.

25
00:01:18,700 --> 00:01:20,533
Chúng tôi bắt đầu từ đầu,
chúng tôi đi đến cùng,

26
00:01:20,533 --> 00:01:23,630
chúng ta tìm giá trị nhỏ nhất là, một trong.

27
00:01:23,630 --> 00:01:24,860
Vì vậy, đó là một phần một.

28
00:01:24,860 --> 00:01:29,440
Và sau đó một phần hai này, đổi giá trị đó với
các yếu tố đầu tiên của phần không được phân loại,

29
00:01:29,440 --> 00:01:31,340
hoặc các yếu tố màu đỏ đầu tiên.

30
00:01:31,340 --> 00:01:34,980
>> Trong trường hợp này mà có thể
năm, vì vậy chúng tôi trao đổi một đến năm.

31
00:01:34,980 --> 00:01:37,320
Khi chúng ta làm điều này, chúng ta có thể
trực quan thấy rằng chúng tôi đã

32
00:01:37,320 --> 00:01:41,260
di chuyển các phần tử nhỏ nhất có giá trị
của mảng, đến sự khởi đầu.

33
00:01:41,260 --> 00:01:43,920
Hiệu quả phân loại phần tử đó.

34
00:01:43,920 --> 00:01:47,520
>> Và vì vậy chúng tôi thực sự có thể xác nhận
và nhà nước mà một, được sắp xếp.

35
00:01:47,520 --> 00:01:52,080
Và vì vậy chúng tôi sẽ chỉ ra những phần được sắp xếp
các mảng của chúng tôi, bằng cách tô nó màu xanh.

36
00:01:52,080 --> 00:01:53,860
>> Bây giờ chúng ta chỉ cần lặp lại quá trình này một lần nữa.

37
00:01:53,860 --> 00:01:57,430
Chúng tôi tìm kiếm thông qua các phần chưa phân loại của
mảng để tìm các phần tử nhỏ nhất.

38
00:01:57,430 --> 00:01:59,000
Trong trường hợp này, đó là hai.

39
00:01:59,000 --> 00:02:02,100
>> Chúng tôi trao đổi rằng với sự đầu tiên
phần tử của một phần được phân loại.

40
00:02:02,100 --> 00:02:05,540
Trong trường hợp này hai cũng sẽ xảy ra là
các yếu tố đầu tiên của phần được phân loại.

41
00:02:05,540 --> 00:02:08,650
Vì vậy, chúng tôi trao đổi hai với chính nó,
mà thực sự chỉ còn hai

42
00:02:08,650 --> 00:02:11,257
nó ở đâu, và nó được sắp xếp.

43
00:02:11,257 --> 00:02:13,840
Tiếp tục, chúng tôi tìm kiếm thông qua
để tìm các phần tử nhỏ nhất.

44
00:02:13,840 --> 00:02:15,030
Đó là ba.

45
00:02:15,030 --> 00:02:17,650
Chúng tôi trao đổi nó với người đầu tiên
yếu tố, mà là năm.

46
00:02:17,650 --> 00:02:19,450
Và bây giờ ba được sắp xếp.

47
00:02:19,450 --> 00:02:22,440
>> Chúng tôi tìm kiếm thông qua một lần nữa, và chúng tôi
tìm các phần tử nhỏ nhất là bốn.

48
00:02:22,440 --> 00:02:28,070
Chúng tôi trao đổi nó với phần tử đầu tiên của
phần chưa phân loại, và bây giờ bốn được sắp xếp.

49
00:02:28,070 --> 00:02:29,910
>> Chúng tôi thấy rằng năm là
các phần tử nhỏ nhất.

50
00:02:29,910 --> 00:02:32,900
Chúng tôi trao đổi nó với người đầu tiên
phần tử của một phần được phân loại.

51
00:02:32,900 --> 00:02:34,740
Và bây giờ năm được sắp xếp.

52
00:02:34,740 --> 00:02:36,660
>> Và rồi cuối cùng, chúng tôi
phần chưa phân loại bao gồm

53
00:02:36,660 --> 00:02:38,576
chỉ là một yếu tố duy nhất,
vì vậy chúng tôi tìm kiếm thông qua

54
00:02:38,576 --> 00:02:41,740
và chúng ta thấy rằng sáu là
nhỏ nhất, và trong thực tế, chỉ có yếu tố.

55
00:02:41,740 --> 00:02:44,906
Và sau đó chúng ta có thể nói rằng nó được sắp xếp.

56
00:02:44,906 --> 00:02:47,530
Và bây giờ chúng tôi đã chuyển sang mảng của chúng tôi
từ khi được hoàn toàn không được phân loại

57
00:02:47,530 --> 00:02:52,660
màu đỏ, để sắp xếp hoàn toàn
trong xanh, sử dụng sắp xếp chọn.

58
00:02:52,660 --> 00:02:54,920
>> Vì vậy, trường hợp xấu nhất ở đây là gì?

59
00:02:54,920 --> 00:02:57,830
Vâng trong tồi tệ nhất tuyệt đối
trường hợp, chúng ta phải nhìn qua

60
00:02:57,830 --> 00:03:02,170
tất cả các yếu tố của mảng để
tìm các phần tử nhỏ nhất không được phân loại,

61
00:03:02,170 --> 00:03:04,750
và chúng ta phải lặp lại
Quá trình này n lần.

62
00:03:04,750 --> 00:03:09,090
Một lần cho mỗi phần tử của mảng
bởi vì chúng ta chỉ, trong thuật toán này,

63
00:03:09,090 --> 00:03:12,180
loại một trong những yếu tố tại thời gian.

64
00:03:12,180 --> 00:03:13,595
>> Trường hợp kịch bản tốt nhất là gì?

65
00:03:13,595 --> 00:03:15,040
Vâng nó chính xác như nhau, phải không?

66
00:03:15,040 --> 00:03:18,440
Chúng tôi thực sự phải vẫn bước qua
mỗi phần tử của mảng

67
00:03:18,440 --> 00:03:22,040
để xác nhận rằng nó là,
trong thực tế, các phần tử nhỏ nhất.

68
00:03:22,040 --> 00:03:26,760
>> Vì vậy, thời gian chạy trường hợp xấu nhất, chúng tôi
phải lặp lại một quá trình n lần,

69
00:03:26,760 --> 00:03:28,960
một lần cho mỗi nguyên tố n.

70
00:03:28,960 --> 00:03:31,940
Và trong trường hợp tốt nhất,
chúng ta phải làm như vậy.

71
00:03:31,940 --> 00:03:35,340
>> Vì vậy, suy nghĩ trở lại của chúng tôi
tính toán hộp công cụ phức tạp,

72
00:03:35,340 --> 00:03:39,250
làm những gì bạn nghĩ là tồi tệ nhất
trường hợp thời gian chạy để lựa chọn loại?

73
00:03:39,250 --> 00:03:41,840
Những gì bạn nghĩ là tốt nhất
trường hợp thời gian chạy để lựa chọn loại?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Bạn có đoán Big O của n bình phương,
và Big Omega của n bình?

76
00:03:49,325 --> 00:03:49,950
Bạn muốn được bên phải.

77
00:03:49,950 --> 00:03:52,490
Đó là, trong thực tế,
trường hợp xấu nhất và trường hợp tốt nhất chạy

78
00:03:52,490 --> 00:03:55,100
lần, sắp xếp chọn.

79
00:03:55,100 --> 00:03:56,260
>> Tôi Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Đây là CS50.

81
00:03:58,600 --> 00:04:00,279