نوع داخلي: أمثلة على كيفية عمل الخوارزمية

2024 مؤلف: Angel Austin | [email protected]. آخر تعديل: 2024-02-02 14:38

هناك عدة خوارزميات أساسية لحل مشكلة فرز المصفوفة. ومن أشهرها نوع الإدراج. نظرًا لوضوحها وبساطتها ، ولكن كفاءتها منخفضة ، تُستخدم هذه الطريقة بشكل أساسي في تعليم البرمجة. يسمح لك بفهم آليات الفرز الأساسية.

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

جوهر خوارزمية فرز الإدراج هو أنه يتم تكوين مقطع مرتب بشكل صحيح داخل المصفوفة الأولية. تتم مقارنة كل عنصر واحدًا تلو الآخر بالجزء المحدد وإدراجه في المكان الصحيح. وهكذا ، بعد التكرار بين جميع العناصر ، فإنها تصطف بالترتيب الصحيح.

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

قد تبدو بداية الفرز على النحو التالي:

1. خذ العنصر الأول من المصفوفة
2. نظرًا لعدم وجود ما يمكن مقارنته به ، خذ العنصر نفسه كما هو مرتبتسلسل.
3. انتقل إلى العنصر الثاني.
4. قارنها بالأول بناءً على قاعدة الفرز.
5. إذا لزم الأمر ، قم بتبديل العناصر في الأماكن.
6. خذ أول عنصرين كسلسلة مرتبة
7. انتقل إلى العنصر الثالث.
8. قارنها بالثانية ، قم بالتبديل إذا لزم الأمر.
9. إذا تم إجراء الاستبدال ، فقارنه مع الأول.
10. خذ ثلاثة عناصر كتسلسل مرتب.

وهكذا حتى نهاية المصفوفة الأصلية.

نوع الإدراج في الحياة الحقيقية

من أجل الوضوح ، يجدر إعطاء مثال على كيفية استخدام آلية الفرز هذه في الحياة اليومية.

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

الأول هو ورقة نقدية من 1000 روبل ، وبعدها مباشرة - 100. نأخذ مائة ونضعها في المقدمة. الثالث على التوالي 500 روبل والمكان المناسب له بين مائة وألف.

بنفس طريقة فرز البطاقات المستلمة عند لعب "المخادعة" لتسهيل التنقل بينها.

العوامل والوظائف المساعدة

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

العنصر الأول هو نفسه مجموعة مرتبة ، لذا تبدأ المقارنة من الثاني.

غالبًا ما تستخدم الخوارزمية وظيفة مساعدة لتبادل قيمتين (مبادلة). يستخدم متغيرًا مؤقتًا إضافيًا يستهلك الذاكرة ويبطئ الكود قليلاً.

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

أمثلة على التنفيذ

التنفيذ المحدد يعتمد إلى حد كبير على لغة البرمجة المستخدمة وصياغتها وهياكلها.

تنفيذ Classic C باستخدام متغير مؤقت لتبادل القيم:

int i، j، temp؛ لـ (i=1 ؛ i=0 ؛ j--) {if (array [j] < temp) break ؛ صفيف [j + 1]=صفيف [j] ؛ مجموعة [ي]=درجة الحرارة ؛ }}

تطبيق PHP:


function insertion_sort (& $ a) {لـ ($ i=1؛ $ i=0 && $ a [$ j] > $ x؛ $ j--) {$ a [$ j + 1]=$ a [$ j] ؛ } $ a [$ j + 1]=$ x ؛ }}








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


public static void insertionSort (int arr) {for (int i=1؛ i=0 && arr [prevKey] > curElem) {arr [prevKey + 1]=arr [prevKey] ؛ arr [prevKey]=curElem؛ prevKey-- ؛ }}}

المعنى العام للرمز يبقى دون تغيير: كل عنصر من المصفوفة يقارن بالتسلسل مع العناصر السابقة ويتم تبديله معهم إذا لزم الأمر.

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







يمكن حساب العدد الدقيق للتباديل لصفيف غير مرتب تمامًا باستخدام الصيغة:


n(n-1) / 2

، حيث n هو طول المصفوفة الأصلية. وبالتالي ، سوف يتطلب الأمر 4950 تبادلاً لترتيب 100 عنصر بالترتيب الصحيح.
طريقة الإدراج فعالة للغاية لفرز المصفوفات الصغيرة أو المصنفة جزئيًا. ومع ذلك ، لا يوصى بتطبيقه في كل مكان بسبب التعقيد الكبير للحسابات.
تُستخدم الخوارزمية كمساعد في العديد من طرق الفرز الأكثر تعقيدًا.






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





ما ورد أعلاه هو مثال مرئي رائع لفرز الإدراج في الرقص.