چھنٹائی پروگرامنگ میں تکنیک: "بلبلا" چھنٹائی

بلبلا طرح صرف، سب سے تیز رفتار طریقہ کار تصور کیا جاتا نہیں ہے اس کے علاوہ، یہ منظم کرنے کے سست ترین طریقوں میں فہرست بند کرتا ہے. تاہم، یہ اس کے فوائد ہیں. اس طرح، بلبلا چھنٹائی کے طریقہ کار - سب سے زیادہ ہے کہ نہ تو آپ کو ایک مخصوص ترتیب میں اشیاء کا انتظام کرنا چاہتے ہیں، مسئلے کا فطری اور منطقی حل ہے. ایک عام شخص کو دستی طور پر، مثال کے طور پر، یہ ان کا استعمال کریں گے - صرف انترجشتھان کی طرف سے.

جہاں اس طرح ایک غیر معمولی نام کیا تھا؟

طریقے کا نام پانی میں ہوا کے غبارے کے قیاس کا استعمال کرتے ہوئے آئے تھے. یہ ایک استعارہ ہے. بس کے طور پر بہت کم ہوا بلبلوں ؤردوگامی اضافہ - ان کی کثافت (اس کیس میں - پانی) ایک سیال سے بڑا ہے کیونکہ، اور ہر صف عنصر، چھوٹے جو قدر، فہرست نمبروں کے سب کے لئے زیادہ بتدریج طریقہ ہے.

الگورتھم کی تفصیل

بلبلا طرح درج ذیل کارکردگی کا مظاہرہ کیا ہے:

• سب سے پہلے پاس: صف نمبروں کے عناصر کے دو جوڑوں کی طرف سے لیا جاتا ہے اور یہ بھی مقابلے میں. دو رکنی ٹیم پہلی قدر میں سے کچھ عناصر دوسرے سے زیادہ ہے تو، پروگرام ان کا تبادلہ مقامات ہوتا ہے؛
• چنانچہ سب سے بڑی تعداد یاد کرتے صف کے آخر میں. وہ تھے کے طور پر دیگر تمام عناصر رہیں جبکہ ایک اراجک انداز میں، اور زیادہ چھنٹائی کی ضرورت ہوتی ہے؛
• اور اس وجہ سے ایک دوسرے کے پاس ضرورت ہوتی ہے: اس کے ساتھ قیاس کی طرف سے بنایا جاتا ہے پچھلے (پہلے ہی بیان کیا ہے) اور موازنہ کی ایک بڑی تعداد ہے - مائنس ایک؛
• گزرنے نمبر تین موازنہ، دوسرے کے مقابلے میں ایک کم، اور دو، پہلے کے مقابلے میں. اور تو؛
• ہر گزرنے ہے کہ (صف میں تمام اقدار، خاص نمبر) مائنس (گزرنے نمبر) موازنہ مختصر.

ایک پروگرام کی بھی کم الگورتھم کے طور پر لکھا جا سکتا ہے:

• کسی بھی دو اعداد پائے جاتے ہیں کے طور پر اعداد کی ایک صف جب تک موازنہ کیا جاتا ہے، ان میں سے دوسرا پہلے سے زیادہ ہونا کرنے کی پابند ہے.
• غلط طریقے سے صف سافٹ ویئر سویپ کے ایک دوسرے عناصر کے سلسلے میں پوزیشن.

بیان الگورتھم کی بنیاد پر pseudocode کے

مندرجہ ذیل کے طور پر سادہ ترین نفاذ کیا جاتا ہے:

Sortirovka_Puzirkom طریقہ کار؛

شروع

konechii_index کرنے nachalnii_index سے J لئے سائیکل.

konechii_index-1 کو nachalnii_index سے میں نے کے لئے سائیکل.

اگر massiv [I]> massiv [I + 1] (ایک سیکنڈ سے زیادہ پہلے عنصر)، پھر:

(تبدیلی اقدار دیتا)؛

آخر

بالکل، یہ سادگی صرف صورت حال بڑھ: آسان الگورتھم، مزید یہ تمام خامیوں اظہار. وقت کی سرمایہ کاری کا تناسب (: عام آدمی کے لئے وقت کی رقم چھوٹے لگ سکتا ہے، لیکن حقیقت میں ایک پروگرامر ہر دوسرے یا اس سے بھی millisecond کی شمار کی اضافیت میں آتا ہے یہاں) بھی ایک چھوٹے صف کے لئے بہت اچھا ہے.

