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

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

فرز سريع تتبع الخوارزمية نهج Divide and Conquer. يقوم بتقسيم العناصر إلى أجزاء أصغر بناءً على حالة معينة وإجراء الفرز operaعلى تلك الأجزاء الأصغر المقسمة.

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

ما هو الفرز؟

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

الفرز الافتراضي في جافا سكريبت

كما ذكرنا سابقًا، تحتوي JavaScript على فرز(). دعونا نأخذ مثالاً مع مجموعة قليلة من العناصر مثل [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]

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

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

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

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

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

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

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

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

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

  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 shift المؤشر الأيسر إلى اليمين للفهرس 1.

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

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

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

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

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

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

رمز لمبادلة اثنين numbers في JavaScript

مبادلة اثنين numbers في JavaScript

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;
}

تنفيذ العودية operaالإنتاج

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

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

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

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

العودية Operaالإنتاج

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: يعمل الفرز السريع مع Time Complexمدينة من يا (تسجيل الدخول).