يعتبر الفرز عملية أساسية يتم فيها ترتيب عناصر المصفوفة بترتيب معين لتعزيز إمكانية البحث عنها. بكلمات بسيطة ، يتم فرز البيانات بحيث يمكن البحث عنها بسهولة.
رسم بياني للمقارنة
| أساس للمقارنة | ترتيب بالإدراج | اختيار نوع |
|---|---|---|
| الأساسية | يتم فرز البيانات عن طريق إدخال البيانات في ملف موجود موجود. | يتم فرز البيانات عن طريق اختيار ووضع العناصر المتتالية في موقع مفروز. |
| طبيعة | مستقر | غير مستقر |
| عملية يجب اتباعها | العناصر معروفة مسبقًا بينما يتم البحث عن الموقع لوضعها. | الموقع معروف سابقًا أثناء البحث عن العناصر. |
| بيانات فورية | نوع الإدراج هو تقنية الفرز المباشر التي يمكنها التعامل مع البيانات الفورية. | لا يمكن التعامل مع البيانات الفورية ، يجب أن تكون موجودة في البداية. |
| أفضل تعقيد الحالة | على) | يا (ن 2 ) |
تعريف تصنيف الإدراج
يعمل الفرز الإدراج عن طريق إدراج مجموعة من القيم في الملف الذي تم فرزه الموجودة. يقوم بإنشاء الصفيف الذي تم فرزه عن طريق إدخال عنصر واحد في كل مرة. تستمر هذه العملية حتى يتم فرز مجموعة كاملة في بعض الترتيب. المفهوم الأساسي وراء فرز الإدراج هو إدراج كل عنصر في مكانه المناسب في القائمة النهائية. يحفظ أسلوب الفرز الإدراج مقدار فعال من الذاكرة.
تعمل من نوع الإدراج
- ويستخدم مجموعتين من المصفوفات حيث يقوم أحدهما بتخزين البيانات التي تم فرزها والأخرى على البيانات التي لم يتم فرزها.
- تعمل خوارزمية الفرز حتى تكون هناك عناصر في المجموعة التي لم يتم فرزها.
- لنفترض أن هناك عناصر عدد 'n' في الصفيف. في البداية ، يوجد العنصر ذو الفهرس 0 (LB = 0) في المجموعة التي تم فرزها. العناصر المتبقية موجودة في القسم الذي لم يتم فرزه من القائمة.
- يحتوي العنصر الأول للجزء الذي لم يتم فرزه على فهرس مصفوفة 1 (إذا كان LB = 0).
- بعد كل تكرار ، فإنه يختار العنصر الأول للقسم الذي لم يتم فرزه ويدرجه في المكان المناسب في المجموعة التي تم فرزها.
مزايا الإدراج الفرز
- يتم تنفيذها بسهولة وكفاءة عالية عند استخدامها مع مجموعات صغيرة من البيانات.
- متطلبات مساحة الذاكرة الإضافية لفرز الإدراج أقل (أي ، O (1)).
- ويعتبر بمثابة أسلوب فرز مباشر حيث يمكن فرز القائمة عند استلام العناصر الجديدة.
- إنه أسرع من خوارزميات الفرز الأخرى.
مثال:
تعريف فرز التحديد
يؤدي فرز الاختيار إلى إجراء الفرز عن طريق البحث عن أدنى قيمة للقيمة ووضعها في الموضع الأول أو الأخير وفقًا للترتيب (تصاعدي أو تنازلي). تستمر عملية البحث عن الحد الأدنى للمفتاح ووضعه في الوضع المناسب حتى يتم وضع جميع العناصر في الموضع الصحيح.
العمل من اختيار التصنيف
- افترض صفيف ARR مع عناصر N في الذاكرة.
- في التمريرة الأولى ، يتم البحث عن أصغر المفتاح مع موضعه ، ثم يتم تبديل ARR [POS] مع ARR [0]. لذلك ، يتم فرز ARR [0].
- في التمريرة الثانية ، يتم تحديد موضع أصغر قيمة في فرعي عناصر N-1. تبادل ARR [POS] مع ARR [1].
- في التمريرة N-1 ، يتم تنفيذ نفس العملية لفرز عدد N من العناصر.
مثال:
الاختلافات الرئيسية بين فرز الإدراج واختيار الفرز
- عادة ما يقوم فرز الإدراج بتنفيذ عملية الإدراج. بل على العكس ، فإن فرز الاختيار يقوم باختيار وتحديد العناصر المطلوبة.
- ويقال أن الإدراج الإدراج مستقرًا بينما لا يكون فرز التحديد خوارزمية مستقرة.
- في خوارزمية الفرز الإدراج العناصر معروفة مسبقاً. في المقابل ، يحتوي اختيار الفرز على الموقع مسبقًا.
- تصنيف الإدراج هو أسلوب فرز مباشر حيث يتم فرز العناصر القادمة في القائمة فورًا ، بينما لا يعمل فرز التحديد بشكل جيد مع البيانات الفورية.
- يكون لفرز الإدراج وقت تشغيل (O) في أفضل حالة. مقابل ، أفضل وقت تشغيل حالة تعقيد فرز الفرز هو O (n2).
تعقيد الإدراج الفرز
أفضل تعقيدات حالة لفرز الإدراج هو O (n) مرة ، أي عندما يتم فرز الصفيف مسبقًا. بنفس الطريقة ، عندما يتم فرز المصفوفة بترتيب عكسي ، يجب مقارنة العنصر الأول من المصفوفة التي لم يتم فرزها مع كل عنصر في المجموعة التي تم فرزها. لذا ، في أسوأ الحالات ، يكون وقت تشغيل الإدراج الإدراج تربيعيًا ، أي ، O (n2) . في الحالة المتوسطة أيضًا ، يجب عليها إجراء المقارنات الدنيا (k-1) / 2. وبالتالي ، فإن الحالة المتوسطة لها أيضًا وقت تشغيل تربيعي O (n2).
تعقيد فرز التحديد
كعمل التحديد ، لا يعتمد الفرز على الترتيب الأصلي للعناصر في المصفوفة ، لذلك لا يوجد فرق كبير بين أفضل حالة وتعقيد الحالة الأسوأ من نوع الفرز.
يقوم اختيار الفرز بتحديد عنصر الحد الأدنى للقيمة ، في عملية الاختيار يتم فحص كل عدد "n" من العناصر ؛ لذلك يتم إجراء مقارنات n-1 في التمريرة الأولى. ثم ، يتم تبادل العناصر. وبالمثل في الممر الثاني أيضا للعثور على ثاني أصغر عنصر نحتاج إلى مسح بقية عناصر n-1 وتستمر العملية حتى يتم فرز المصفوفة بأكملها.
وبالتالي ، فإن تعقيد وقت التشغيل لفرز الاختيار هو O (n2) .
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = O (n2)
استنتاج
من بين كل من خوارزمية الفرز ، يكون فرز الإدراج سريعًا وفعالًا ومستقرًا ، بينما لا يعمل فرز التحديد بكفاءة إلا عندما تكون مجموعة صغيرة من العناصر متضمنة أو تم فرز القائمة جزئيًا من قبل. يكون عدد المقارنات التي يتم إجراؤها بواسطة فرز التحديد أكبر من الحركات التي يتم إجراؤها بينما في الفرز ، يتم فرز عدد المرات التي يتم فيها تحريك عنصر أو تبديله أكبر من المقارنات التي أجريت.
