प्रोग्रामिंग में तकनीक छँटाई: छँटाई "बुलबुला"

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

जहां इस तरह के एक असामान्य नाम किया था?

विधि नाम आया था, पानी में हवा के बुलबुले के सादृश्य का उपयोग कर। यह एक रूपक है। बस के रूप में छोटे से हवाई बुलबुले ऊपर की ओर वृद्धि - क्योंकि उनके घनत्व एक तरल पदार्थ (इस मामले में - पानी) से अधिक है, और प्रत्येक सरणी तत्व, छोटे यह मूल्य, सूची संख्या के शीर्ष करने के लिए और अधिक क्रमिक तरीका है।

एल्गोरिथ्म का विवरण

बुलबुला तरह के रूप में निम्नानुसार किया जाता है:

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

एक कार्यक्रम के भी कम एल्गोरिथ्म के रूप में लिखा जा सकता है:

• संख्या की एक सरणी, के रूप में किसी भी दो नंबर पाए जाते हैं जब तक चेक किया गया है उनमें से दूसरा पहले से अधिक होना स्वाभाविक है;
• गलत तरीके से सरणी सॉफ्टवेयर स्वैप में से प्रत्येक के अन्य तत्वों के संबंध में तैनात।

एल्गोरिथ्म वर्णित के आधार पर स्यूडोकोड

सबसे सरल कार्यान्वयन किए गए इस प्रकार है:

Sortirovka_Puzirkom प्रक्रिया;

शुरू

nachalnii_index konechii_index करने से जे के लिए चक्र;

konechii_index -1 nachalnii_index से मैं के लिए चक्र;

यदि massiv [i]> massiv [i + 1] (पहले एक दूसरे से अधिक तत्व), तो:

(परिवर्तन मूल्यों देता है);

अंत

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

यह बेहतर कार्यान्वयन ले लिया। उदाहरण के लिए, खाते में सरणी स्थानों में मूल्यों के आदान-प्रदान लेने:

Sortirovka_Puzirkom प्रक्रिया;

शुरू

sortirovka सच =;

चक्र sortirovka सच = जब तक;

sortirovka = झूठी;

konechii_index -1 nachalnii_index से मैं के लिए चक्र;

यदि massiv [i]> massiv [i + 1] (पहले एक दूसरे से अधिक तत्व), तो:

(तत्वों स्थानों बदल);

sortirovka सच =; (पहचान है कि विनिमय किया गया है)।

अंत।

सीमाएं

मुख्य नुकसान - प्रक्रिया की अवधि। ज्यादा समय कैसे किया जाता है एल्गोरिथ्म छँटाई बुलबुला?

लीड समय वर्ग नंबरों की संख्या से गणना की जाती है सरणी में - इसके बारे में अंतिम परिणाम आनुपातिक है।

सरणी कई बार के रूप पारित हो जाता है सबसे खराब स्थिति तो यह एक मूल्य शून्य से तत्व है के रूप में। यह तब होता है केवल एक ही तत्व है अंत में क्योंकि, जो तुलना करने के लिए कुछ भी नहीं है, और सरणी के माध्यम से पिछले पास बेकार कार्रवाई हो जाता है।

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

गौरव

बुलबुला तरह समझने के लिए बहुत आसान है। अपने सरणी के आदेश तत्वों के अध्ययन में तकनीकी विश्वविद्यालय के पाठ्यक्रम पहली जगह में गुजरती हैं। विधि दोनों डेल्फी प्रोग्रामिंग भाषा (एल (डेल्फी), और C / C ++ (सी / सी प्लस प्लस), सही क्रम में और कम से स्थान एल्गोरिथ्म के एक अविश्वसनीय रूप से सरल मूल्यों को लागू करना आसान है पास्कल (पास्कल)। बुलबुला तरह शुरुआती के लिए आदर्श है।

एल्गोरिथ्म की खामियों के कारण पाठ्येतर उद्देश्यों में उपयोग नहीं किया जाता है।

दृश्य छंटाई सिद्धांत

सरणी 8 22 4 74 44 37 1 7 के प्रारंभिक दृश्य

चरण 8 22 4 74 44 1 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

चरण 1 से 8 22 4 74 2 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 से 7 74 44 37

1 8 22 4 से 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

चरण 1 से 4 8 22 7 3 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 से 4 7 8 22 37 74 44

चरण 1 से 4 7 8 22 4 37 44 74

1 से 4 7 8 22 37 44 74

1 से 4 7 8 22 37 44 74

1 से 4 7 8 22 37 44 74

चरण 1 से 4 7 8 22 5 37 44 74

1 से 4 7 8 22 37 44 74

1 से 4 7 8 22 37 44 74

चरण 1 से 4 7 8 22 6 37 44 74

1 से 4 7 8 22 37 44 74

चरण 1 से 4 7 8 22 7 37 44 74

पास्कल में बुलबुला तरह उदाहरण

उदाहरण:

स्थिरांक kol_mas = 10;

वर massiv: सरणी [1..kol_mas] के पूर्णांक;

ए, बी, कश्मीर: पूर्णांक;

शुरू करना

writeln ( 'इनपुट', kol_mas, 'सरणी के तत्वों');

एक के लिए: = 1 kol_mas को readln कर (massiv [एक ]);

एक के लिए: = 1 kol_mas -1 करने के लिए शुरू करते हैं

ख के लिए: = एक + 1 kol_mas करने के लिए शुरू करते हैं

यदि massiv [एक]> massiv [ ख] तब शुरू

कश्मीर: = massiv [एक]; massiv [एक]: = massiv [ ख]; massiv [ख]: = k;

अंत;

अंत;

अंत;

writeln ( 'प्रकार के बाद');

एक के लिए: = 1 kol_mas को writeln कर (massiv [एक ]);

अंत।

उदाहरण बुलबुला सी भाषा में छँटाई (सी)

उदाहरण:

# शामिल

# शामिल

पूर्णांक मुख्य (int argc, char * argv [])

{

पूर्णांक massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, मैं, एफएफ;

के लिए (;;) {

एफएफ = 0;

(i = 7; i> 0; मैं -) {

अगर (massiv [i] [I- 1]) {

स्वैप (massiv [i], massiv [I- 1]);

एफएफ ++;

}

}

अगर (एफएफ == 0) को तोड़ने;

}

getch (); // प्रदर्शन देरी

0 वापसी;

}।