एक कार्यक्रम विधि रूपमा Quicksort

1960 मा, K. ए Hoar, जानकारी तीव्र क्रमबद्धमा लागि विधि विकसित सबै भन्दा प्रसिद्ध भए। आज यो सकारात्मक गुण धेरै छ रूपमा, कार्यक्रम मा व्यापक प्रयोग गरिन्छ: यो सामान्य अवस्थामा लागि प्रयोग गर्न सकिन्छ, यो थप स्मृति एउटा सानो वृद्धि, सूचीहरू विभिन्न प्रकारका उपयुक्त र लागू गर्न सजिलो आवश्यक छ। प्रयोग काम गल्ती धेरै अनुमति, र यो केहि अस्थिर छ: तर जो छ Quicksort, कमियां छन्।

तर, यो सबै भन्दा अध्ययन संस्करण हो। पहिलो भुक्तानी Hoare पछि, धेरै यसको बाक्लो अध्ययन गर्छन्। ठूलो आधार empirical प्रमाण द्वारा underpinned छ जो काम, मा खर्च समय फेला को सैद्धान्तिक प्रश्नहरू मा स्थापित भएको थियो। त्यहाँ आधारभूत अल्गोरिदम र वृद्धि गति सुधार वास्तविक प्रस्ताव थियो।

Quicksort चारैतिर पाउन सकिन्छ, धेरै साधारण छ। यसको आधारमा विधि TList.Sort, सबै संस्करण (बाहेक 1) डेल्फी, समय को पुस्तकालयको समारोह यो सी मा पूरा गर्न, qsort ++ लिए मा वर्तमान कार्यान्वयन गरिएको छ।

सञ्चालनको आधारभूत सिद्धान्त एक "भाग र विजयी" को रूपमा formulated गर्न सकिन्छ। यो दुई समूह मा सूची तोडने आउँछ र आफै द्वारा प्रत्येक भाग को लागि हल। एक आधार तत्व निर्धारण गरिन्छ र अपेक्षाकृत आफ्नो सम्पूर्ण सूची पुनर्व्यवस्थित छ: यसलाई अझ बढी ध्यान जुदाई प्रक्रिया, निम्नलिखित हुन्छ जो समयमा भुक्तान कि हुनुपर्छ निम्नानुसार। उम्मेदवारको एक समूह को बायाँ निर्मित, मान जो सबै अन्य स्थानान्तरण नियम भन्दा कम छ। यो क्रमबद्ध सूची मा मुख्य तत्व यसको वैध स्थानमा छ कि बाहिर जान्छ। अर्को चरण - एक चुनौती आधार सापेक्षित तत्व दुवै पक्षलाई लागि दोहोरिने क्रमबद्धमा कार्यहरु। यो कि क्रमबद्ध गर्न छ, प्रक्रिया सूचीमा केवल एक तत्त्व समावेश भने मात्र काम गर्छ समाप्त हुन्छ। यसरी, एउटा द्रुत क्रमबद्ध रूपमा कार्यक्रम समारोह मास्टर गर्न, यो आवश्यक कम-स्तर एल्गोरिदम काम थाहा छ: क) आधार सदस्य को विकल्प; ख) सानो र ठूलो मान दुई सेट उत्पादन गर्न सबैभन्दा प्रभावकारी क्रमवय सूची।

पहिलो सिद्धान्त Familiarize। जब आधार सदस्य छनौट, आदर्श औसत सूचीबाट चयन गर्नुपर्छ। त्यसपछि ब्रेक मा दुई बराबर आधा विभाजन गरिएको छ। बस गणना औसत मूल्य सूचीमा धेरै गाह्रो छ, त्यसैले पनि तेज क्रमबद्धमा यो कलन पक्ष bypasses। तर अधिकतम वा न्यूनतम मूल्य संग आधारभूत तत्व को विकल्प - पनि छैन सबै भन्दा राम्रो विकल्प। मामला मा एक यस्तो अठोट सिर्जना खाली सूची प्रत्याभूति गरिनेछ, र दोस्रो पूर्ण। यसैले आधार सदस्यको रूपमा औसत नजिक छ कि एक रोज्नु पर्छ भनेर, तर अधिकतम र न्यूनतम मा निष्कर्षमा।

एक विकल्प निर्धारित भएपछि, तपाईं गर्न अपघटन अल्गोरिदम अगाडि बढ्न सक्छ। यो द्रुत क्रमबद्ध भित्री लूपहरूको तथाकथित। सबै दुई र्यापिड पहुँच indexes मा निर्माण गरिएको छ: पहिलो बायाँ दायाँ देखि, सही, दोस्रो बायाँबाट विपरीत तत्व अधिक जानुहोस्। सुरु सञ्चालनको कार्यान्वयन अधिकार: सूचकांक सूचीमा छ र मुख्य सबै मानहरू तुलना गर्नुहोस्। तत्व को आधारलाइन भन्दा कम वा बराबर छ जब चक्र पूरा हुन्छ। भन्ने एक तुलना छ र सूचकांक को मूल्य घट्ने छ। बायाँ हातमा जब काम भन्दा बढी वा बराबर मूल्य ठूलो समाप्त भयो। यहाँ, को तुलना मूल्य बढ्छ।

quicksort comprises जो विभाजन अल्गोरिदम यस चरण मा, दुई परिस्थिति उत्पन्न हुन सक्छ। पहिलो बाँया मा सूचकांक सही भन्दा कम छ भन्ने छ। यो त्रुटि संकेत, त्यसपछि त्यहाँ सूचीमा यसो भनिएको थियो जो मा तत्व गलत क्रममा छौं। उत्पादन - आफ्नो ठाउँमा परिवर्तन। स्तम्भ दुवै बराबर वा क्रस हुँदा दोस्रो अवस्था हो। यो त्यो छ, काम अब पूरा छ, सूची एक सफल अलग संकेत गर्छ।