فرز الإدراج في جافا

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

ما هو فرز الإدراج؟

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

• الإدخال: مصفوفة A تحتوي على عناصر رقمية غير مصنفة: A[0,1, n, n-2...].
• الإخراج: مصفوفة تحتوي على نفس الأرقام ولكن مرتبة بالكامل. يُشار إلى هذا عادةً باسم B: B[0]B[1]...B[n-1].

هناك عدة طرق لاستخدام الفرز بالإدراج - فيما يلي الطرق الأكثر شيوعًا:

• الفرز العددي (ترتيب تصاعدي): [1، 2، 3، 4، 5]
• الفرز العددي (ترتيب تنازلي): [5، 4، 3، 2، 1]
• الترتيب الأبجدي: [أ، ب، ج، د]

ملاحظة: إذا كان لديك مصفوفة فارغة أو مصفوفة مفردة، فسيتم اعتبارها مرتبة بشكل افتراضي.

فهم نظرية فرز الإدراج

قبل استكشاف التعليمات البرمجية وراء فرز الإدراج، دعونا نقسم الخوارزمية باستخدام لغة غير تقنية. نظرًا لأننا سنعرض رمز الفرز بترتيب تصاعدي، فمن المنطقي شرح الخوارزمية خطوة بخطوة في هذا المنشور. الخطوة 1. التكرار بين arr[1]وأين arr[n]تكون nقيمة عددية عادة أقل من 10. الخطوة 2. قارن العنصر الذي اخترته (المعروف باسم key) بالرقم السابق في التسلسل باستخدام الطريقة sort(). الخطوة 3. إذا كانت جميع العناصر أصغر من العناصر التي تليها، كرر المقارنة حتى تجد قيمة أكبر. الخطوة 4. قم بتبديل القيمة الأكبر بموضع واحد خلف الموضع الأصغر لإنشاء تسلسل مرتب. الخطوة 5. كرر العملية حتى تحصل على سلسلة مرتبة من الأحرف

فرز المصفوفات البدائية

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

1. قم بتعريف مصفوفة للفرز

في البداية، لنقم بإنشاء سلسلة من القيم التي سنعرضها لاحقًا باستخدام Java. لاستخدام الفرز بالإدراج، تحتاج إلى إنشاء مصفوفة. من أجل ذلك استخدمint[]

int[] arrayA = {10, 14, 20, 30};

2. استخدمsort_arr لتنفيذ الخوارزمية

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

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. قم بإنشاء حلقة ومكرر

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

for(int i=0; i< sort_arr.length; ++i){

الآن بعد أن أصبح لديك حلقة فعالة، فقد حان الوقت لإنشاء مكرر يقوم بفرز جميع العناصر بالترتيب المطلوب. من الآن فصاعدا، سوف نشير إلى المكرر باسم " j".

int j = i;

4. إنشاء "حلقة أثناء"

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

• القيمة المخصصة لـ j يجب أن تكون أكبر من 0
• j-1يجب أن تكون القيمة المخصصة أكبر من jالفهرس

بمجرد تحقق الشرطين في الحلقة، فإن القيمة الأساسية للمصفوفة سوف تساوي الفهرس j.

5. فرز المصفوفة

بعد إعداد حلقة while، سيتم تبديل قيم jand حتى يفشل أحد الشرطين أو كليهما في حلقة while. j-1وبالمثل، سيتم تكرار الفرز لكل قيمة في حلقة for حتى تفشل شروط الحلقة أيضًا. إليك كيفية عمل عملية فرز الإدراج عمليًا:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

فرز قائمة ArrayList

على الرغم من أهمية فهم الرياضيات وراء فرز الإدراج، عندما يتعلق الأمر بتطوير البرامج الواقعية، فسوف تقوم بفرز ArrayLists أكثر بكثير من التسلسلات في المصفوفات البدائية. فيما يلي دليل خطوة بخطوة لفرز ArrayList:

1. قم بإنشاء فئة جديدة Elementللعناصر التي تنتمي إلى المجموعة.

   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }

2. توجد طريقة داخل المجموعة compareTo()- سنستخدمها لمقارنة معرفات عنصرين.

   public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }

3. قم بتطبيق الخوارزمية وإنشاء بعض الحلقات لفرز الكائنات ArrayListبدلاً من مقارنتها.

   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }

4. يمكنك إضافة المزيد من العناصر إلى القائمة ArrayListأيضًا، كما هو موضح أدناه:

   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);

5. والآن حان وقت الفرز:

   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array
   list.forEach(e -> System.out.print(e.getId() + ", "));

6. الآن دعونا نقارن المدخلات والمخرجات للتأكد من أننا لم نرتكب أي أخطاء. فيما يلي مقارنة السلسلة التي استخدمناها كمثال.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

مشاكل ممارسة فرز الإدراج

الآن بعد أن تعرفت على خوارزمية الفرز هذه، فقد حان الوقت لاختبار مهاراتك النظرية والعملية. اختبار نظري رقم 1 لقد تم إعطاؤك مصفوفة [1، 4، 6، 8] وقمت بإضافة عنصر جديد n = 7 إليها. ما هو عدد المقارنات التي ستحتاج إلى إجرائها للحصول على تسلسل مرتب من الأرقام؟ أشر إلى القيمة النهائية للمؤشر n في المصفوفة. الاختبار النظري رقم 2 في مقابلة عمل، يطلب منك قائد الفريق إثبات أن إدراج الفرز هو أسلوب غير فعال. بالنظر إلى سلسلة رقمية من [0، 3، 6، 8، 9]، ما هو ترتيب تسلسل الإدخال الخاص بك لزيادة وقت التشغيل المطلوب للفرز إلى أقصى حد؟ تمرين تدريبي قم بفرز المصفوفة [0، 1، 4، 5، 2، 3، 7، 9، 8] بترتيبها التصاعدي باستخدام الفرز بالإدراج في Java.

خاتمة

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