اس سے بہتر عمل جاری رہی. مثال کے طور پر اکاؤنٹ میں صف مقامات میں اقدار کے تبادلے لینے:

Sortirovka_Puzirkom طریقہ کار؛

شروع

sortirovka سچا =؛

سائیکل sortirovka سچ = جب تک؛

sortirovka جھوٹے =؛

konechii_index-1 کو nachalnii_index سے میں نے کے لئے سائیکل.

اگر massiv [I]> massiv [I + 1] (ایک سیکنڈ سے زیادہ پہلے عنصر)، پھر:

(عناصر کے مقامات تبدیل)؛

sortirovka سچا =؛ (کی نشاندہی کی ہے کہ زر مبادلہ کی گئی ہے).

اختتام.

حدود

اہم نقصان - عمل کا دورانیہ. کارکردگی کتنا وقت کر رہا ہے الگورتھم چھنٹائی بلبلا؟

وقت کی قیادت کی صف میں مربع اعداد کی تعداد سے شمار کیا جاتا ہے - اس کے آخر نتیجہ متناسب ہے.

یہ ایک قدر مائنس عناصر ہیں کے طور پر صف کئی بار کے طور پر منظور کیا جاتا ہے بدترین صورت تو. آخر میں موازنہ کرنے کے لئے کچھ بھی نہیں ہے جس میں صرف ایک عنصر نہیں ہے، کیونکہ اگر ایسا ہوتا ہے، اور صف کے ذریعے گزشتہ پاس بیکار کارروائی ہو جاتا ہے.

اس کے علاوہ، ایک سادہ تبادلے چھنٹائی طور پر اس کا صرف چھوٹے سائز کے arrays کے لئے کیا جاتا ہے کہا جاتا ہے کا موثر طریقہ. عمل کی مدد سے ڈیٹا کی بڑی مقدار کام نہیں کرے گا: نتیجہ یا تو ایک غلطی یا پروگرام کی ناکامی ہو جائے گا.

وقار

بلبلا طرح سمجھنے کے لئے بہت آسان ہے. اس صف کے حکم عناصر کے مطالعہ میں تکنیکی یونیورسٹیوں کے نصاب کو پہلی جگہ میں منتقل. طریقہ کار دونوں Delphi کے پروگرامنگ زبان (ایل (Delphi کے)، اور C / C + + (C / C پلس پلس)، صحیح ترتیب میں اور میں مقام کا الگورتھم کی ایک ناقابل یقین حد تک آسان اقدار لاگو کرنے کے لئے آسان ہے پاسکل (پاسکل) بلبلا طرح beginners کے لئے مثالی ہے.

الگورتھم کی خرابیوں کی وجہ سے نصابی مقاصد میں استعمال نہیں کیا جاتا ہے.

بصری چھنٹائی اصول

صف 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

پاسکل میں بلبلا طرح مثال

مثال:

CONST kol_mas = 10؛

متغیر massiv: صف کے [1..kol_mas] عددی؛

A، B، K: عددی؛

شروع

writeln ( 'ان پٹ'، kol_mas، 'صف کے عناصر')؛

ایک کے لئے: = kol_mas سے 1 readln کرتے (massiv [ایک ])؛

ایک کے لئے: = 1 kol_mas-1 کے لئے شروع کرتے ہیں

بی لئے: A + 1 kol_mas کرنے کے لئے شروع ہے =

massiv [ایک]> massiv [اگر ب] پھر شروع

K: = massiv [A]؛ massiv [A]: = massiv [ ب]؛ massiv [ب] = K؛

آخر؛

آخر؛

آخر؛

writeln ( 'چھانٹیں بعد')؛

ایک کے لئے: = kol_mas سے 1 writeln کرتے (massiv [ایک ])؛

آخر میں.

EXAMPLE بلبلا C زبان میں چھنٹائی (C)

مثال:

# شامل

# شامل

int اہم (INT جہاں argc، چار * argv کے [])

{

INT massiv [8] = {36، 697، 73، 82، 68، 12، 183، 88}، میں، FF؛

(؛؛) کے لئے {

FF = 0؛

کے لئے (میں = 7؛ میں> 0؛ میں -) {

اگر (massiv [میں] [i- 1]) {

ادل بدل (massiv [میں]، massiv [i- 1])؛

FF ++؛

}

}

اگر (FF == 0) توڑنے؛

}

getch ()؛ // ڈسپلے تاخیر

0 واپس؛

}.