मार्क GROZEN स्मिथ: हाय, मैं मार्क हूँ स्मिथ Grozen, और इस quicksort है. बस सम्मिलन सॉर्ट और बुलबुले की तरह सॉर्ट, quicksort के लिए एक एल्गोरिथ्म है एक सूची या चीजों की एक सरणी छँटाई. सादगी के लिए, चलो मान लेते हैं कि उन बातें सिर्फ पूर्णांक हैं, लेकिन quicksort के लिए काम करता है बस संख्या से अधिक है. Quickstart थोड़ा और अधिक जटिल है से सम्मिलन या बुलबुला, लेकिन यह बात है यह भी बहुत अधिक कुशल ज्यादातर मामलों में. एक मिनट रुको. वह सिर्फ "सबसे कहा था मामलों, "नहीं" सब "? दिलचस्प है, नहीं. नहीं सभी मामलों में ही हैं. इस विस्तार के बारे में चिंता मत करो तुम अगर अभी तक बड़ी हे संकेतन देखा, लेकिन नहीं है Quicksort एक हे (एन चुकता) एल्गोरिथ्म है सबसे पर, बस की तरह सम्मिलन या बुलबुला तरह. हालांकि, यह आम तौर पर बहुत अधिक कार्य करता है एक पुरानी एनालॉग मीटर एल्गोरिथ्म की तरह. क्यों? हम बाद में वापस करने के लिए मिल जाएगा. लेकिन अब के लिए, चलो बस सीख देना quicksort कैसे काम करता है. 

तो चलो इस Quicksorting के माध्यम से चलना छोटी से पूर्णांकों की सरणी सबसे बड़ा करने के लिए. यहाँ हम, पूर्णांकों 6 5, 1, 3, 8, 4, 7, 9, और 2. सबसे पहले, हम अंतिम तत्व की उठाओ इस सरणी - इस मामले में, दो - और कहा कि "धुरी कहते हैं." अगला, हम दो चीजों को देखने के लिए शुरू - एक, मैं उल्लेख करता हूँ जो सबसे कम सूचकांक करने के अधिकार के लिए रहने के रूप में दीवार, और, दो, सबसे बाएँ मैं "वर्तमान फोन करता हूँ जो तत्व, तत्व. "हम क्या करने जा रहे है अन्य सभी अन्य तत्वों, देखो धुरी से, और सभी तत्वों डाल धुरी से छोटी दीवार के बाएँ और उन सभी धुरी से बड़ा दीवार की सही. फिर, अंत में, हम धुरी छोड़ देंगे सही के बीच इसे लगाने के लिए कि दीवार पर यह तुलना में छोटे सभी नंबरों और सभी नंबरों बड़ा. 

तो चलो करते हैं. 2 उठाओ, पर दीवार डाल शुरुआत, और 6 "वर्तमान कॉल तत्व. "तो हम देखना चाहता हूँ हमारे वर्तमान तत्व, 6. और यह की तुलना में बड़ा है, क्योंकि 2, हम करने के लिए वहाँ छोड़ दें दीवार की सही. फिर, हम के रूप में 5 को देखने के लिए आगे बढ़ना हमारे वर्तमान तत्व और देखना है कि इस , फिर से, है धुरी से बड़ा है, तो हम यह सही पर है, जहां इसे छोड़ दीवार की ओर. हम पर चलते हैं. हमारे वर्तमान तत्व है अब 1, और - ओह. यह अब अलग है. वर्तमान तत्व अब से छोटी है धुरी है, इसलिए हम यह करना चाहते हैं दीवार के बाईं ओर. ऐसा करने के लिए, चलो बस स्विच करें सबसे कम सूचकांक के साथ वर्तमान तत्व सिर्फ दीवार के अधिकार के लिए बैठे. अब, हम एक सूचकांक दीवार स्थानांतरित तो 1 पर छोड़ दिया है अब दीवार की ओर. 

रुको. मैं बस पर तत्वों को मिलाया दीवार के दाईं ओर, मैं नहीं था? चिंता मत करो. यह ठीक है. हम अब के लिए देखभाल के बारे में ही बात है कि इन सभी तत्वों दीवार की सही कर रहे हैं बड़ा धुरी से. कोई वास्तविक आदेश अभी तक माना जाता है. 

अब, वापस छँटाई करने के लिए. इसलिए हम देख रहे हैं पर जारी तत्वों के बाकी. और इस मामले में, हम देखते हैं कि वहाँ की तुलना में कोई अन्य तत्व कम धुरी, तो हम पर उन सब को छोड़ दीवार के दाईं ओर. अंत में, हम वर्तमान तत्व के लिए मिल और यह धुरी है कि देखते हैं. अब, कि हम दो मतलब है कि सरणी, पहला किया जा रहा है वर्गों धुरी पर और बाईं ओर छोटे दीवार, और दूसरे की जा रही है धुरी से बड़ा दीवार के दाईं ओर. हम दोनों के बीच धुरी तत्व डाल करना चाहते हैं दो, और फिर हम पता चल जाएगा धुरी अपने अधिकार में है कि अंतिम छांटी गई जगह. इसलिए हम पर पहले तत्व स्विच धुरी के साथ दीवार के दाईं ओर, और हम जानते हैं कि धुरी है इसकी सही स्थिति में. 

