مراجعة واختبار طرق الفرز. الجزء الأول

في أحد الأيام، في التعليقات على فكونتاكتي، تشاجرت مع أحد الطلاب الآخرين في المشروع. كان جوهر النزاع هو "من سيفوز" - طريقة sort()من فئة java.util.Arraysأو تطبيقات مكتوبة ذاتيًا لخوارزميات بسيطة: الفقاعة ، والإدراج ، والاختيار ، والصدفة (خوارزمية Shell). بالنسبة للبعض، قد تكون الإجابة على هذا السؤال واضحة، لكن بما أن الخلاف قد نشأ، رغم أن كل طرف كان لديه «مصادر محترمة» لصالح وجهة نظره، فقد تقرر إجراء دراسة، تمد المادة الرمادية في العملية، وتنفيذ خوارزميات مختلفة. TL;DR: java.util.Arrays.sort() هو الرائد دون قيد أو شرط في المصفوفات التي تحتوي على 100000 عنصر أو أكثر؛ مع حجم أصغر، يمكن لطريقة Shell أن تتنافس معه في بعض الأحيان. بقية الخوارزميات المدروسة فارغة تمامًا ولا يمكن أن تكون مفيدة إلا في ظل بعض الظروف الغريبة. الآن دعونا نلقي نظرة على كيفية فرز المصفوفات في أجهزتنا المصنوعة من السيليكون.

اختيار نوع. الفرز حسب الاختيار

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

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

يُظهر تحليل الخوارزمية أنه من الضروري تمشيط ما تبقى من المصفوفة عند كل تمريرة، أي أننا سنحتاج بالضبط إلى N + (N-1) + (N-2) + ... + 1 = N^ 2/2 مقارنات. وبالتالي، فإن تعقيد الخوارزمية هو O(N^2). ماذا يعني هذا؟ هذا يعني أنه من خلال زيادة عدد العناصر في المصفوفة (N) مرتين، سنزيد وقت تشغيل الخوارزمية ليس بمقدار 2، ولكن بمقدار 2 ^ 2 = 4 مرات. وبزيادة N بمقدار 10 مرات، سنزيد وقت التشغيل بمقدار 100 مرة، وهكذا. على جهاز الكمبيوتر المحمول الخاص بي لعام 2012 المزود بمعالج Core i3 الذي يعمل بنظام التشغيل Ubuntu 14.4، حصلت على وقت التشغيل التالي:

ترتيب بالإدراج. ترتيب بالإدراج

هنا الفكرة مختلفة قليلا. مرة أخرى، دعنا ننتقل إلى الرسوم المتحركة من دكتور سيدجويك: عرض ما هو أمامنا، لم نشاهده بعد، وكل ما نتركه خلفنا يظل دائمًا في محله. النقطة المهمة هي أننا "نعيد" كل عنصر جديد من المصفوفة الأصلية إلى البداية حتى "تستقر" على عنصر أصغر. وبالتالي، لدينا مرة أخرى N تمريرات (لكل عنصر من عناصر المصفوفة الأصلية)، ولكن في كل تمريرة، في معظم الحالات، لا ننظر إلى الباقي بالكامل، ولكن إلى جزء منه فقط. أي أننا سنحصل على الخيار 1 + (N-1) + (N-2) + … + N = N^2/2 فقط إذا كان علينا إعادة كل عنصر تالٍ إلى البداية، أي في هذه الحالة من المدخلات مرتبة "في الاتجاه المعاكس" (سيئ الحظ، سيئ الحظ). في حالة المصفوفة التي تم فرزها بالفعل (هذا هو الحظ) ستكون هناك هدية مجانية كاملة - في كل تمريرة هناك مقارنة واحدة فقط وترك العنصر في مكانه، أي أن الخوارزمية ستعمل في وقت يتناسب مع N. التعقيد سيتم تحديد الخوارزمية من خلال أسوأ حالة نظرية، وهي O(N^2). في المتوسط، سيكون وقت التشغيل متناسبًا مع N^2/4، أي ضعف سرعة الخوارزمية السابقة. في تنفيذي، نظرًا للاستخدام غير الأمثل للتبديل، كان وقت التشغيل أطول من وقت التحديد. وأخطط لتصحيح وتحديث هذا المنصب قريبا. هذا هو الكود ونتيجة تشغيله على نفس الجهاز:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

نوع شل. نوع شل

