تنفيذ فرز الفقاعة في جافا

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

مقدمة

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

الفرز من خلال عيون الآلة والعين البشرية

لنتخيل أنك بحاجة إلى فرز 5 أعمدة بارتفاعات مختلفة بترتيب تصاعدي. يمكن أن تعني هذه الأعمدة أي نوع من المعلومات (أسعار الأسهم، النطاق الترددي لقناة الاتصال، وما إلى ذلك)؛ يمكنك تقديم بعض الإصدارات الخاصة بك من هذه المهمة لجعلها أكثر وضوحًا. حسنًا، على سبيل المثال، سنقوم بفرز المنتقمون حسب الارتفاع: على عكس برنامج الكمبيوتر، لن يكون الفرز صعبًا بالنسبة لك، لأنك قادر على رؤية الصورة بأكملها ويمكنك على الفور معرفة البطل الذي يجب نقله إلى أي مكان حتى يتم إكمال الفرز حسب الارتفاع بنجاح. ربما خمنت بالفعل أنه لفرز بنية البيانات هذه بترتيب تصاعدي، يكفي تبديل أماكن Hulk و Iron Man:

منتهي!

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

• قارن بين عنصرين؛
• مبادلة أو نسخ واحد منهم؛
• انتقل إلى العنصر التالي؛

يمكن للخوارزميات المختلفة تنفيذ هذه العمليات بطرق مختلفة، لكننا سننتقل للنظر في كيفية عمل فرز الفقاعات.

خوارزمية فرز الفقاعة

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

• تنتقل إلى العنصر صفر في مصفوفتنا (الأرملة السوداء)؛
• قارن العنصر الصفري (الأرملة السوداء) بالعنصر الأول (هالك)؛
• إذا كان العنصر الموجود في الموضع صفر أعلى، يمكنك تبديله؛
• وإلا، إذا كان العنصر عند الموضع صفر أصغر، فإنك تتركه في أماكنه؛
• انتقل إلى الموضع الموجود على اليمين وكرر المقارنة (قارن الهيكل بالكابتن)

بعد مراجعة القائمة بأكملها في مسار واحد باستخدام هذه الخوارزمية، لن يكتمل الفرز بالكامل. ولكن من ناحية أخرى، سيتم نقل العنصر الأكبر في القائمة إلى أقصى الموضع الأيمن. سيحدث هذا دائمًا، لأنه بمجرد العثور على العنصر الأكبر، ستقوم بتغيير الأماكن باستمرار حتى تقوم بنقله إلى النهاية. أي أنه بمجرد أن "يجد" البرنامج الهيكل في المصفوفة، فإنه سينقله إلى نهاية القائمة: ولهذا السبب تسمى هذه الخوارزمية بفرز الفقاعات، لأنه نتيجة لعملها، سيكون العنصر الأكبر في القائمة في أعلى المصفوفة، وسيتم إزاحة جميع العناصر الأصغر موضعًا واحدًا إلى اليسار: لإكمال الفرز، ستحتاج إلى العودة إلى بداية المصفوفة وتكرار الخطوات الخمس الموضحة أعلاه مرة أخرى، والانتقال مرة أخرى من اليسار إلى اليمين، ومقارنة العناصر وتحريكها حسب الضرورة. لكن هذه المرة تحتاج إلى إيقاف الخوارزمية بعنصر واحد قبل نهاية المصفوفة، لأننا نعلم بالفعل أن العنصر الأكبر (Hulk) موجود تمامًا في أقصى اليمين: لذلك يجب أن يحتوي البرنامج على حلقتين. لمزيد من الوضوح، قبل أن ننتقل إلى مراجعة كود البرنامج، يمكنك مشاهدة تصور لكيفية عمل فرز الفقاعات على هذا الرابط: تصور لكيفية عمل فرز الفقاعات

تنفيذ فرز الفقاعة في جافا

لتوضيح كيفية عمل الفرز في Java، إليك رمز البرنامج:

