हेल्लो दोस्तों, आपका हमारी इस नई पोस्ट मैं स्वागत है। अब तक हमने Bubble Sort और Selection Sort जैसे basic algorithms देखे। लेकिन आज हम जिस algorithm की बात करने जा रहे हैं, वह सोर्टिंग की दुनिया का ‘Ferrari’ है। जी हाँ, हम बात कर रहे हैं Quick Sort की।
इस पोस्ट में हमने आपको क्विक सॉर्ट क्या है? (What is Quick Sort in Hindi?), Pivot का क्या role होता है? और यह बाकी algorithms से इतना तेज़ क्यों है, इसके बारे मैं विस्तार से बताया है।
अगर आप Google, Amazon जैसी कंपनियों के इंटरव्यू की तैयारी कर रहे हैं, तो यह टॉपिक आपके लिए सबसे महत्वपूर्ण है। इसीलिए इस पोस्ट को अंत तक जरूर पड़े।
What is Quick Sort in Hindi? – क्विक सॉर्ट क्या है?
Quick Sort एक बहुत ही highly efficient सोर्टिंग एल्गोरिदम है जो Divide and Conquer (बांटो और जीतो) के सिद्धांत पर काम करता है।
इसका मुख्य आईडिया यह है कि हम पूरी लिस्ट में से किसी एक नंबर को अपना ‘लीडर’ चुन लेते हैं (जिसे हम Pivot कहते हैं)। फिर हम उस लीडर से छोटे सभी नंबर्स को उसके बाईं (Left) तरफ और बड़े नंबर्स को दाईं (Right) तरफ रख देते हैं। इस प्रोसेस को Partitioning कहते हैं।
यही काम हम बार-बार छोटे हिस्सों के साथ करते हैं जब तक कि पूरी लिस्ट sort नहीं हो जाती।
Real Life Example: मान लीजिये स्कूल की असेंबली में हाइट के हिसाब से लाइन लगनी है। टीचर ने एक random बच्चे (Rahul) को खड़ा किया और कहा – “जिनकी हाइट Rahul से कम है वो लेफ्ट में खड़े हो जाओ, और जिनकी ज्यादा है वो राईट में।” बस यही Quick Sort का बेसिक फंडा है!
How Quick Sort Works in Hindi? – क्विक सॉर्ट कैसे काम करता है?
Quick Sort काम करने के लिए मुख्य रूप से 3 स्टेप्स फॉलो करता है:
- Choose a Pivot: लिस्ट में से किसी भी एक element को Pivot (केंद्र बिंदु) मान लिया जाता है। (आमतौर पर हम लास्ट element को pivot चुनते हैं)।
- Partitioning: लिस्ट को ऐसे reorder किया जाता है कि Pivot से छोटे सारे elements उसके पहले आ जाएं और बड़े elements उसके बाद।
- Recursion: अब Pivot के लेफ्ट और राईट वाली सब-लिस्ट (sub-lists) पर फिर से यही स्टेप्स apply किये जाते हैं।
Step-by-Step Example of Quick Sort
चलिए इसे एक उदाहरण से समझते हैं।
Array: [10, 80, 30, 90, 40, 50, 70]
Step 1: Pivot चुनना
हम आखिरी element 70 को Pivot मान लेते हैं।
Step 2: Partitioning (बंटवारा)
अब हम चेक करेंगे कि कौन 70 से छोटा है और कौन बड़ा।
- 10, 30, 40, 50 -> यह सब 70 से छोटे हैं (Left side आएंगे)।
- 80, 90 -> यह सब 70 से बड़े हैं (Right side आएंगे)।
New Array Structure: [10, 30, 40, 50, **70**, 90, 80]
(ध्यान दें: 70 अब अपनी सही sorted जगह पर फिक्स हो गया है)
Step 3: Recursion
अब हमारे पास दो हिस्से हैं:
- Left Part:
[10, 30, 40, 50] - Right Part:
[90, 80]
अब हम इन दोनों हिस्सों पर अलग-अलग Quick Sort लगाएंगे। और अंत में हमें पूरी sorted लिस्ट मिल जाएगी:
Sorted Array: [10, 30, 40, 50, 70, 80, 90]
Time Complexity Analysis – यह कितना फ़ास्ट है?
Quick Sort की स्पीड इस बात पर निर्भर करती है कि हम Pivot किसे चुनते हैं।
- Best Case: $O(n \log n)$
- जब Pivot हमेशा लिस्ट को दो बराबर हिस्सों में बांटता है।
- Average Case: $O(n \log n)$
- ज्यादातर cases में यह इतना ही समय लेता है। इसलिए यह बहुत fast है।
- Worst Case: $O(n^2)$
- यह तब होता है जब लिस्ट पहले से sorted हो और हम हमेशा last element को pivot चुनें। (लेकिन इसे Randomized Quick Sort से ठीक किया जा सकता है)।
Space Complexity: $O(\log n)$ (Recursion stack के कारण)।
Quick Sort vs Merge Sort in Hindi – क्विक सॉर्ट और मर्ज सॉर्ट में से कौन बेहतर है?
| Feature | Quick Sort | Merge Sort |
| Speed | यह छोटे और मध्यम डाटा के लिए Merge Sort से तेज होता है (Cache friendly होने के कारण)। | यह बहुत बड़े डाटा (Large Datasets) के लिए consistent speed देता है। |
| Memory | यह कम मेमोरी लेता है (In-place sorting)। | इसे एक्स्ट्रा मेमोरी की जरूरत होती है ($O(n)$ space)। |
| Stability | यह Unstable है (original order बदल सकता है)। | यह Stable sort है। |
| Usage | Arrays के लिए बेस्ट है। | Linked List के लिए बेस्ट है। |
Conclusion – निष्कर्ष
हमें उम्मीद है कि इस पोस्ट से आपने Quick Sort in Hindi (इसका Pivot लॉजिक और Partitioning) अच्छी तरह समझ लिया होगा। संक्षेप में कहें तो, Quick Sort एक “स्मार्ट” एल्गोरिदम है। यह कम मेमोरी लेता है और बहुत तेज काम करता है, इसीलिए ज्यादातर programming languages की default libraries (जैसे C++ में std::sort) में इसी का इस्तेमाल होता है।
अगर आपको यह लेख उपयोगी लगा हो तो इसे शेयर करें और कोडिंग प्रैक्टिस करते रहें!
FAQs
Q1. Quick Sort का Worst Case कब होता है?
Ans: जब Array पहले से ही sorted हो (ascending या descending) और हम सबसे आखिरी element को Pivot चुनें, तब यह सबसे धीमा ($O(n^2)$) काम करता है।
Q2. Pivot क्या होता है?
Ans: Pivot वह element है जिसके आधार पर हम पूरी लिस्ट को दो भागों में बांटते हैं (छोटे elements एक तरफ, बड़े दूसरी तरफ)।
Q3. क्या Quick Sort एक Stable Algorithm है?
Ans: नहीं, Quick Sort ‘Unstable’ है। यानी अगर लिस्ट में दो एक जैसे नंबर हैं (जैसे दो बार 5), तो सोर्टिंग के बाद उनका आपसी क्रम बदल सकता है।