خوارزمية الفرز السريع في Javaنص برمجي مع مثال

ما هو التصنيف السريع؟

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

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

ثلاث خصائص تحدد خوارزمية الفرز السريع:

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

ما هو الفرز؟

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

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

الترتيب الافتراضي في Javaسيناريو

كما ذكر آنفا، Javaيوفر البرنامج النصي فرز()خذ مصفوفة صغيرة مثل [5,3,7,6,2,9] التي تريد ترتيبها تصاعديًا. استدعِ الدالة فرز() يبدو أن الدالة على المصفوفة تفعل ذلك بالضبط.

تُظهر لقطة الشاشة أعلاه وحدة تحكم المتصفح وهي تطبع المصفوفة المرتبة. إليك نفس الكود:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

الإخراج:

[ 2, 3, 5, 6, 7, 9 ]

تلك النتيجة صحيحة، ولكن بالصدفة فقط. تقوم الدالة Array.prototype.sort() بتحويل كل عنصر إلى سلسلة نصية ثم تقارن السلاسل النصية. إلا إذا قمت بتوفير دالة مقارنة. كل قيمة في هذه المصفوفة عبارة عن رقم واحد، لذا فإن ترتيب السلسلة النصية يتطابق مع الترتيب الرقمي. غيّر البيانات وسيختفي هذا الوهم.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

الإخراج:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

ما هي الخوارزمية التي تستخدمها الدالة sort()؟

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

• V8 (Chrome، Edge، Node.js) يستخدم تيمسورت منذ الإصدار V8 7.0، تم تضمينه في متصفح Chrome 70.
• القرد العنكبوت (Firefox) الاستخدامات دمج الفرز.
• Javaسكريبت كور (سفاري) يستخدم أيضًا دمج الفرز.

منذ إصدار ES2019، تضمن اللغة أن sort() is مستقروهذا يستبعد استخدام خوارزمية الفرز السريع البسيطة داخل المحرك. يحتاج الفرز القائم على الدمج إلى ذاكرة إضافية بسعة O(n)، ويجب أن يستدعي دالة الفرز الخاصة بك. Javaيُستخدم مُقارن برمجي لكل عملية مقارنة. تقوم خوارزمية الفرز السريع الرقمية المكتوبة يدويًا بمقارنة الأرقام مباشرةً وفرزها في مكانها، مما يجعلها فعّالة مع المصفوفات الرقمية الكبيرة. استغرق فرز مليون عدد صحيح عشوائي على Node.js 22 ما يقارب مللي 100 مع الفرز السريع أدناه وتقريبًا مللي 210 مع sort((a, b) => a - b).

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

كيف تعمل خوارزمية الفرز السريع؟

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

1. أعثر على محور عنصر في المصفوفة.
2. ابدأ المؤشر الأيسر عند العنصر الأول من النطاق.
3. ابدأ المؤشر الأيمن عند العنصر الأخير من النطاق.
4. قارن العنصر الموجود عند المؤشر الأيسر بالعنصر المحوري. إذا كان أصغر من العنصر المحوري، حرك المؤشر الأيسر خطوة واحدة إلى اليمين. استمر حتى يصبح العنصر الأيسر أكبر من أو يساوي العنصر المحوري.
5. قارن العنصر الموجود عند المؤشر الأيمن بالعنصر المحوري. إذا كان أكبر من العنصر المحوري، حرك المؤشر الأيمن خطوة واحدة إلى اليسار. استمر حتى يصبح العنصر الأيمن أصغر من أو يساوي العنصر المحوري.
6. إذا كان المؤشر الأيسر لا يزال أقل من أو يساوي المؤشر الأيمن، فقم بتبديل العنصرين.
7. زيادة المؤشر الأيسر وإنقاص المؤشر الأيمن.
8. إذا كان الفهرس الأيسر لا يزال أقل من أو يساوي الفهرس الأيمن، فكرر العملية من الخطوة 4. وإلا، فأرجع فهرس المؤشر الأيسر.

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

كيفية تحديد عنصر المحور

يُعد اختيار نقطة الارتكاز القرار الوحيد الذي يفصل بين خوارزمية الفرز السريع والبطيء. إذا كنت دائمًا تختار أول ينتج عن عنصر في مصفوفة مرتبة مسبقًا أسوأ تقسيم ممكن: جانب فارغ وجانب آخر يحتوي على كل عنصر متبقٍ. هذا يجعل الخوارزمية من رتبة O(n²). بأخذ وسط العنصر (طول المصفوفة مقسومًا على اثنين) يتجنب هذا المأزق بالنسبة للمدخلات المرتبة والمرتبة عكسيًا، ولهذا السبب يستخدمه الكود أدناه.

استراتيجيات التحول الشائعة:

• العنصر الأول أو الأخير: الأسهل في البرمجة، ولكن O(n²) على البيانات المصنفة.
• العنصر الأوسط: خيار افتراضي جيد يتعامل مع المصفوفات المرتبة والمصفوفات المرتبة عكسيًا في O(n log n).
• عنصر عشوائي: يجعل ذلك من المستحيل إنشاء مدخلات أسوأ الحالات مسبقًا.
• الوسيط لثلاثة: يأخذ الوسيط للقيم الأولى والوسطى والأخيرة؛ وهو الخيار القياسي في مكتبات الإنتاج.

الآن قم باستعراض خوارزمية الفرز السريع على المصفوفة [5,3,7,6,2,9].

الخطوة 1: العنصر المحوري هو العنصر الأوسط. مع اليسار = 0 واليمين = 5، Math.floor((5 + 0) / 2) يعطي الفهرس 2، لذا فإن قيمة المحور هي 7.