• إنشاء مجموعة من 5 عناصر؛
• يرفع صعود المنتقمين فيه؛
• يعرض محتويات المصفوفة؛
• ينفذ نوع الفقاعة؛
• يعيد عرض المصفوفة التي تم فرزها.

يمكنك عرض الكود أدناه، وحتى تنزيله في IntelliJ IDE المفضل لديك. وسيتم تحليلها أدناه:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

على الرغم من التعليقات التفصيلية في الكود، إلا أننا نقدم وصفًا لبعض الطرق المقدمة في البرنامج. تتم كتابة الطرق الرئيسية التي تنفذ العمل الرئيسي في البرنامج في فئة ArrayBubble. يحتوي الفصل على مُنشئ وعدة طرق:

• into- طريقة إدراج العناصر في مصفوفة؛
• printer- يعرض محتويات المصفوفة سطرًا تلو الآخر؛

• toSwap– إعادة ترتيب العناصر إذا لزم الأمر. للقيام بذلك، يتم استخدام متغير مؤقت dummy، حيث يتم كتابة قيمة الرقم الأول، وبدلا من الرقم الأول يتم كتابة قيمة الرقم الثاني. ثم تتم كتابة محتويات المتغير المؤقت إلى الرقم الثاني. هذه تقنية قياسية لتبديل عنصرين؛

  وأخيرا الطريقة الرئيسية:

• bubbleSorter- الذي يقوم بالعمل الرئيسي ويفرز البيانات المخزنة في المصفوفة، وسوف نقدمها بشكل منفصل مرة أخرى:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

هنا يجب الانتباه إلى عدادين: خارجي outوداخلي in. يبدأ العداد الخارجيout بتعداد القيم من نهاية المصفوفة ويتناقص تدريجيًا بمقدار واحد مع كل تمريرة جديدة. outمع كل تمريرة جديدة، يتم إزاحة المتغير إلى اليسار أكثر حتى لا يؤثر على القيم التي تم فرزها بالفعل على الجانب الأيمن من المصفوفة. يبدأ العداد الداخليin بتعداد القيم من بداية المصفوفة ويزداد تدريجيًا بمقدار واحد في كل مسار جديد. وتحدث الزيادة inحتى تصل إلى out(آخر عنصر تم تحليله في التمرير الحالي). تقارن الحلقة الداخلية inخليتين متجاورتين inو in+1. إذا inتم تخزين رقم أكبر من in+1، فسيتم استدعاء الطريقة toSwap، والتي تقوم بتبديل أماكن هذين الرقمين.

خاتمة

تعد خوارزمية فرز الفقاعة واحدة من أبطأ الخوارزميات. إذا كانت المصفوفة تتكون من عناصر N، فسيتم إجراء مقارنات N-1 في التمريرة الأولى، وN-2 في التمريرة الثانية، ثم N-3، وما إلى ذلك. أي أنه سيتم إجراء إجمالي عدد التمريرات: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 وهكذا، عند الفرز، الخوارزمية ينفذ حوالي 0.5x(N ^2) مقارنات. بالنسبة لـ N = 5، سيكون عدد المقارنات حوالي 10، وبالنسبة لـ N = 10 سيزيد عدد المقارنات إلى 45. وبالتالي، مع زيادة عدد العناصر، يزداد تعقيد الفرز بشكل كبير: لا تتأثر سرعة الخوارزمية بعدد التمريرات فحسب، بل أيضًا بعدد التباديل التي يجب إجراؤها. بالنسبة للبيانات العشوائية، متوسط ​​عدد التباديل (N^2) / 4، وهو ما يعادل نصف عدد التمريرات تقريبًا. ومع ذلك، في أسوأ الحالات، يمكن أن يكون عدد التباديل أيضًا N^2 / 2 - وهذا هو الحال إذا تم فرز البيانات في البداية بترتيب عكسي. على الرغم من أن هذه خوارزمية فرز بطيئة إلى حد ما، فمن المهم جدًا معرفة وفهم كيفية عملها، وكما ذكرنا سابقًا، فهي الأساس لخوارزميات أكثر تعقيدًا. ججد!