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

2
00:00:07,270 --> 00:00:10,390
>> मार्क GROZEN स्मिथ: हाय, मैं मार्क हूँ
स्मिथ 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 एक हे (एन चुकता) एल्गोरिथ्म है
सबसे पर, बस की तरह

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
मैं बस पर तत्वों को मिलाया
दीवार के दाईं ओर, मैं नहीं था?

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
में समग्र सरणी विभाजित
लंबाई 1 की बस subarrays.

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
यह हे की एक क्रम बनाता है (एन लॉग एन)
हमें क्या करना है पता माइनस 1 एन क्योंकि

106
00:04:57,500 --> 00:05:01,640
हर पीढ़ी और प्रवेश पर तुलना
हम सूची में विभाजित करने के लिए n है क्योंकि

107
00:05:01,640 --> 00:05:03,210
एन बार लॉग ऑन करें.

108
00:05:03,210 --> 00:05:06,160
हालांकि, सबसे खराब मामलों में, इस
एल्गोरिथ्म वास्तव हे (एन हो सकता है

109
00:05:06,160 --> 00:05:09,850
चुकता.) प्रत्येक पीढ़ी पर मान लीजिए,
धुरी बस इतना होना होता है

110
00:05:09,850 --> 00:05:12,520
छोटी से छोटी या की सबसे बड़ी
हम छँटाई रहे नंबर.

111
00:05:12,520 --> 00:05:15,870
इस सूची टूट मतलब होगा
बार और बनाने एन शून्य से 1 n

112
00:05:15,870 --> 00:05:17,690
तुलना हर बार.

113
00:05:17,690 --> 00:05:20,490
इस प्रकार, एन के ओ चुकता.

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
देखने का समय कभी वास्तव में है
n के ओ चुकता.

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