अध्याय 5 में, आपने
नामक एक सरल छँटाई विधि देखी बुलबुला छँटाई. उस समय यह उल्लेख किया गया था कि
काफी बेहतर रेटिंग। यहां, आप सर्वश्रेष्ठ में से एक का एक संस्करण विकसित करेंगे: त्वरित सॉर्ट (क्विकसॉर्ट)।
त्वरित वर्गीकरण, आविष्कार और नामकरण सी.ए.आर. द्वारा। होरे, वर्तमान में उपलब्ध सर्वोत्तम सामान्य प्रयोजन वर्गीकरण एल्गोरिदम है। मैं इसे अध्याय 5 में नहीं दिखा सका क्योंकि त्वरित सॉर्ट का सर्वोत्तम कार्यान्वयन रिकर्सन पर आधारित है। हम जो संस्करण विकसित करेंगे वह वर्णों की एक श्रृंखला को क्रमबद्ध करेगा, लेकिन तर्क को किसी भी प्रकार की वस्तु को क्रमबद्ध करने के लिए अनुकूलित किया जा सकता है।
त्वरित सॉर्ट विभाजन के विचार पर आधारित है। सामान्य प्रक्रिया में एक मान का चयन करना शामिल है, जिसे तुलना करना कहा जाता है, और फिर सरणी को दो खंडों में विभाजित करना शामिल है। विभाजन मान से बड़े या उसके बराबर के सभी तत्वों को एक तरफ डाला जाता है और छोटे तत्वों को दूसरी तरफ डाला जाता है। यह प्रक्रिया प्रत्येक शेष अनुभाग के लिए तब तक दोहराई जाती है जब तक कि सरणी क्रमबद्ध न हो जाए। उदाहरण के लिए, सरणी फ़ेडासीबी को देखते हुए और तुलना के रूप में मान d का उपयोग करते हुए, त्वरित सॉर्ट का पहला पास नीचे दिखाए गए अनुसार सरणी को पुनर्व्यवस्थित करेगा:

प्रारंभिक एफ ई डी ए सी बी
मार्ग 1 बी सी ए डी ई एफ

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

QSDemo.java देखें।

त्वरित क्रमबद्ध:

• सबसे कुशल और व्यापक रूप से उपयोग किए जाने वाले वर्गीकरण एल्गोरिदम में से एक।
• सी.ए.आर. द्वारा आविष्कार किया गया। होरे.
• विभाजन की अवधारणा के आधार पर, जहां सरणी को उन अनुभागों में विभाजित किया जाता है जिन्हें पुनरावर्ती रूप से क्रमबद्ध किया जाता है।
• बबल सॉर्ट और अन्य सरल तरीकों से अधिक कुशल।

संचालन:

• तुलना मूल्य (धुरी):
• एक मान को संदर्भ (धुरी) के रूप में चुना जाता है और सरणी को उस मान के आसपास व्यवस्थित किया जाता है।
• धुरी से छोटे तत्व एक तरफ जाते हैं और बड़े तत्व दूसरी तरफ जाते हैं।
• प्रत्येक अनुभाग के लिए प्रक्रिया को पुनरावर्ती रूप से दोहराया जाता है जब तक कि सरणी पूरी तरह से क्रमबद्ध न हो जाए।

त्वरित वर्गीकरण

QSDemo