المحتوى

• رسم بياني للمقارنة
• تعريف فقاعة التصنيف
• تعريف اختيار الفرز
• استنتاج

يعد الفرز أحد المهام الرئيسية في برامج الكمبيوتر حيث يتم ترتيب عناصر الصفيف بترتيب معين. الفرز يجعل البحث أسهل. فرز الفرز وفرز التحديد هما خوارزميات الفرز التي يمكن تمييزها من خلال الطرق التي يستخدمونها للفرز. يقوم فرز الفقاعة بتبادل العناصر بشكل أساسي بينما يقوم فرز التحديد بإجراء الفرز عن طريق تحديد العنصر.

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

1. رسم بياني للمقارنة
2. فريف
3. الاختلافات الرئيسية
4. استنتاج

رسم بياني للمقارنة

أساس للمقارنة	فقاعة الفرز	اختيار نوع
الأساسية	تتم مقارنة العنصر المجاور والمبادلة	يتم تحديد أكبر عنصر ومبادلة مع العنصر الأخير (في حالة ترتيب تصاعدي).
أفضل حالة تعقيد الوقت	على)	على2)
نجاعة	غير فعال	تحسين الكفاءة بالمقارنة مع نوع الفقاعة
مستقر	نعم فعلا	لا
طريقة	تبادل	اختيار
سرعة	بطيء	بسرعة بالمقارنة مع نوع فقاعة

تعريف فقاعة التصنيف

فقاعة الفرز هي أبسط خوارزمية تكرارية تعمل عن طريق مقارنة كل عنصر أو عنصر بالعنصر المجاور له ومبادلتهم إذا لزم الأمر. وبكلمات بسيطة ، فإنه يقارن العنصر الأول والثاني من القائمة ويتبادلها ما لم تكن خارج الترتيب المحدد. وبالمثل ، تتم مقارنة العنصر الثاني والثالث ومبادلتهما ، ويمضي هذا المقارنة والتبادل إلى نهاية القائمة. عدد المقارنات في التكرار الأول هو n-1 حيث n هي عناصر الأرقام في صفيف. سيكون العنصر الأكبر في الموضع التاسع بعد التكرار الأول. وبعد كل تكرار ، ينخفض ​​عدد المقارنات ، وفي آخر مرة يتم إجراء مقارنة واحدة فقط.

هذه الخوارزمية هي أبسط خوارزمية الفرز. أفضل تعقيد لحالة (عندما تكون القائمة بالترتيب) من النوع Bubble هو بالترتيب n (على)) ، وأسوأ تعقيد الحالة على²). في أفضل الأحوال ، يكون الترتيب n لأنه يقارن العناصر فقط ولا يقايضها. تتطلب هذه التقنية أيضًا مساحة إضافية لتخزين المتغير المؤقت.

تعريف اختيار الفرز

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

في فرز التحديد ، لا تحدث المصفوفة المصنفة وغير المصنفة أي فرق وتستهلك ترتيبًا n² (على²)) في كلا الوضعين الأسوأ والتعقيد. فرز التحديد أسرع من فرز الفقاعات.

1. في الفرز الفقاعي ، تتم مقارنة كل عنصر والعنصر المجاور له وتبديلهما إذا لزم الأمر. من ناحية أخرى ، يعمل فرز التحديد عن طريق تحديد العنصر ومبادلة ذلك العنصر المحدد بالعنصر الأخير. يمكن أن يكون العنصر المحدد أكبر أو أصغر بناءً على الترتيب ، أي تصاعديًا أو تنازليًا.
2. أسوأ تعقيد الحالة هو نفسه في كل من الخوارزميات ، أي O (n²) ، ولكن أفضل تعقيد هو مختلف. يأخذ ترتيب الفقاعات ترتيبًا زمنيًا n في حين يستهلك فرز التحديد ترتيبًا n² زمن.
3. Bubble sort هي خوارزمية مستقرة ، على النقيض من ذلك ، فإن فرز التحديد غير مستقر.
4. خوارزمية فرز التحديد سريعة وفعالة مقارنة بفرز الفقاعة البطيئة وغير الفعالة.

استنتاج

تعتبر خوارزمية فرز الفقاعات هي الخوارزمية الأكثر بساطة وغير فعالة ، ولكن خوارزمية فرز التحديد تتسم بالكفاءة مقارنةً بترتيب الفقاعات الفقاعية. يستهلك Bubble sort أيضًا مساحة إضافية لتخزين المتغير المؤقت ويحتاج إلى مزيد من المقايضات.