1
00:00:00,000 --> 00:00:03,360
>> [เล่นเพลง]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: สิทธิทั้งหมดเพื่อ
การจัดเรียงฟองเป็นอัลกอริทึม

4
00:00:06,730 --> 00:00:08,730
คุณสามารถใช้ในการจัดเรียงชุดขององค์ประกอบ

5
00:00:08,730 --> 00:00:10,850
ลองมาดูที่วิธีการทำงาน

6
00:00:10,850 --> 00:00:13,240
>> ดังนั้นความคิดพื้นฐานที่อยู่เบื้องหลัง
การจัดเรียงฟองนี้

7
00:00:13,240 --> 00:00:17,340
โดยทั่วไปเราต้องการที่จะย้ายที่สูงขึ้น
องค์ประกอบโดยทั่วไปจะมีมูลค่าที่เหมาะสม

8
00:00:17,340 --> 00:00:20,340
และลดองค์ประกอบมูลค่าทั่วไป
ไปทางซ้ายในขณะที่เราคาดว่าจะได้

9
00:00:20,340 --> 00:00:23,256
เราต้องการสิ่งที่ต่ำกว่าจะเป็นที่
จุดเริ่มต้นและสิ่งที่สูงขึ้น

10
00:00:23,256 --> 00:00:24,970
จะเป็นที่สิ้นสุด

11
00:00:24,970 --> 00:00:26,130
>> เราจะทำเช่นนี้ได้อย่างไร?

12
00:00:26,130 --> 00:00:28,040
ดีในรหัส pseudocode,
เราอาจจะบอกว่าขอ

13
00:00:28,040 --> 00:00:30,320
ตั้งเคาน์เตอร์แลกเปลี่ยนที่ไม่ใช่ศูนย์ค่า

14
00:00:30,320 --> 00:00:32,570
เราจะเห็นว่าทำไมเราทำอย่างนั้นในครั้งที่สอง

15
00:00:32,570 --> 00:00:36,090
แล้วเราทำซ้ำดังต่อไปนี้
กระบวนการจนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0

16
00:00:36,090 --> 00:00:39,910
หรือจนกว่าเราทำสัญญาแลกเปลี่ยนที่ไม่ทั้งหมด

17
00:00:39,910 --> 00:00:43,170
>> รีเซ็ตเคาน์เตอร์แลกเปลี่ยนไป
0 ถ้ามันไม่ได้ 0

18
00:00:43,170 --> 00:00:46,420
แล้วมองไปที่ทุก
คู่ที่อยู่ติดกันขององค์ประกอบ

19
00:00:46,420 --> 00:00:49,550
หากทั้งสององค์ประกอบ
ไม่ได้อยู่ในการสั่งซื้อสลับพวกเขา

20
00:00:49,550 --> 00:00:51,620
และเพิ่ม 1 ถึงเคาน์เตอร์แลกเปลี่ยน

21
00:00:51,620 --> 00:00:53,870
หากคุณกำลังคิดเกี่ยวกับ
ก่อนที่คุณจะเห็นภาพนั้น

22
00:00:53,870 --> 00:00:57,471
สังเกตเห็นว่าเรื่องนี้จะย้ายที่ต่ำกว่า
องค์ประกอบมูลค่าไปทางซ้าย

23
00:00:57,471 --> 00:01:00,720
และองค์ประกอบที่มีมูลค่าสูงขึ้นไปทางขวา
ได้อย่างมีประสิทธิภาพทำสิ่งที่เราต้องการจะทำ

24
00:01:00,720 --> 00:01:03,940
ซึ่งเป็นกลุ่มผู้ที่ย้าย
ขององค์ประกอบในทางที่

25
00:01:03,940 --> 00:01:07,035
ขอเห็นภาพว่านี้
อาจมีลักษณะการใช้อาร์เรย์ของเรา

26
00:01:07,035 --> 00:01:10,504
ที่เราใช้ในการทดสอบ
จากขั้นตอนวิธีการเหล่านี้

27
00:01:10,504 --> 00:01:13,420
เรามีอาร์เรย์ที่ไม่ได้เรียงลำดับนี่อีกครั้ง
ระบุโดยทุกองค์ประกอบ

