طرق الفرز في البرمجة: الفرز حسب "فقاعة"
لا يعتبر التصنيف حسب الفقاعة الأكثر فقطمن خلال طريقة سريعة ، وعلاوة على ذلك ، فإنه يغلق قائمة أبطأ طرق الطلب. ومع ذلك ، لديها أيضا مزاياه. لذا ، فإن الفرز حسب طريقة الفقاعة هو الحل الأكثر منطقية وطبيعية للمشكلة ، إذا كنت ترغب في ترتيب العناصر بترتيب معين. شخص عادي ، على سبيل المثال ، سوف يستخدمه باليد ، ببساطة عن طريق الحدس.
من أين جاء هذا الاسم غير المعتاد؟
تم اختراع اسم الأسلوب باستخدام تشبيه معفقاعات الهواء في الماء. هذا استعارة. كما ترتفع فقاعات الهواء الصغيرة إلى الأعلى - لأن كثافتها أكبر من أي سائل (في هذه الحالة - الماء) ، وكل عنصر في الصفيف ، كلما صغر حجمه ، كلما زاد تدريجياً طريقه إلى بداية قائمة الأرقام.
وصف الخوارزمية
يتم إجراء الفرز حسب الفقاعة كما يلي:
- التمريرة الأولى: يتم أخذ عناصر مصفوفة الأرقام في اثنتين ويتم مقارنتها أيضًا في أزواج. إذا كانت القيمة الأولى أكبر من الثانية في بعض العنصرين من العناصر ، فإن البرنامج يقوم بتبادل الأماكن ؛
- لذلك ، يكون العدد الأكبر في نهاية الصفيف. بينما تبقى جميع العناصر الأخرى ، كما هي ، في حالة فوضوية وتتطلب المزيد من الفرز ؛
- لذلك ، هناك حاجة لتمريرة ثانية: يتم إنتاجها قياسا على السابق (الموصوف سابقا) ولديها عدد من المقارنات - ناقص واحد ؛
- في التمريرة ، تكون المقارنات الثلاثة رقم واحد أقل من الثانية ، واثنتين ، من الأولى. و هكذا
- دعونا نلخص أن كل تمريرة لها (في المصفوفة ، رقم محدد) ناقص (عدد الممرات) المقارنات.
يمكن كتابة حتى خوارزمية أقصر للبرنامج المستقبلي كما يلي:
- يتم تحديد مصفوفة الأرقام حتى يتم العثور على رقمين ، يجب أن يكون الثاني منها أكبر من الأول ؛
- يقع بشكل غير صحيح فيما يتعلق بكل عنصر آخر من الصفيف ، ومقايضة البرنامج.
Pseudocode استناداً إلى الخوارزمية الموصوفة
أبسط التنفيذ هو كما يلي:
إجراء Sortirovka_Puzirkom.
البداية
دورة ل ي من nachalnii_index تصل إلى konechii_index.
دورة ل أنا من nachalnii_index تصل إلى konechii_index-1.
إذا massiv [i]> massiv [i + 1] (العنصر الأول أكبر من الثاني) ، ثم:
(تغيير القيم في الأماكن) ؛
النهاية
وبطبيعة الحال ، فإن البساطة هنا لا تؤدي إلا إلى تفاقمهاالوضع: في أبسط الخوارزمية، وأكثر ما يتجلى جميع العيوب. نسبة استثمار الوقت كبيرة جدا حتى بالنسبة لمجموعة صغيرة (وهنا يأتي في النسبية: مقدار الوقت للشخص العادي قد تبدو صغيرة، ولكن في واقع الأمر مبرمج في كل ثانية أو حتى ميلي ثانية واحدة التهم).
استغرق الأمر تنفيذ أفضل. على سبيل المثال ، مع مراعاة تبادل القيم في المصفوفة في بعض الأماكن:
إجراء Sortirovka_Puzirkom.
البداية
sortirovka = صحيح
دورة حتى sortirovka = صحيح
sortirovka = خطأ
دورة ل أنا من nachalnii_index تصل إلى konechii_index-1.
إذا massiv [i]> massiv [i + 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
الخطوة الخامسة 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؛
var massiv: array [1..kol_mas] of integer؛
a، b، k: integer؛
بدأ
writeln ("input"، kol_mas، "elements of array")؛
a: = 1 to kol_mas do readln (massiv [a])؛
لـ: = 1 تبدأ kol_mas-1
لـ b: = a + 1 تبدأ kol_mas
إذا بدأت massiv [a]> massiv [b] بعد ذلك
k: = massiv [a]؛ massiv [a]: = massiv [b]؛ massiv [b]: = k؛
ينتهي.
ينتهي.
ينتهي.
writeln ("بعد الفرز") ؛
a: = 1 to kol_mas do writeln (massiv [a])؛
نهاية.
مثال للفرز حسب الفقاعة في C (C)
على سبيل المثال:
تتضمن #
تتضمن #
int main (int argc، char * argv [])
{
int massiv [8] = {36، 697، 73، 82، 68، 12، 183، 88}، i، ff؛
ل (؛؛) {
ff = 0؛
لـ (i = 7؛ i> 0؛ i -) {
if (massiv [i] <massiv [i-1]) {
swap (massiv [i]، massiv [i-1])؛
ص و ++
}
}
إذا كسر (ff == 0) ؛
}
getch ()؛ // تأخير الشاشة
العودة 0
}.
</ p>
