प्रोग्रामिङमा क्रमबद्ध तरिकाहरू: "बुलबुला" क्रमबद्ध गर्दै

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

यो असामान्य नाम कहाँबाट आयो?

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

एल्गोरिदमको विवरण

बबल क्रमबद्ध निम्नानुसार सम्पन्न गरिएको छ:

• पहिलो पास: संख्याको एरेको तत्व दुई मा लिइन्छ र जोडीहरूमा तुलनात्मक छन्। यदि केही दुई तत्वहरूमा पहिलो मूल्य दोस्रो भन्दा ठूलो छ भने, कार्यक्रमले स्थानहरूको आदान प्रदान गर्दछ;
• यसैले, सबैभन्दा ठूलो संख्या array को अन्तमा छ। जबकि सबै अन्य तत्वहरू, तिनीहरू अराजकता क्रममा रहन्थे र थप क्रमबद्ध गर्न चाहन्छन्;
• यसैले, दोस्रो सेकेन्ड आवश्यक छ: यो उल्लेखित द्वारा अघिल्लो एक (पहिले नै वर्णन गरिएको) सँगको उत्पादन गरिएको छ र यसको तुलनात्मक संख्या - एक मिनेट छ;
• पासमा, तीनवटा तुलना संख्या दोस्रो भन्दा कम छ, र पहिलो भन्दा दुई भन्दा बढी। र त्यसमा;
• हामी संक्षेप गर्छौं प्रत्येक पास (array, a specific number) minus (पासको संख्या) तुलनाहरू छन्।

भविष्यको कार्यक्रमको छोटो एल्गोरिदम पनि निम्नानुसार लेख्न सकिन्छ:

• संख्याहरूको सङ्कमा जाँच गरिएको छ जबसम्म दुई नम्बर भेटिएन, दोस्रो को पहिलो भन्दा भन्दा बढी हुनु पर्छ;
• सरणीको एक अन्य तत्वको सम्बन्धमा गलत रूपमा स्थित छ, कार्यक्रम स्वैप गर्दछ।

Pseudocode वर्णित एल्गोरिथ्म मा आधारित

सरल कार्यान्वयन निम्नानुसार छ:

प्रक्रिया Sortirovka_Puzirkom ;

सुरू गर्नुहोस्

Nachalnii_index बाट konechii_index बाट j को लागि एक पाश;

म लागी नै लाग्न सक्छन ।

यदि massiv [i]> massiv [i + 1] (पहिलो तत्त्व दोस्रो भन्दा ठूलो छ), त्यसपछि:

(स्थानहरूमा मानहरू परिवर्तन गर्नुहोस्);

अन्त

निस्सन्देह, यहाँ सादगी मात्र स्थिति बढ्न सक्छ: सरल एल्गोरिदम, अझ बढी यसले सबै कमजोरीहरू देखाउँदछ। समय-उपभोग पनि एक सानो सरणी को लागि पनि एकदम राम्रो छ (यहाँ रिटरेटिटिटी आउँछ: औसत व्यक्ति को लागि समय सानो लाग्न सक्छ, तर प्रोग्रामर को हरेक सेकेंड मा या दोस्रो मिलिसेन्ड्स मा पनि)।

यसले राम्रो कार्यान्वयन गर्यो। उदाहरणका लागि, केहि स्थानहरूमा सरणीमा मानहरूको विनिमयमा लिईन्छ:

प्रक्रिया Sortirovka_Puzirkom ;

सुरू गर्नुहोस्

Sortirovka = true;

Cycle जबकि क्रमबद्ध = true;

Sortirovka = गलत;

म लागी नै लाग्न सक्छन ।

यदि massiv [i]> massiv [i + 1] (पहिलो तत्त्व दोस्रो भन्दा ठूलो छ), त्यसपछि:

(हामी ठाउँहरूमा तत्वहरू परिवर्तन गर्छौं);

Sortirovka = true; (सूचित गरिएको थियो कि विनिमय गरियो)।

अन्त्य

विधिको हानिकारक

मुख्य हानि प्रक्रियाको अवधि हो। बुलबुला क्रम एल्गोरिथ्म कति लामो काम गर्दछ ?

निष्पादन समय सरणी मा संख्या को संख्या को वर्ग देखि गणना गरिएको छ - अन्तिम परिणाम आनुपातिक हो।

सबै भन्दा खराब-केस परिदृश्यको साथ, सरणीमा धेरै तत्वहरु को रूप मा ट्रान्स गरिनेछ, माइनस एक मान। यो किनभने किनकि त्यहाँ एक मात्र तत्व हो जसले सँग तुलना गर्न केही छैन, र सरणीको माध्यमबाट अन्तिम पास बेकार कार्य हुन्छ।

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

फाइदाहरू

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

कमजोरीहरूको कारण, एल्गोरिदम असामान्य उद्देश्यहरूको लागि प्रयोग गरिएको छैन।

क्रमबद्ध गर्ने एक स्पष्ट सिद्धान्त

Array को प्रारम्भिक दृश्य 8 22 4 74 44 37 1 7 हो

चरण 1 8 22 4 74 44 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

चरण 2 1 8 22 4 74 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

चरण 3 1 4 8 22 7 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

चरण 4 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 37 44 74

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

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

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

1 4 7 8 22 37 44 74

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

पास्कल मा एक बुलबुला द्वारा क्रमबद्ध

उदाहरण:

Kol_mas const = 10;

Var massiv: array [1..kol_mas] पूर्णांकको;

A, b, k: पूर्णांक;

सुरू गर्नुहोस्

Writeln ('input', kol_mas, 'array of elements');

एक को लागि: = 1 को kol_mas को पढ्न पढें (massiv [a]);

एक को लागि: = 1 kol_mas-1 मा सुरु गर्नुहोस्

को लागि: kol_mas को लागि एक + 1 सुरु गरौं

यदि massiv [a]> massiv [b] त्यसपछि सुरू गर्नुहोस्

K: = massiv [a]; Massiv [a]: = massiv [b]; Massiv [b]: = k;

अन्त्य;

अन्त्य;

अन्त्य;

Writeln ('sort' पछि);

एक को लागि: = 1 को kol_mas लेख लेखन (massiv [a]);

अन्त

एक बुलबुला द्वारा सी (क्रमबद्ध) क्रमबद्ध

उदाहरण:

# समावेश गर्नुहोस्

# समावेश गर्नुहोस्

Int मुख्य (int argc, char * argv [])

{

Int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

यसकालागि (;;) {

Ff = 0;

को लागी (i = 7; i> 0; i -) {

यदि (massiv [i]

स्वैप (मासिक [i], मासिक [i-1]);

Ff ++;

}

}

यदि (ff == 0) ब्रेक;

}

Getch (); // स्क्रिन विलम्ब

फर्काउनुहोस् 0;

}।