28
00:01:13,420 --> 00:01:14,840
อยู่ในสีแดง

29
00:01:14,840 --> 00:01:17,970
และเราจะตั้งเคาน์เตอร์แลกเปลี่ยนของฉัน
เป็นค่าที่ไม่ใช่ศูนย์

30
00:01:17,970 --> 00:01:20,610
ฉันเลือกโดยพลการ
1- เชิงลบก็ไม่ได้ 0

31
00:01:20,610 --> 00:01:23,840
เราต้องการที่จะทำซ้ำขั้นตอนนี้
จนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0

32
00:01:23,840 --> 00:01:26,540
นี่คือเหตุผลที่ผมตั้งการแลกของฉัน
สวนทางกับค่าบางอย่างที่ไม่ใช่ศูนย์

33
00:01:26,540 --> 00:01:29,400
เพราะมิฉะนั้น
แลกเปลี่ยนเคาน์เตอร์จะเป็น 0

34
00:01:29,400 --> 00:01:31,610
เราจะไม่ได้เริ่มต้น
กระบวนการของขั้นตอนวิธี

35
00:01:31,610 --> 00:01:33,610
ดังนั้นอีกครั้งขั้นตอน are--
รีเซ็ตเคาน์เตอร์แลกเปลี่ยน

36
00:01:33,610 --> 00:01:37,900
0 แล้วมองไปที่ทุกคนที่อยู่ติดกัน
คู่และถ้าพวกเขากำลังออกคำสั่ง

37
00:01:37,900 --> 00:01:40,514
สลับพวกเขาและเพิ่ม 1
ไปที่เคาน์เตอร์แลกเปลี่ยน

38
00:01:40,514 --> 00:01:41,680
ดังนั้นขอเริ่มต้นกระบวนการนี​​้

39
00:01:41,680 --> 00:01:44,430
ดังนั้นสิ่งแรกที่เราทำคือ
เราตั้งเคาน์เตอร์แลกเปลี่ยนเป็น 0

40
00:01:44,430 --> 00:01:46,660
และจากนั้นเราเริ่มมองหา
ในแต่ละคู่ที่อยู่ติดกัน

41
00:01:46,660 --> 00:01:49,140
>> ดังนั้นเราจึงเริ่มมองหาที่ 5 และ 2

42
00:01:49,140 --> 00:01:52,410
เรามาดูกันว่าพวกเขาจะออกจาก
สั่งซื้อและเพื่อให้เราสลับพวกเขา

43
00:01:52,410 --> 00:01:53,830
และเราเพิ่ม 1 ไปที่เคาน์เตอร์แลกเปลี่ยน

44
00:01:53,830 --> 00:01:57,860
ดังนั้นตอนนี้เคาน์เตอร์แลกเปลี่ยนของเราคือ 1,
และ 2 และ 5 ได้รับการเปลี่ยน

45
00:01:57,860 --> 00:01:59,370
ตอนนี้เราทำซ้ำขั้นตอนอีกครั้ง

46
00:01:59,370 --> 00:02:03,540
>> เรามองไปที่คู่ที่อยู่ติดกันต่อไป
1- 5 และพวกเขายังออกคำสั่ง

47
00:02:03,540 --> 00:02:06,960
ดังนั้นเราจึงสลับพวกเขาและเพิ่ม
1 ไปที่เคาน์เตอร์แลกเปลี่ยน

48
00:02:06,960 --> 00:02:08,900
จากนั้นเรามองไปที่ 5 และ 3

49
00:02:08,900 --> 00:02:13,830
พวกเขาจะออกคำสั่งเพื่อให้เราสลับ
พวกเขาและเราเพิ่ม 1 ไปที่เคาน์เตอร์แลกเปลี่ยน

50
00:02:13,830 --> 00:02:15,550
จากนั้นเรามองไปที่ 5 และ 6

51
00:02:15,550 --> 00:02:18,630
พวกเขากำลังในการสั่งซื้อเพื่อให้เราทำไม่ได้จริง
ต้องการที่จะแลกเปลี่ยนอะไรในเวลานี้

52
00:02:18,630 --> 00:02:20,250
จากนั้นเรามองที่ 6 และ 4

