خوارزمية الفرز السريع في Javaسيناريو

ما هو الفرز؟

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

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

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

رمز:

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

ما هو سبب اختيار الفرز السريع على الفرز الافتراضي () في Javaسيناريو

على الرغم من أن التابعsort()‎ يعطي النتيجة التي نريدها، إلا أن المشكلة تكمن في الطريقة التي يفرز بها عناصر المصفوفة. الفرز الافتراضي () في Javaاستخدامات البرنامج النصي ترتيب بالإدراج by محرك V8 من كروم دمج الفرز by موزيلا Firefox سفاري.

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

لذا، لكي تفهم الأمر بشكل كامل، عليك أن تعرف كيفية عمل الفرز السريع ودعنا نرى ذلك بالتفصيل الآن.

ما هو الفرز السريع؟

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

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

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

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

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

لذلك، دعونا نرى هذه الخطوات مع مثال. دعونا نفكر في مجموعة العناصر التي نحتاج إلى فرزها هي [5,3,7,6,2,9،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX].

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

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

فيما يلي خطوات إجراء الفرز السريع التي تظهر مع مثال [5,3,7,6,2,9،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX].

الخطوة 1: تحديد المحور كعنصر وسط. لذا، 7 هو العنصر المحوري

الخطوة 2: ابدأ بالمؤشرين الأيسر والأيمن كعنصرين أول وأخير في المصفوفة على التوالي. لذلك، يشير المؤشر الأيسر إلى 5 في الفهرس 0 ويشير المؤشر الأيمن إلى 9 في الفهرس 5.

الخطوة 3: قارن العنصر الموجود عند المؤشر الأيسر مع عنصر المحور. نظرًا لأن 5 < 6 يحول المؤشر الأيسر إلى اليمين إلى المؤشر 1.

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

الخطوة 5: الآن، قارن القيمة عند المؤشر الأيمن مع العنصر المحوري. منذ 9 > 6 حرك المؤشر الأيمن إلى اليسار. الآن بعد أن توقف 2 <6 عن تحريك المؤشر الأيمن.

الخطوة 6: قم بتبديل القيمتين الموجودتين عند المؤشرات اليسرى واليمنى مع بعضهما البعض.

الخطوة 7: حرك كلا المؤشرين خطوة أخرى.

الخطوة 8: بما أن 6 = 6، حرك المؤشرات إلى خطوة أخرى وتوقف عندما يتقاطع المؤشر الأيسر مع المؤشر الأيمن ويعيد مؤشر المؤشر الأيسر.

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

كود لتبادل رقمين في Javaسيناريو

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); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

تنفيذ العملية التكرارية

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

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

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

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

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 result = quickSort(items, 0, items.length - 1);

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

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); //sawpping 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); //prints [2,3,5,6,7,9]

NOTE: يتم تشغيل الفرز السريع مع تعقيد الوقت يا (تسجيل الدخول).