لاحظ رجل ذكي، دونالد شيل، في عام 1959 أن الحالات الأكثر تكلفة في خوارزمية الإدراج هي عندما يعود العنصر بعيدًا جدًا إلى بداية المصفوفة: في بعض التمريرات نعيد العنصر إلى البداية ببضعة مواقع ، وفي ممر آخر تقريبًا عبر المصفوفة بأكملها إلى البداية يكون بعيدًا وطويلًا. هل من الممكن القيام بذلك مرة واحدة، والقفز من خلال عدة عناصر؟ ووجد مثل هذه الطريقة. وهو يتألف من تنفيذ فرز جزئي خاص بشكل متسلسل، يُطلق عليه عمومًا النوع d، أو، وفقًا لسيدجويك، النوع h (أظن أن h تعني قفزة). 3-الفرز، على سبيل المثال، سوف يقارن العنصر المعني ليس بالعنصر السابق، ولكنه سيتخطى اثنين ويقارن مع المواضع الثلاثة السابقة. إذا تم تغييره، فسيتم مقارنته مرة أخرى مع مواضع العنصر 3 مرة أخرى وهكذا. خلاصة القول هي أن المصفوفة الناتجة ستكون "مرتبة 3"، أي أن الموضع غير الصحيح للعناصر سيكون أقل من 3 مواضع. سيكون العمل مع خوارزمية الإدراج هذه سهلاً وممتعًا. بالمناسبة، "الفرز 1" ليس أكثر من مجرد خوارزمية إدراج =) من خلال تطبيق الترتيب h بشكل تسلسلي على المصفوفة مع قيم h المتناقصة، يمكننا فرز مصفوفة كبيرة بشكل أسرع. إليك ما يبدو عليه الأمر: عرض التحدي هنا هو كيفية اختيار التسلسل الصحيح للفرز الجزئي. في النهاية، يعتمد أداء الخوارزمية على هذا. الأكثر شيوعًا هو التسلسل الذي اقترحه دونالد كنوث: h = h*3 + 1، أي 1، 4، 13، 40، ... وهكذا حتى 1/3 من حجم المصفوفة. يوفر هذا التسلسل أداءً لائقًا كما أنه سهل التنفيذ. يتطلب تحليل الخوارزمية قدرًا كبيرًا من اللغة وهو يتجاوز قدرتي. يتم تحديد نطاق التحليل أيضًا من خلال المتغيرات العديدة لتسلسلات h. تجريبيًا، يمكننا القول أن سرعة الخوارزمية جيدة جدًا - انظر بنفسك: مليون عنصر في أقل من ثانية! وهنا كود جافا مع تسلسل كنوت.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

فقاعة الفرز. طريقة الفقاعة

هذا كلاسيكي! يقوم كل مبرمج مبتدئ تقريبًا بتنفيذ هذه الخوارزمية. إنه فيلم كلاسيكي لدرجة أن الدكتور سيدجويك لم يكن لديه حتى رسوم متحركة له، لذا كان علي أن أقوم بالعمل بنفسي. عرض هنا، في كل تمريرة، نجتاز المصفوفة من البداية إلى النهاية، ونتبادل العناصر المجاورة التي تكون خارج الترتيب. ونتيجة لذلك، فإن أكبر العناصر "تطفو" (ومن هنا الاسم) إلى نهاية المصفوفة. نبدأ كل تمريرة جديدة بتفاؤل على أمل أن تكون المصفوفة مرتبة بالفعل ( sorted = true). وفي نهاية المقطع، إذا رأينا أننا ارتكبنا خطأ، نبدأ مقطعًا جديدًا. تكمن الصعوبة هنا في أننا، مرة أخرى، نجتاز (تقريبًا) المصفوفة بأكملها في كل تمريرة. تحدث المقارنة في كل خطوة، ويتم التبادل في كل خطوة تقريبًا، مما يجعل هذه الخوارزمية واحدة من أبطأ الخوارزميات (إذا اعتبرنا تلك التي تم تنفيذها بشكل عقلاني، وليس "الفرز الهزاز" وغيرها من هذا القبيل). ومن المثير للاهتمام أن التعقيد الرسمي هنا سيكون أيضًا مساويًا لـ O(N^2)، لكن المعامل أعلى بكثير من معاملات الإدخال والتحديد. رمز الخوارزمية:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

وقت التشغيل: اشعر بالفرق: أكثر من نصف ساعة على مليون عنصر! الخلاصة: لا تستخدم هذه الخوارزمية أبدًا!!!

ملخص الجزء الأول

ونتيجة لذلك، أقترح النظر في الجدول العام لهذه الخوارزميات. يمكنك أيضًا المقارنة مع نتائج الطريقة المضمنة java.util.Arrays.sort(). يبدو وكأنه نوع من السحر - ما الذي يمكن أن يكون أسرع من شركة شل؟ سأكتب عن هذا في الجزء التالي. هناك سنلقي نظرة على خوارزميات الفرز السريع المستخدمة على نطاق واسع، بالإضافة إلى الفرز المدمج، والتعرف على الفرق في طرق فرز المصفوفات من الأوليات والأنواع المرجعية، وكذلك التعرف على واجهة مهمة جدًا في هذا الشأن؛) Comparableأدناه يمكنك الدراسة رسم بياني مبني على مقياس لوغاريتمي باستخدام جداول البيانات. كلما كان الخط مسطحًا، كانت الخوارزمية أفضل =) بالنسبة لأولئك الذين يرغبون في تنزيل المشروع بأكمله وإجراء الاختبارات بأنفسهم، احتفظ بالرابط: Java نراكم في الجزء التالي! =)