53
00:02:20,250 --> 00:02:24,920
พวกเขายังออกคำสั่งเพื่อให้เราสลับ
พวกเขาและเราเพิ่ม 1 ไปที่เคาน์เตอร์แลกเปลี่ยน

54
00:02:24,920 --> 00:02:26,230
>> ตอนนี้สังเกตเห็นสิ่งที่เกิดขึ้น

55
00:02:26,230 --> 00:02:29,514
เราได้ย้ายไปอยู่ที่ 6 ตลอดทางจนจบ

56
00:02:29,514 --> 00:02:32,180
ดังนั้นในการเรียงลำดับการเลือกถ้าคุณได้
วิดีโอที่เห็นสิ่งที่เราทำก็คือ

57
00:02:32,180 --> 00:02:35,290
เราจบลงด้วยการย้าย
องค์ประกอบที่เล็กที่สุดในอาคาร

58
00:02:35,290 --> 00:02:39,640
แถวเรียงเป็นหลักจาก
จากซ้ายไปขวามีขนาดเล็กที่สุดไปหามากที่สุด

59
00:02:39,640 --> 00:02:43,200
ในกรณีของการจัดเรียงฟองถ้าเรา
ต่อไปนี้ขั้นตอนวิธีการนี​​้โดยเฉพาะ

60
00:02:43,200 --> 00:02:46,720
เราจริงจะได้รับการสร้าง
แถวเรียงจากขวา

61
00:02:46,720 --> 00:02:49,100
ไปซ้ายใหญ่ไปเล็ก

62
00:02:49,100 --> 00:02:53,840
เราได้อย่างมีประสิทธิภาพฟอง 6
ค่าที่มากที่สุดทุกทางไปยังจุดสิ้นสุด

63
00:02:53,840 --> 00:02:56,165
>> และเพื่อให้เราสามารถประกาศในขณะนี้
ที่ที่มีการเรียงลำดับ

64
00:02:56,165 --> 00:02:59,130
และในอนาคตอัน iterations--
จะผ่านอาร์เรย์ again--

65
00:02:59,130 --> 00:03:01,280
เราไม่ได้มีการพิจารณา 6 อีกต่อไป

66
00:03:01,280 --> 00:03:03,850
เราจะต้องพิจารณา
องค์ประกอบที่ไม่ได้เรียงลำดับ

67
00:03:03,850 --> 00:03:06,299
เมื่อเรากำลังมองหาที่อยู่ติดกันเป็นคู่

68
00:03:06,299 --> 00:03:08,340
ดังนั้นเราจึงได้เสร็จสิ้นการอย่างใดอย่างหนึ่ง
ผ่านการจัดเรียงฟอง

69
00:03:08,340 --> 00:03:11,941
ดังนั้นตอนนี้เรากลับไปที่คำถามที่ว่า
ทำซ้ำจนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0

70
00:03:11,941 --> 00:03:13,690
ดีแลกเปลี่ยนเคาน์เตอร์
คือ 4, ดังนั้นเราจะ

71
00:03:13,690 --> 00:03:15,410
เพื่อให้ทำซ้ำขั้นตอนนี้อีกครั้ง

72
00:03:15,410 --> 00:03:19,180
>> เรากำลังจะรีเซ็ตเคาน์เตอร์แลกเปลี่ยน
0 และดูแต่ละคู่ที่อยู่ติดกัน

73
00:03:19,180 --> 00:03:21,890
ดังนั้นเราจึงเริ่มต้นด้วยการที่ 2 และ 1- พวกเขากำลัง
ออกคำสั่งเพื่อให้เราสลับพวกเขา

74
00:03:21,890 --> 00:03:23,620
และเราเพิ่ม 1 ถึงเคาน์เตอร์แลกเปลี่ยน

75
00:03:23,620 --> 00:03:25,490
2 และ 3 ที่พวกเขากำลังในการสั่งซื้อ

76
00:03:25,490 --> 00:03:27,060
เราไม่จำเป็นต้องทำอะไร

77
00:03:27,060 --> 00:03:28,420
3 และ 5 อยู่ในลำดับที่

78
00:03:28,420 --> 00:03:30,150
เราไม่จำเป็นต้องทำอะไรที่นั่น

