تصنيف الفقاعات مقابل تصنيف الإدراج
فرز الفقاعات عبارة عن خوارزمية فرز تعمل من خلال تصفح القائمة ليتم فرزها بشكل متكرر أثناء مقارنة أزواج العناصر المتجاورة. إذا كان هناك زوج من العناصر بالترتيب الخاطئ ، فسيتم تبديلهما لوضعهما بالترتيب الصحيح. يتكرر هذا الاجتياز حتى لا تكون هناك حاجة إلى مقايضات أخرى. فرز الإدراج هو أيضًا خوارزمية فرز تعمل عن طريق إدراج عنصر في قائمة الإدخال في الموضع الصحيح في قائمة تم فرزها بالفعل. يتم تطبيق هذه العملية بشكل متكرر حتى يتم فرز القائمة.
ما هو تصنيف الفقاعات؟
فرز الفقاعات عبارة عن خوارزمية فرز تعمل من خلال تصفح القائمة ليتم فرزها بشكل متكرر أثناء مقارنة أزواج العناصر المتجاورة. إذا كان هناك زوج من العناصر بالترتيب الخاطئ ، فسيتم تبديلهما لوضعهما بالترتيب الصحيح. يتكرر هذا الاجتياز حتى لا تكون هناك حاجة إلى مقايضات أخرى (مما يعني أن القائمة مرتبة). نظرًا لأن العناصر الأصغر في القائمة تظهر في الأعلى عندما تظهر فقاعة على السطح ، يتم إعطاؤها اسم فرز الفقاعة. الفرز الفقاعي عبارة عن خوارزمية فرز بسيطة للغاية ولكنها تحتوي على متوسط تعقيد وقت الحالة O (n2) عند فرز قائمة تحتوي على عناصر n. نتيجة لذلك ، لا يعد فرز الفقاعة مناسبًا لفرز القوائم التي تحتوي على عدد كبير من العناصر. ولكن نظرًا لبساطته ، يتم تدريس فرز الفقاعات أثناء مقدمات الخوارزميات.
ما هو تصنيف الإدراج؟
نوع الإدراج هو خوارزمية فرز أخرى ، تعمل عن طريق إدراج عنصر في قائمة الإدخال في الموضع الصحيح في القائمة (التي تم فرزها بالفعل).يتم تطبيق هذه العملية بشكل متكرر حتى يتم فرز القائمة. في فرز الإدخال ، يتم إجراء الفرز في المكان. لذلك بعد تكرار الخوارزمية ، سيتم فرز مدخلات i + 1 الأولى في القائمة وسيتم إلغاء فرز باقي القائمة. في كل تكرار ، سيتم أخذ العنصر الأول في الجزء غير الفرز من القائمة وإدراجه في المكان الصحيح في القسم المصنف من القائمة. فرز الإدراج له متوسط تعقيد وقت الحالة O (n2). نتيجة لهذا ، فإن فرز الإدراج ليس مناسبًا أيضًا لفرز القوائم الكبيرة.
ما الفرق بين تصنيف الفقاعات وفرز الإدراج؟
على الرغم من أن كلاً من خوارزميات فرز الفقاعات وفرز الإدراج لها متوسط تعقيدات وقت الحالة لـ O (n2) ، إلا أن فرز الفقاعة يتفوق في جميع الأوقات تقريبًا عن طريق نوع الإدراج. هذا يرجع إلى عدد المقايضات التي تحتاجها الخوارزميتان (تحتاج أنواع الفقاعات إلى المزيد من المقايضات). ولكن نظرًا لبساطة نوع الفقاعة ، فإن حجم رمزها صغير جدًا.يوجد أيضًا نوع متغير من نوع الإدراج يُسمى نوع الغلاف ، والذي يحتوي على تعقيد زمني لـ O (n3 / 2) ، مما يسمح باستخدامه عمليًا. علاوة على ذلك ، يعتبر فرز الإدراج فعالًا جدًا لفرز القوائم "المصنفة تقريبًا" ، عند مقارنتها بفرز الفقاعة.
