الفصل 3: خوارزميات الفرز

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

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

الفرز الابتدائي

تقوم أبسط خوارزميات الفرز بالعمليات التالية:

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

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

فرز الاختيار

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

الحلقة الداخلية لفرز الاختيارهنا ترجمة الملف إلى اللغة العربية مع الحفاظ على الرموز البرمجية دون ترجمتها:

يُستخدم الفرز للعثور على العنصر الأصغر في الجزء غير المفروز a[i..N-1]. يتم تخزين فهرس العنصر الأصغر في min. ثم، يتم تبادل a[i] مع a[min]، مما يضع العنصر الأصغر في موضعه النهائي. بينما ينتقل الفهرس i من اليسار إلى اليمين، تكون العناصر إلى يساره مرتبة بالفعل في المصفوفة ولن يتم لمسها مرة أخرى.

هنا تنفيذ لفرز الاختيار في Java:

public static void selectionSort(Comparable[] a) {
    // العدد الإجمالي للعناصر في المصفوفة
    int N = a.length;
    for (int i = 0; i < N; i++) {
        // تخزين فهرس العنصر الأصغر
        int min = i;
        for (int j = i+1; j < N; j++) {
            // البحث عن العنصر الأصغر في الجزء غير المفروز
            if (less(a[j], a[min])) min = j;
        }
        // تبادل العنصر الأصغر مع العنصر الحالي
        exch(a, i, min);
    }
}

يستخدم فرز الاختيار حوالي ~N^2/2 مقارنات و N تبادلات لفرز مصفوفة بطول N. وقت التشغيل لا يتأثر بالإدخال - يستغرق نفس الوقت تقريبًا لتشغيل فرز الاختيار لمصفوفة مرتبة بالفعل أو لمصفوفة بجميع المفاتيح متساوية كما هو الحال بالنسبة لمصفوفة عشوائية الترتيب.

فرز الإدراج

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

• إنه فعال للمجموعات البيانية الصغيرة.
• إنه أكثر كفاءة عمليًا من فرز الاختيار.
• إنه مستقر؛ أي أنه لا يغير الترتيب النسبي للعناصر ذات المفاتيح المتساوية.
• إنه في-مكان؛ أي أنه يتطلب فقط كمية ثابتة O(1) من المساحة الإضافية.
• إنه على الإنترنت؛ أي أنه يمكن فرز قائمة عند استلامها.

هنا تنفيذ لفرز الإدراج في Java:

public static void insertionSort(Comparable[] a) {
    // العدد الإجمالي للعناصر في المصفوفة
    int N = a.length;
    for (int i = 1; i < N; i++) {
        // إدراج العنصر الحالي في المكان المناسب
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // تبادل العنصر الحالي مع العنصر السابق
            exch(a, j, j-1);
        }
    }
}

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

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

فرز شل

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

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

فيما يلي تنفيذ لفرز شل في Java:

public class MaxPQ<Key extends Comparable<Key>> {
    // لا تترجم الشفرة، ترجم التعليقات فقط
    // هذه المصفوفة التي تخزن الحد الأقصى للعناصر الأولوية
    private Key[] pq;
    // عدد العناصر في المصفوفة
    private int N;
    
    // إنشاء مصفوفة أولوية بسعة محددة
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    // تحقق مما إذا كانت المصفوفة فارغة
    public boolean isEmpty() {
        return N == 0;
    }
   
    // إدراج عنصر جديد في المصفوفة
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    // إزالة الحد الأقصى من المصفوفة
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    // رفع عنصر إلى أعلى في المصفوفة
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    // خفض عنصر إلى أسفل في المصفوفة
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    // طرق مساعدة أخرى
    private booleaهنا ترجمة الملف إلى اللغة العربية. بالنسبة للشفرة البرمجية، لا تترجم الشفرة، بل ترجم التعليقات فقط:
 
n less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

هذا الشفرة تنفذ كومة ثنائية موجهة للحد الأقصى باستخدام مصفوفة pq لتخزين الشجرة الثنائية المرتبة حسب الكومة. عمليات insert() و delMax() تحافظ على خاصية الكومة باستخدام الطرق المساعدة swim() و sink() لاستعادة ترتيب الكومة من خلال تبادل المفاتيح مع أب أكبر من الطفل أو طفل أكبر من والده على التوالي.

ساعة إيقاف

نوع البيانات المجرد الأكثر فائدة هو ساعة إيقاف بسيطة وفعالة، كما هو موضح على الصفحة المقابلة. لاستخدامها، قم بإنشاء كائن Stopwatch عندما تريد بدء المؤقت، ثم استخدم طريقة elapsedTime() للحصول على الوقت المنقضي بالثواني منذ إنشاء الكائن. التنفيذ يستخدم System.currentTimeMillis() في Java للحصول على الوقت الحالي بالملي ثانية منذ منتصف ليلة 1 يناير 1970.

المتغير المستقل start يسجل الوقت الذي تم فيه إنشاء ساعة الإيقاف، وتستخدم elapsedTime() start لحساب الوقت المنقضي. العميل المعروض هو نموذجي: إنه يقوم بحساب ما ما ويستخدم ساعة الإيقاف لقياس الوقت الذي استغرقه الحساب. نوع البيانات Stopwatch هو تجريد فعال لأنه يفصل بين مفهوم ساعة الإيقاف (الواجهة) وتنفيذها (باستخدام System.currentTimeMillis() في Java). هذا الفصل بين الواجهة والتنفيذ هو سمة أساسية لأنواع البيانات المجردة التي سنراها في جميع أنواع البيانات المجردة في هذا الكتاب.

ملخص

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

• تعريف نوع بيانات مجرد كفئة Java، مع متغيرات مستقلة لتعريف قيم نوع البيانات وطرق مستقلة لتنفيذ العمليات على تلك القيم.
• تطوير تنفيذات متعددة لنفس واجهة البرمجة التطبيقية، باستخدام تمثيلات مختلفة لنفس نوع البيانات المجرد.هنا الترجمة إلى اللغة العربية للملف المقدم:

نوع البيانات المجردة.

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

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