79
00:03:30,150 --> 00:03:32,515
>> 5 และ 4 พวกเขาจะออก
การสั่งซื้อและเพื่อให้เรา

80
00:03:32,515 --> 00:03:35,130
ต้องสลับพวกเขาและเพิ่ม
1 ไปที่เคาน์เตอร์แลกเปลี่ยน

81
00:03:35,130 --> 00:03:38,880
และตอนนี้เราได้ย้ายที่ 5
องค์ประกอบที่ใหญ่ที่สุดต่อไป

82
00:03:38,880 --> 00:03:40,920
ที่ส่วนท้ายของส่วนบ้านทั่วไป

83
00:03:40,920 --> 00:03:44,360
ดังนั้นตอนนี้เราสามารถเรียกว่า
เป็นส่วนหนึ่งของส่วนที่เรียง

84
00:03:44,360 --> 00:03:47,180
>> ตอนนี้คุณกำลังมองหาที่
หน้าจอและอาจจะสามารถบอกได้

85
00:03:47,180 --> 00:03:50,130
ที่ฉันสามารถที่อาร์เรย์
จะถูกจัดเรียงในขณะนี้

86
00:03:50,130 --> 00:03:51,820
แต่เราไม่สามารถพิสูจน์ได้ว่ายัง

87
00:03:51,820 --> 00:03:54,359
เราไม่ได้มีการรับประกัน
ว่ามันเรียง

88
00:03:54,359 --> 00:03:56,900
แต่นี้เป็นที่แลกเปลี่ยน
เคาน์เตอร์จะเข้ามาเล่น

89
00:03:56,900 --> 00:03:59,060
>> ดังนั้นเราจึงได้เสร็จส่ง

90
00:03:59,060 --> 00:04:00,357
เคาน์เตอร์แลกเปลี่ยนคือ 2

91
00:04:00,357 --> 00:04:02,190
ดังนั้นเรากำลังจะทำซ้ำ
กระบวนการนี​​้อีกครั้ง

92
00:04:02,190 --> 00:04:04,290
ทำซ้ำจนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0

93
00:04:04,290 --> 00:04:05,550
รีเซ็ตเคาน์เตอร์แลกเปลี่ยนเป็น 0

94
00:04:05,550 --> 00:04:06,820
ดังนั้นเราจะตั้งค่าได้

95
00:04:06,820 --> 00:04:09,810
>> ตอนนี้ดูที่แต่ละคู่ที่อยู่ติดกัน

96
00:04:09,810 --> 00:04:11,880
นั่นคือในการสั่งซื้อที่ 1 และ 2

97
00:04:11,880 --> 00:04:13,590
2 และ 3 อยู่ในลำดับที่

98
00:04:13,590 --> 00:04:15,010
3 และ 4 อยู่ในลำดับที่

99
00:04:15,010 --> 00:04:19,250
ดังนั้น ณ จุดนี้เราได้แจ้งให้ทราบแล้วเสร็จ
กำลังมองหาที่ทุกคู่ที่อยู่ติดกัน

100
00:04:19,250 --> 00:04:22,530
แต่เคาน์เตอร์แลกเปลี่ยนยังคงเป็น 0

101
00:04:22,530 --> 00:04:25,520
>> ถ้าเราไม่ต้องเปลี่ยน
องค์ประกอบใด ๆ แล้วพวกเขา

102
00:04:25,520 --> 00:04:28,340
จะต้องอยู่ในคำสั่งโดย
อาศัยอำนาจตามความในขั้นตอนนี้

103
00:04:28,340 --> 00:04:32,000
และเพื่อประสิทธิภาพของแปลก,
ที่เรารักนักวิทยาศาสตร์คอมพิวเตอร์,

104
00:04:32,000 --> 00:04:35,560
คือตอนนี้เราสามารถประกาศ
อาร์เรย์ทั้งหมดต้อง

105
00:04:35,560 --> 00:04:38,160
จัดเรียงเพราะเราไม่ได้
ต้องสลับองค์ประกอบใด ๆ

106
00:04:38,160 --> 00:04:40,380
นั่นคือที่ดีงาม