हम तो के लिए इस प्रक्रिया को दोहराने subarrays छोड़ दिया और धुरी का अधिकार. पिछले subarray केवल एक है तत्व लंबे, हम पहले से ही जानते हैं सॉर्ट किया गया है कि कैसे आप से बाहर हो सकता है क्योंकि आप केवल एक ही तत्व कर रहे हैं आदेश? Subarray के दाईं ओर के लिए, हम धुरी दीवार 5 है, और देखते हैं कि सिर्फ 6 के लिए छोड़ दिया है. और वर्तमान तत्व भी 6 के रूप में शुरू होता है. तो 6 5 से अधिक है. यह पर है जहां हम इसे छोड़ दीवार के दाईं ओर. अब, पर चलती है, 3 से 5 से कम है. इसलिए हम पहले तत्व के साथ यह स्विच दीवार के लिए सिर्फ सही. अब, मैं एक दीवार में ले जाया गया. अब, 8 पर जाने से. 8, 5 से अधिक है और इसलिए हम इसे छोड़ दें. 4 कम से कम 5 है, तो हम यह स्विच. और पर. और पर. 

हम पर इस प्रक्रिया को दोहराने हर बार सरणी के बाएँ और दाएँ पक्ष. हम एक धुरी का चयन और तुलना करते हैं और छोड़ दिया की एक और स्तर बना सकते हैं और सही subarrays. इस पुनरावर्ती कॉल तक जारी रहेगा हम हम है जब अंत तक पहुँचने में समग्र सरणी विभाजित लंबाई 1 की बस subarrays. वहाँ से, हम सरणी सॉर्ट किया जाता है पता हर तत्व है, क्योंकि में कुछ बिंदु, एक धुरी गया. दूसरे शब्दों में, हर तत्व के लिए, सभी बाईं ओर संख्या कम कर रहे हैं मूल्यों और करने के लिए सभी नंबरों सही अधिक से अधिक मूल्य नहीं है. 

यह विधि बहुत अच्छी तरह से काम करता है चुना धुरी का मूल्य है लगभग बीच में सूची मानों की श्रेणी. हम ले जाने के बाद यह मतलब होगा कि के रूप में कई के बारे में वहाँ के आसपास तत्वों, धुरी के बाईं ओर तत्वों सही करने के लिए वहाँ के रूप में. और के विभाजन और विजय प्रकृति Quicksort एल्गोरिथ्म तो लिया जाता है का पूरा फायदा. यह हे की एक क्रम बनाता है (एन लॉग एन) हमें क्या करना है पता माइनस 1 एन क्योंकि हर पीढ़ी और प्रवेश पर तुलना हम सूची में विभाजित करने के लिए n है क्योंकि एन बार लॉग ऑन करें. हालांकि, सबसे खराब मामलों में, इस एल्गोरिथ्म वास्तव हे (एन हो सकता है चुकता.) प्रत्येक पीढ़ी पर मान लीजिए, धुरी बस इतना होना होता है छोटी से छोटी या की सबसे बड़ी हम छँटाई रहे नंबर. इस सूची टूट मतलब होगा बार और बनाने एन शून्य से 1 n तुलना हर बार. इस प्रकार, एन के ओ चुकता. 

हम कैसे विधि में सुधार कर सकते हैं? विधि में सुधार करने के लिए एक अच्छा तरीका है संभावना में कटौती करने के लिए कि देखने का समय कभी वास्तव में है n के ओ चुकता. यह सबसे खराब, सबसे बुरी स्थिति याद रखें तभी हो सकता है जब चुना धुरी हमेशा सर्वोच्च है या सरणी में सबसे कम मूल्य. ऐसा होने की संभावना कम होती है यह सुनिश्चित करने के लिए, हम से धुरी पा सकते हैं कई तत्वों और चुनने औसत मूल्य ले रही है. 

मेरा नाम मार्क Grozen स्मिथ है और इस CS50 है. 

सादगी के लिए, चलो मान लेते हैं कि उन बातें सिर्फ पूर्णांक हैं, लेकिन कि Quicksert पता है - Quicksert? माफ़ कीजिए. 

यहाँ हम पूर्णांकों है 6, 5, 1, 3, 8, 4, 9. 

स्पीकर 1: सच में? 

अध्यक्ष 2: वहाँ रोक नहीं है. 

स्पीकर 1: सच में?