प्रोग्रामिंग पद्धत म्हणून Quicksort

1960 मध्ये, के अ वेश्या माहिती जलद क्रमवारी एक पद्धत विकसित, सर्वात प्रसिद्ध झाला. आज तो सकारात्मक गुणधर्म भरपूर आहे म्हणून मोठ्या प्रमाणावर प्रोग्रामिंग मध्ये वापरले जाते: सामान्य प्रकरणे वापरले जाऊ शकते, तो याद्या विविध प्रकारच्या सुसंगत व त्याची अंमलबजावणी करण्यास सोपे अतिरिक्त स्मृती मध्ये एक लहान वाढ करणे आवश्यक आहे. पण, शुद्धीत आहेत जे Quicksort आहे: वापरून काम चुका भरपूर परवानगी, आणि ती थोडीशी अस्थिर आहे.

तथापि, तो सर्वात अभ्यास आवृत्ती आहे. प्रथम देय होआरे केल्यानंतर, अनेक त्याच्या दाट अभ्यास करू. मोठ्या बेस प्रायोगिक पुरावा द्वारे underpinned आहे नोकरी, वेळ घालवला शोधत सैद्धांतिक प्रश्न स्थापना करण्यात आली. मूलभूत अल्गोरिदम आणि वाढ गती सुधारण्यासाठी रिअल प्रस्ताव होते.

Quicksort तो सर्वत्र आढळू शकते अतिशय सामान्य आहे. त्याच्या आधारावर पद्धत TList.Sort, सर्व आवृत्त्या Delphi, तो सी मध्ये पूर्ण करण्यासाठी, qsort ++ घेतला वेळ लायब्ररी कार्य (1 वगळता) उपस्थित राबविण्यात येत आहे.

ऑपरेशन मूलभूत तत्त्व एक "पाणलोट आणि विजय" म्हणून तयार केले जाऊ शकते. हे दोन गट यादी ब्रेकिंग येते आणि स्वत: हून प्रत्येक भाग लावलेले आहेत. एक बेस घटक द्वारे केले जाते आणि तुलनेने त्याच्या संपूर्ण यादी पुनर्रचना आहे: हे अधिक लक्ष वेगळे प्रक्रिया आहे, जे दरम्यान खालील येते अदा केले जाईल खालीलप्रमाणे. उमेदवार एक गट डाव्या बाजुस, मूल्य, जे इतर सर्व हस्तांतरण नियम पेक्षा कमी आहे. तो लावलेले यादीत मुख्य घटक त्याच्या रास्त ठिकाणी आहे की बाहेर करते. पुढील टप्प्यात - बेस संबंधीत घटक दोन्ही बाजूंना एक आव्हान रिकर्सिव क्रमवारी कार्ये. हे प्रक्रिया यादी फक्त एक घटक आहे तरच कार्य करते संपते, की लावलेले करणे आहे. त्यामुळे, एक द्रुत क्रमवारी म्हणून एक प्रोग्रामिंग कार्य मास्टर करण्यासाठी, तो आवश्यक कमी-स्तरीय अल्गोरिदम काम माहित आहे: एक) बेस सदस्य निवड; ब) लहान आणि मोठ्या मूल्ये दोन संच निर्मिती सर्वात प्रभावी क्रमांतरण यादी.

प्रथम तत्त्वे ओळख. बेस सदस्य निवडून तेव्हा, आदर्श सरासरी सूचीतून निवडले पाहिजे. ब्रेक मग दोन समान भागात विभागलेला आहे. फक्त गणना सरासरी मूल्य यादी अत्यंत कठीण आहे, त्यामुळे अगदी सर्वात वेगवान क्रमवारीवर या गणिताची एक शाखा बाजूला बायपास करते. पण जास्तीत जास्त किंवा किमान मूल्य मूळ घटक निवड - देखील नाही सर्वोत्तम पर्याय. जर एक अशा निश्चित रिक्त यादी हमी जाईल, आणि दुसरा संपूर्ण निर्माण करतो. त्यामुळे बेस सदस्य म्हणून सरासरी जवळ आहे की एक निवडले पाहिजे, पण कमाल आणि किमान वर निष्कर्ष.

निवड निश्चित आहे की, आपण कुजणे अल्गोरिदम पुढे जाऊ शकता. ही द्रुत क्रमवारी तथाकथित आतील लूप. सर्व काही दोन जलद प्रवेश निर्देशांक तयार केला आहे: प्रथम डावीकडून उजवीकडे, त्याउलट, योग्य, दुसरा डावीकडून घटक प्रती जा. सुरुवात ऑपरेशन अंमलबजावणी योग्य: निर्देशांक यादीत आहे आणि मुख्य सर्व मूल्ये तुलना करा. घटक मूलभूत या पेक्षा कमी किंवा या समान आहे तेव्हा सायकल पूर्ण झाले आहे. त्या एक तुलना आहे आणि निर्देशांक मूल्य कमी होते आहे. डाव्या हाताला काम किंवा त्याहून मोठे मूल्य पूर्ण झाल्यावर. येथे, तुलना किंमत वाढते.

quicksort असलेल्या विभाजन अल्गोरिदम या टप्प्यावर, दोन घटनांमध्ये उद्भवू शकतात. प्रथम डावीकडे निर्देशांक योग्य पेक्षा कमी आहे. या त्रुटी दर्शवितात, नंतर घटक सूचीमध्ये नमूद केले गेले जे चूक क्रमाने आहेत. आउटपुट - त्यांच्या ठिकाणी बदला. स्तंभ दोन्ही समान किंवा पार आहे दुसर्या परिस्थिती आहे. ही यादी एक यशस्वी वेगळे दर्शवितात, की, काम आता पूर्ण झाले आहे.