107
00:04:40,380 --> 00:04:43,260
>> ดังนั้นสิ่งที่เป็นกรณีที่เลวร้ายที่สุด
สถานการณ์ที่มีการจัดเรียงฟอง?

108
00:04:43,260 --> 00:04:46,240
ในกรณีที่เลวร้ายที่สุดคืออาร์เรย์
ในการสั่งซื้อกลับอย่างสมบูรณ์

109
00:04:46,240 --> 00:04:49,870
และเพื่อให้เรามีฟองแต่ละ
ขององค์ประกอบที่มีขนาดใหญ่ทั้งหมด

110
00:04:49,870 --> 00:04:51,780
วิธีที่ทั่วอาร์เรย์

111
00:04:51,780 --> 00:04:55,350
และเราได้อย่างมีประสิทธิภาพนอกจากนี้ยังต้อง
ฟองทั้งหมดขององค์ประกอบเล็ก ๆ ด้านหลัง

112
00:04:55,350 --> 00:04:57,050
ทุกทางทั่วอาร์เรย์เกินไป

113
00:04:57,050 --> 00:05:01,950
ดังนั้นแต่ละองค์ประกอบ n ที่มีการย้าย
ในทุกองค์ประกอบ n อื่น ๆ

114
00:05:01,950 --> 00:05:04,102
เพื่อให้เป็นสถานการณ์กรณีที่เลวร้าย

115
00:05:04,102 --> 00:05:05,810
ในกรณีที่ดีที่สุด
สถานการณ์ที่ว่านี้คือ

116
00:05:05,810 --> 00:05:07,880
แตกต่างจากการจัดเรียงตัวเลือก

117
00:05:07,880 --> 00:05:10,040
อาร์เรย์ที่มีอยู่แล้ว
เรียงเมื่อเราไปใน

118
00:05:10,040 --> 00:05:12,550
เราไม่ได้มีเพื่อให้การใด ๆ
แลกเปลี่ยนในวันแรกผ่านไป

119
00:05:12,550 --> 00:05:14,940
ดังนั้นเราอาจจะต้องมอง
องค์ประกอบน้อยลงใช่มั้ย?

120
00:05:14,940 --> 00:05:18,580
เราไม่ได้มีการทำซ้ำนี้
ประมวลผลจำนวนครั้งมากกว่า

121
00:05:18,580 --> 00:05:19,540
>> ดังนั้นสิ่งที่หมายความว่า?

122
00:05:19,540 --> 00:05:22,390
ดังนั้นสิ่งที่สถานการณ์กรณีที่เลวร้ายที่สุด
สำหรับการจัดเรียงฟองและสิ่งที่

123
00:05:22,390 --> 00:05:25,330
สถานการณ์กรณีที่ดีที่สุดสำหรับการจัดเรียงฟอง?

124
00:05:25,330 --> 00:05:27,770
คุณคิดว่านี้หรือไม่?

125
00:05:27,770 --> 00:05:32,420
ในกรณีที่เลวร้ายที่สุดที่คุณจะต้องย้ำ
ในทุกองค์ประกอบ n n ครั้ง

126
00:05:32,420 --> 00:05:34,220
ดังนั้นกรณีที่เลวร้ายที่สุดคือการยกกำลังสอง n

127
00:05:34,220 --> 00:05:36,550
>> ถ้าอาร์เรย์เป็นอย่างดี
เรียงลำดับแม้ว่าคุณเท่านั้น

128
00:05:36,550 --> 00:05:38,580
ต้องมองไปที่แต่ละ
ขององค์ประกอบหนึ่งครั้ง

129
00:05:38,580 --> 00:05:42,670
และถ้าเคาน์เตอร์แลกเปลี่ยนยังคงเป็น 0,
ที่คุณสามารถพูดอาร์เรย์นี้จะถูกจัดเรียง

130
00:05:42,670 --> 00:05:45,780
และในกรณีที่ดีที่สุดนี้เป็น
จริงดีกว่าเลือก

131
00:05:45,780 --> 00:05:49,230
sort-- ก็โอเมก้าของ n

132
00:05:49,230 --> 00:05:50,270
>> ฉันลอยด์ดั๊ก

133
00:05:50,270 --> 00:05:52,140
นี่คือ CS50

134
00:05:52,140 --> 00:05:54,382