الخطوة 2: ابدأ المؤشرات من نهايتي المصفوفة. المؤشر الأيسر عند الفهرس 0 (القيمة 5) والمؤشر الأيمن موجود عند الفهرس 5 (القيمة 9).

الخطوة 3: قارن القيمة اليسرى بالقيمة المحورية. 5 < 7، لذا انتقل إلى اليمين إلى الفهرس 1. 3 < 7، لذا انتقل إلى اليمين إلى الفهرس 2. القيمة هناك هي 7، وهي ليست أقل من القيمة المحورية، لذا يتوقف المؤشر الأيسر عند الفهرس 2.

الخطوة 4: قارن القيمة اليمنى بالقيمة المحورية. 9 > 7، لذا انتقل إلى اليسار إلى الفهرس 4. القيمة هناك هي 2، وهي ليست أكبر من القيمة المحورية، لذا يتوقف المؤشر الأيمن عند الفهرس 4.

الخطوة 5: بما أن الفهرس الأيسر (2) أصغر من أو يساوي الفهرس الأيمن (4)، فقم بتبديل القيمتين. يصبح شكل المصفوفة كالتالي: [5,3,2,6,7,9].

الخطوة 6: حرك كلا المؤشرين خطوة واحدة إلى الداخل. أصبح المؤشر الأيسر الآن عند الفهرس 3 والمؤشر الأيمن عند الفهرس 3.

الخطوة 7: كرر عملية المسح. القيمة عند الفهرس 3 هي 6، و6 < 7، لذا ينتقل المؤشر الأيسر إلى الفهرس 4. القيمة عند الفهرس 3 ليست أكبر من نقطة الارتكاز، لذا يبقى المؤشر الأيمن عند الفهرس 3.

الخطوة 8: أصبح المؤشر الأيسر (4) الآن أكبر من المؤشر الأيمن (3)، لذا تنتهي الحلقة وتعود الدالة 4كل شيء قبل الفهرس 4 أصغر من أو يساوي المحور، وكل شيء من الفهرس 4 فصاعدًا أكبر من أو يساويه.

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

Code لتبديل اثنين Numbers in Javaسيناريو

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

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

الإخراج:

[ 9, 3, 7, 6, 2, 5 ]

Code لإجراء عملية التقسيم

يحوّل الكود الموضح في لقطة الشاشة أعلاه الخطوات من 1 إلى 8 إلى دالة. الحلقات تقدم المؤشرات، if تقوم الكتلة بعملية التبديل، وتقوم الدالة بإرجاع فهرس التقسيم.

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

الإخراج:

[ 5, 3, 2, 6, 7, 9 ]
4

تتطابق المخرجات مع الدليل الإرشادي تمامًا: بعد عملية تقسيم واحدة، تكون المصفوفة [5,3,2,6,7,9] ويكون فهرس التقسيم المُعاد هو 4.

نفّذ العملية التكرارية Operaالإنتاج

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

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

لذا تتصل بـ تقسيم() الدالة الموضحة أعلاه، واستخدام قيمتها المُعادة لتقسيم مجموعة إلى أجزاء. إليك الكود الذي يقوم بذلك:

لاحظ شرطي الحماية الموضحين في لقطة الشاشة. left < index - 1 يؤكد ذلك أن عنصرين على الأقل ما زالا موجودين على الجانب الأيسر، و index < right يؤكد ذلك الأمر نفسه بالنسبة للجانب الأيمن. بدون هذه الشروط، ستستمر الدالة في استدعاء نفسها إلى ما لا نهاية على نطاقات العناصر المفردة.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

الإخراج:

[ 2, 3, 5, 6, 7, 9 ]

فرز سريع كامل Code

يؤدي تجميع أجزاء التبديل والتقسيم والتكرار معًا إلى الحصول على التنفيذ الكامل:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

الإخراج:

[ 2, 3, 5, 6, 7, 9 ]

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

تعقيد الوقت والمساحة لخوارزمية الفرز السريع

تُعالج كل عملية تقسيم كل عنصر في النطاق مرة واحدة، لذا فإن تكلفة العملية الواحدة هي O(n). وبالتالي، تعتمد التكلفة الإجمالية على عدد مرات تقسيم المصفوفة قبل أن تصبح النطاقات تافهة.

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

يُؤكد هذا الأمر رقمان. فعملية فرز 4,096 قيمة عشوائية باستخدام الكود المذكور أعلاه استلزمت ما يقارب 65,000 مقارنة، مقابل قيمة نظرية n·log₂(n) تساوي 49,152، ووصل أعمق تكرار إلى 24 إطارًا بينما قيمة log₂(4096) تساوي 12. يقع كلا الرقمين ضمن عامل ثابت صغير متوقع لخوارزمية من رتبة O(n log n).

الفرز السريع مقابل أنواع الفرز الأخرى Algorithms

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

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

كيفية فرز الكائنات والسلاسل النصية بسرعة

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

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

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

الإخراج:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

ثلاثة تفاصيل جديرة بالملاحظة. أصبح حارس التكرار الآن left >= rightوهذا صحيح لأي نطاق ولا يعتمد على طول المصفوفة الخارجية. تستخدم مقارنة السلاسل النصية localeCompare() بحيث يتم التعامل مع الأحرف المُشكّلة وحالة الأحرف بشكل صحيح بدلاً من استخدام رمز البرنامج الخام. ولأنّ خوارزمية الفرز السريع غير مستقرة، فقد تتبادل السجلات التي تتشارك نفس الراتب أماكنها؛ لذا يُنصح بالفرز باستخدام مفتاح ثانٍ لكسر التعادل إذا كان الترتيب الأصلي مهمًا بالنسبة لك.

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

الأسئلة الشائعة