فرز التقنيات في صناعة برمجة: فرز "فقاعة"

لا يعتبر نوع فقاعة فقط لتكون أسرع طريقة، علاوة على ذلك، فإنه يغلق قائمة أبطأ سبل تنظيم. ومع ذلك، فإنه مزاياه. وهكذا، فإن طريقة الفرز فقاعة - الأكثر أنه لا هو الحل الطبيعي والمنطقي لهذه المشكلة، إذا كنت ترغب في ترتيب العناصر في ترتيب معين. شخص عادي يدويا، على سبيل المثال، فإنه سيتم استخدامها - فقط عن طريق الحدس.

أين هذا الاسم الغريب؟

وجاء اسم الأسلوب حتى، وذلك باستخدام القياس من فقاعات الهواء في الماء. إنها استعارة. تماما كما ترتفع فقاعات الهواء قليلا نحو الأعلى - بسبب كثافتها أكبر من السوائل (في هذه الحالة - الماء)، ولكل عنصر من عناصر مجموعة، وأصغر هو قيمة، والطريقة أكثر تدرجا إلى أعلى أرقام القائمة.

وصف الخوارزمية

يتم تنفيذ فقاعة نوع على النحو التالي:

• يمر أولا: عناصر أرقام مجموعة يؤخذ من قبل اثنين من أزواج ومقارنة أيضا. وإذا كان بعض عناصر فريق من رجلين القيمة الأولى أكبر من الثانية، البرنامج يجعلها أماكن الصرف؛
• بالتالي، على أكبر عدد من يخطئ نهاية المصفوفة. في حين تظل جميع العناصر الأخرى كما كانت، بطريقة فوضوية، وتتطلب مزيد من الفرز.
• وبالتالي تتطلب تمريرة الثاني: يتم ذلك قياسا على سابقة (التي سبق وصفها) ويحتوي على عدد من المقارنات - ناقص واحد؛
• في عدد مرور ثلاثة المقارنات، وأقل واحد من الثانية، واثنين، من الأولى. وهلم جرا؛
• تلخيص كل ذلك مرور ديه (كافة القيم في مجموعة، وعدد معين) ناقص (رقم المرور) المقارنات.

خوارزمية أقصر من البرنامج يمكن أن تكون مكتوبة على النحو التالي:

• يتم فحص مجموعة من الأرقام طالما تم العثور على أي رقمين، لا بد أن يكون أكبر من الأولى والثانية منها.
• وضع فيما يتعلق بكل العناصر الأخرى للمقايضة البرنامج مجموعة بشكل غير صحيح.

شبة الكود على أساس خوارزمية وصفه

ويتم تنفيذ أبسط على النحو التالي:

الإجراء Sortirovka_Puzirkom.

بداية

دورة لي من nachalnii_index إلى konechii_index.

دورة لأنني من nachalnii_index إلى konechii_index-1؛

إذا MASSIV [أنا]> MASSIV [ط + 1] (العنصر الأول أكبر من الثاني)، ثم:

(التغير يضع القيم)؛

نهاية

بالطبع، هذه البساطة يفاقم فقط الوضع: أبسط الخوارزمية، وأكثر ما تتجلى جميع العيوب. نسبة استثمار الوقت كبيرة جدا حتى بالنسبة لمجموعة صغيرة (وهنا يأتي في النسبية: مقدار الوقت للشخص العادي قد تبدو صغيرة، ولكن في واقع الأمر مبرمج في كل ثانية أو حتى ميلي ثانية واحدة التهم).

واستغرق تنفيذ أفضل. على سبيل المثال، مع الأخذ بعين الاعتبار تبادل القيم في مواقع مجموعة:

الإجراء Sortirovka_Puzirkom.

بداية

sortirovka = صحيح.

الدورة حتى = sortirovka صحيح.

sortirovka = كاذبة؛

دورة لأنني من nachalnii_index إلى konechii_index-1؛

إذا MASSIV [أنا]> MASSIV [ط + 1] (العنصر الأول أكبر من الثاني)، ثم:

(تغيير العناصر الأماكن)؛

sortirovka = صحيح. (معلومة تبادل أحرز).

نهاية.

القيود

العيب الرئيسي - مدة هذه العملية. كم من الوقت يتم تنفيذ خوارزمية الفرز فقاعة؟

يتم احتساب المهلة من عدد مربع كامل في مجموعة - النتيجة النهائية لذلك هي النسبية.

إذا كان أسوأ الحالات يتم تمرير مجموعة عدة مرات كما أنه يحتوي على عناصر ناقص قيمة واحدة. يحدث هذا لأنه في النهاية لا يوجد سوى عنصر واحد، والتي ليس لديها ما مقارنة، وتمرير الماضي من خلال مجموعة العمل يصبح عديم الفائدة.

وبالإضافة إلى ذلك، طريقة فعالة لفرز تبادل بسيط، كما يطلق عليه، فقط للصفائف من الحجم الصغير. وكميات كبيرة من البيانات مع مساعدة من عملية لا يعمل: ستكون النتيجة إما خطأ أو فشل البرنامج.

كرامة

فقاعة نوع من السهل جدا أن نفهم. مناهج الجامعات التقنية في دراسة العناصر ترتيب مجموعته تمر في المقام الأول. طريقة سهلة لتنفيذ كل لغة دلفي البرمجة (L (دلفي)، وC / C ++ (C / C زائد زائد)، والقيم بسيطة بشكل لا يصدق من خوارزمية موقع في حق النظام وفي باسكال (باسكال). فقاعة نوع مثالية للمبتدئين.

بسبب عيوب الخوارزمية لا تستخدم في أغراض اللامنهجية.

مبدأ الفرز البصرية

وجهة النظر الأولي للمجموعة 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؛

فار 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 [ب]: = ك.

ينتهي.

ينتهي.

ينتهي.

writeln ( 'بعد الفرز')؛

ل: = 1 إلى kol_mas القيام writeln (MASSIV [في ])؛

نهاية.

مثال فقاعة الفرز في لغة C (C)

على سبيل المثال:

تتضمن #

تتضمن #

الباحث الرئيسي (الباحث ARGC، شار * ARGV [])

{

الباحث MASSIV [8] = {36، 697، 73، 82، 68، 12، 183، 88}، ط، وما يليها.

ل(؛؛) {

وما يليها = 0؛

ل(ط = 7؛ ط> 0؛ ط -) {

إذا (MASSIV [ط] [ط- 1]) {

مبادلة (MASSIV [أنا]، MASSIV [ط- 1])؛

وما يليها ++؛

}

}

إذا (و و == 0) كسر.

}

getch ()؛ // عرض تأخير

العودة 0؛

}.