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
ไม่ต้องกังวลเกี่ยวกับรายละเอียดนี้ถ้าคุณ
ยังไม่เห็นสัญกรณ์โอใหญ่ แต่

14
00:00:36,650 --> 00:00:39,730
quicksort คือ O (n squared) ขั้นตอนวิธีการ
ที่เลวร้ายที่สุดเช่นเดียวกับ

15
00:00:39,730 --> 00:00:41,430
แทรกหรือฟองเรียง

16
00:00:41,430 --> 00:00:44,950
แต่ก็มักจะทำหน้าที่มากขึ้น
เช่นอัลกอริธึมอนาล็อกเก่า

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
ตอนนี้เราย้ายผนังดัชนีหนึ่ง
1 เพื่อเป็นทางด้านซ้าย

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
ฉันเพียงแค่ผสมขึ้นอยู่กับองค์ประกอบ
ด้านขวาของผนังที่ไม่ได้ I?

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
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 (n log n)
n เพราะเราต้องทำ n ลบ 1

106
00:04:57,500 --> 00:05:01,640
การเปรียบเทียบในแต่ละรุ่นและเข้าสู่ระบบ
n เพราะเรามีการแบ่งรายการ

107
00:05:01,640 --> 00:05:03,210
log n ครั้ง

108
00:05:03,210 --> 00:05:06,160
อย่างไรก็ตามในกรณีที่เลวร้ายที่สุดนี้
ขั้นตอนวิธีการสามารถจริงจะ O (n

109
00:05:06,160 --> 00:05:09,850
squared.) สมมติว่าในแต่ละรุ่น
หมุนเกิดขึ้นเพียงเพื่อที่จะเป็น

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
ดังนั้น o n-squared

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
runtime เคยจริง
o n-squared

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 สมิ ธ
และนี่คือ 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
>> ลำโพง 1: จริงเหรอ?

129
00:06:03,200 --> 00:06:04,850
>> ลำโพง 2: อย่าหยุดเพียงแค่นั้น

130
00:06:04,850 --> 00:06:06,100
>> ลำโพง 1: จริงเหรอ?

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