👨🏾‍🎓 ⛎ ✈️ فرز المكتبة 🤽🏾 👩🏽‍🏭 ℹ️

خذ مصفوفة ذات ترتيب عكسي وقم بتطبيق الفرز عليها باستخدام إدخالات بسيطة .

انظر مع الصرير الذي يتم إدخال العنصر التالي في المكان الصحيح. لذلك ، تحتاج إلى تحرير مكان الإدراج ، حيث يجب عليك نقل جميع العناصر المدرجة مسبقًا.

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

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

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

خوارزمية

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

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

حجم الصفيف الإضافي

في حين لا يوجد رأي ثابت ، كم عدد المرات التي يجب أن تكون فيها المجموعة المساعدة أكبر من المجموعة الرئيسية.

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

إذا قررنا عدد المرات التي يكون فيها الصفيف المساعد أكبر من الصفيف الرئيسي ، فستبدو صيغة تحديد العدد الدقيق للعناصر كما يلي:

NewSize = ε × (الحجم + 1) - 1

NewSize - عدد العناصر في الصفيف المساعد
ε - عدد المرات التي يكون فيها الصفيف المساعد أكبر من الصفيف الرئيسي
الحجم - عدد العناصر في الصفيف الرئيسي

إذا قمنا ببساطة بضرب الحجم بعامل: NewSize = Size × ε ، فعند التوزيع الموحد لن يكون لدينا ما يكفي من الخلايا في كمية ε - 1 قطعة. أي أنه من الممكن ترتيبها بالتساوي ، ولكن سيتم تحديد أول خلية مملوءة أو الأخيرة بالقرب من حافة الصفيف المساعد. ونحتاج إلى الأماكن الفارغة في الخلايا المملوءة ليتم حجزها من جميع الجوانب - بما في ذلك قبل العنصر الأول وبعد العنصر الأخير.

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

البحث عن مكان الإدراج في مصفوفة مساعدة

بالطبع ، هنا تحتاج إلى بحث ثنائي. ومع ذلك ، لن ينجح التطبيق الكلاسيكي بالنسبة لنا.

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

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

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

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

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

إعادة توازن الصفيف

البحث الثنائي ليس أصعب شيء يمكن تنفيذه في هذا التصنيف. لا يزال هناك إعادة التوازن.

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

علاوة على ذلك ، فإن إعادة التوازن محلية أو كاملة .

إعادة التوازن المحلي

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

هناك فروق دقيقة محتملة. على سبيل المثال ، ما هي الطريقة للبحث عن أقرب مكان شاغر؟ من أجل تجنب الموقف عندما يكون التحول مستحيلًا (أي ، إذا كانت جميع الخلايا مشغولة في بعض الجوانب حتى حافة الصفيف) ، يمكنك التركيز على موضع نقطة الإدراج بالنسبة إلى منتصف الصفيف. إذا كنت بحاجة إلى الإدراج على الجانب الأيسر من المصفوفة ، فانتقل إلى اليمين ، إذا كان على اليمين - إلى اليسار. إذا كانت ε ≥ 2 ، فإن هذا النهج يلغي الحالة التي يكون فيها التحول مستحيلاً (لأنه في نصف الصفيف المساعد هناك أكثر من مساحة كافية لجميع العناصر).

في تفسير المؤلف للخوارزمية ، فإن إعادة التوازن المحلي ضمنيًا.

إعادة توازن كاملة

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

لقد جربت كلا الخيارين وحتى الآن ألاحظ أنه مع إعادة التوازن المحلي ، تعمل الخوارزمية أسرع 1.5-2 مرة من الخيار الكامل. ومع ذلك ، يمكن أن تكون إعادة التوازن الكاملة مفيدة. على سبيل المثال ، إذا كان عليك القيام بإعادة التوازن المحلي في كثير من الأحيان ، فهذا يعني أنه في الصفيف في بعض المناطق تراكمت "جلطات الدم" التي تمنع العملية بأكملها. تتيح لك إعادة التوازن الكاملة التي تتم مرة واحدة ، التخلص من كل الازدحام المحلي في ضربة واحدة.

دعونا نكتشف كيفية إعادة التوازن تمامًا.

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

م - عدد الخلايا التي يمكن تخصيصها لكل عنصر
NewSize - حجم الصفيف المساعد
العدد - العدد الحالي للعناصر غير الفارغة في الصفيف المساعد

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

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

NewPos = الرقم × م

NewPos - موضع عنصر جديد بعد إعادة التوازن
الرقم - ما هو العنصر غير الفارغ في الصفيف المساعد (1 ≤ رقم ≤ عدد)
م - عدد الخلايا المخصصة لكل عنصر

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

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

حالة متدهورة

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

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

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

يعالج فرز المكتبة مجموعات البيانات العشوائية بكفاءة. يؤدي الترتيب الجزئي (المباشر والعكس) إلى إعاقة أداء السرعة.

التعقيد الخوارزمي

في مجموعات كبيرة من البيانات العشوائية ، تعطي الخوارزمية تعقيد الوقت O ( n log n ). ليس سيئًا على الإطلاق!

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

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

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

السبل الممكنة للتحسين

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

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

يعد البحث عن "فرز المكتبات" أكثر متعة - في العينة ستجد الفرزات المختلفة المضمنة في مكتبات مختلفة ، ومع ذلك ، لن تكون هذه الخوارزميات مرتبطة بفرز المكتبات الأصلي .

وهناك شيء يجب تحسينه:

الاختيار التجريبي للمعامل الأمثل ε .
تعديل (مع الأخذ في الاعتبار تفاصيل الخوارزمية العامة) للبحث الثنائي لتحديد أكثر كفاءة لنقطة الإدراج.
تقليل تكاليف إعادة التوازن.

إذا قمت بتلميع هذه الأماكن ، فربما فرز المكتبة بسرعة حتى يساوي فرز سريع؟

كود المصدر

لم أتمكن من إعداد التطبيق في Python ، هناك إصدار يعمل في PHP.

الخوارزمية الأساسية

function LibrarySort($arr) { global $arr_new;//  $e = 3;//     $rebalance_local = true;// (true)   (false)  //   $newSize = $e * (count($arr) + 1) - 1; $arr_new = array_fill(0, $newSize, null); //       $arr_new[LibrarySort_Pos(1, 1, $newSize)] = $arr[0]; //    -    //     $start = 0; $finish = $newSize - 1; $i = 1; //      while($i < count($arr)) { //        $pos = LibrarySort_BinarySearch($arr[$i], $start, $finish, $newSize); if($pos === false) {//        //    LibrarySort_Rebalance_Total($i, $newSize); } else {//  ,   ,    if($arr_new[$pos] !== null) {//   if($rebalance_local) {//  (+ ) LibrarySort_Rebalance_Local($arr[$i++], $pos, $newSize); } else {//  LibrarySort_Rebalance_Total($i, $newSize); } } else {//   ,   $arr_new[$pos] = $arr[$i++]; } } } //      $pos = 0; for($i = 0; $i <= $newSize - 1; $i++) { if($arr_new[$i] !== null) $arr[$pos++] = $arr_new[$i]; } return $arr; }

الموضع الجديد للعنصر في الصفيف الإضافي بعد إعادة التوازن الكاملة

 // $number-    $count //     //$number -      ( )  //$count -       //$newSize -     //$number <= $count <= count($arr) <= $newSize) function LibrarySort_Pos($number, $count, $newSize) { return $number * floor(($newSize + 1) / ($count + 1)) - 1; }

البحث الثنائي عن مكان الإدراج في مصفوفة مساعدة

 //       //$search -     ,      //($start, $finish) -   ,     //$newSize -     function LibrarySort_BinarySearch($search, $start, $finish, $newSize) { global $arr_new;//  //      //      ,     //  ,       while($arr_new[$start] === null && $start < $newSize - 1) { ++$start; } //         , //         if($search == $arr_new[$start]) { return LibrarySort_PosNearby($start, $newSize); //  ,        } elseif($search < $arr_new[$start]) { //      //     if($start > 0) {// $start    $finish = $start; $start = 0; return floor(($start + $finish) / 2); } else {//$start == 0,      return $start;//    ,    } } //      ,     //  ,       while($arr_new[$finish] === null && $finish > 0) { --$finish; } //         , //         if($search == $arr_new[$finish]) { return LibrarySort_PosNearby($finish, $newSize); //  ,        } elseif($search > $arr_new[$finish]) { //      //     if($finish < $newSize - 1) {// $finish    $start = $finish; $finish = $newSize - 1; return ceil(($start + $finish) / 2); } else {//$finish == $newSize - 1,      return $finish;//    ,    } } //     , //,    -   //   ,       If($finish - $start > 1) {//   ,    3  $middle = ceil(($start + $finish) / 2); //   $middle_Pos = 0; // ""     $offset = 0; //         //,    /,      while($middle - $offset > $start && $middle_Pos == 0){ if($arr_new[$middle - $offset] !== null) { $middle_Pos = $middle - $offset; } elseif($middle + $offset < $finish && $arr_new[$middle + $offset] !== null) { $middle_Pos = $middle + $offset; } ++$offset; } //    , ,     , //              If($middle_Pos) { if($arr_new[$middle_Pos] == $search) { return LibrarySort_PosNearby($middle_Pos, $newSize); } else { if($arr_new[$middle_Pos] > $search) { $finish = $middle_Pos; } else {//$arr_new[$middle_Pos] < $search $start = $middle_Pos; } return LibrarySort_BinarySearch($search, $start, $finish, $newSize); } } else {//$middle_Pos == 0 -   (   )     return $middle;//   - ,     } } else {//  ,       return floor(($start + $finish) / 2); } return false;//  ,       }

إذا كان العنصر أثناء البحث يساوي أحد نهايات المقطع

 //    ,        //$start - ,        //$newSize -     function LibrarySort_PosNearby($start, $newSize) { global $arr_new;//  //       for($left = $start - 1; $left >= 0; $left--) { if($arr_new[$left] === null) {//  return $left;//   } elseif($arr_new[$left] <> $arr_new[$start]) {//     break; //   ,      } } //     ,    for($right = $start + 1; $right <= $newSize - 1; $right++) { if($arr_new[$right] === null) {//  return $right; //   } elseif($arr_new[$right] <> $arr_new[$start]) {//     break; //   ,      } } return $start; //          .      ,     }

إعادة التوازن المحلي لمجموعة إضافية

 //    //$insert - ,    //$pos -            //$newSize -     function LibrarySort_Rebalance_Local($insert, $pos, $newSize) { global $arr_new;//  // $pos  $insert,       while($pos - 1 >= 0 && $arr_new[$pos - 1] !== null && $arr_new[$pos - 1] > $insert) {--$pos;} while($pos + 1 <= $newSize - 1 && $arr_new[$pos + 1] !== null && $arr_new[$pos + 1] < $insert) {++$pos;} $middle = (integer) $newSize / 2;//  if($pos <= $middle) {//      if($arr_new[$pos] !== null && $arr_new[$pos] < $insert) ++$pos; //  $right = $pos; while($arr_new[++$right] !== null) {} for($i = $right; $i > $pos; $i--) { $arr_new[$i] = $arr_new[$i - 1]; } } else {//      if($arr_new[$pos] !== null && $insert < $arr_new[$pos]) --$pos; //  $left = $pos; while($arr_new[--$left] !== null) {} for($i = $left; $i < $pos; $i++) { $arr_new[$i] = $arr_new[$i + 1]; } } $arr_new[$pos] = $insert; }

إعادة التوازن الكامل للصفيف الإضافي

 //    //$count -        //$newSize -     function LibrarySort_Rebalance_Total($count, $newSize) { global $arr_new;//  global $library_Number;//     global $library_LeftPos;//        $library_Number = $count; //        $library_LeftPos = $newSize - 1;// ,     //         $i = $newSize - 1; while($i >= 0) { if($arr_new[$i] !== null) {//   $pos = LibrarySort_Pos($library_Number, $count, $newSize);//   newSize=$newSize"); if($i == $pos) {//      --$i;//      } elseif($i < $pos) {//    $arr_new[$pos] = $arr_new[$i]; $arr_new[$i] = null; --$i;//      } else {//$i > $pos -     //      LibrarySort_RemoveLeft($i, $pos, $count, $newSize); $i = ($i > $library_LeftPos) ? $library_LeftPos - 1 : --$i; } --$library_Number;//      } else {// ,   --$i;//      } } }

تحريك العنصر إلى اليسار مع إعادة التوازن الكامل

 //     . //    ,   //$i -     ,    //$pos -       //$count -        //$newSize -     function LibrarySort_RemoveLeft($i, $pos, $count, $newSize) { global $arr_new;//  global $library_Number;//     global $library_LeftPos;//        $left = false; $left_Pos = false;//      $j = $i;//      //     while($j > 0 && $left === false) {//            --$j; //     if($arr_new[$j] !== null) $left = $j;//    } if($left === false || $left < $pos) {//   (  )    //     } else { //$left >= $pos,     --$library_Number;//,       $left_Pos = LibrarySort_Pos($library_Number, $count, $newSize);//     //        LibrarySort_RemoveLeft($left, $left_Pos, $count, $newSize); //  ,     } //    ,   $arr_new[$pos] = $arr_new[$i]; $arr_new[$i] = null; //,         if($pos < $library_LeftPos) $library_LeftPos = $pos; }

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

أود أن أرى نسخة من منشئي الخوارزمية. سأكتب اليوم للمؤلفين (وأرسل لهم رابطًا إلى هذا habrastatu) ، وسوف يجيبون فجأة. على الرغم من ... أتذكر ، حاولت الاتصال بـ Allen Beachich ( ABC- Sorting) و Jason Morrison ( J-sorting ) ، لكن النتيجة كانت كما لو أنني كتبت في Sportloto.

UPD أجابني مارتن فرح كولتون بأنهم لم يقوموا بالتنفيذ أبدًا:

أخشى أننا لم نقم بتطبيق هذه الخوارزميات.

الشيء الرئيسي هو الفكرة :)

خصائص الخوارزمية

العنوان	فرز المكتبة ، فرز المكتبة
اسم آخر	فرز إدراج بفواصل
المؤلفين	مايكل أ. بندر ، مارتن فاراش كولتون ، ميغيل موستيرو
عام	2004
فئة	أنواع الإدراج
مقارنات	يوجد
تعقيد الوقت	الأفضل	O ( ن )
	متوسط	O ( n log n )
	الأسوأ	O ( ن ² )
تعقيد الذاكرة الزائدة	O ( ن )

المراجع

فرز المكتبة

مكتبة تصور خوارزمية الفرز

ترتيب الإدراج هو O (n log n)

مؤلفو الخوارزمية:

مايكل أ. بندر
مارتن فرح كولتون
ميغيل موستيرو

مقالات سلسلة:

تطبيق Excel AlgoLab.xlsm
أنواع التبادل
أنواع الإدراج
- ترتيب أمين المكتبة
- فرز سوليتير
- فرز "برج هانوي"
- فرز طاولة الشباب
- عكس الفرز
- إدراج مقارنة الفرز
فرز حسب التحديد
دمج الأنواع
فرز حسب التوزيع
الفرز الهجين

تمت إضافة الفرز إلى AlgoLab. لذلك يمكنك تجربة مجموعات بيانات صغيرة.

في هذه الحالة ، يمكنك تحديد عدد المرات التي يكون فيها الصفيف الإضافي أكبر من الصفيف الرئيسي. لتحديد المعامل ε ، يمكنك النقر بزر الماوس الأيمن على الخلية باستخدام "تصنيف المكتبة" وتحديد "تغيير الملاحظة". وفي الملاحظة ، قم بتعيين قيمة العدد الصحيح لـ e من 2 إلى 5. إذا قمت بإدخال شيء آخر بدلاً من هذه الأرقام ، فسيتم استخدام القيمة الافتراضية = 2.

يمكنك أيضًا تحديد نوع إعادة التوازن. إذا قمت بتعيين local = 1 ، فسيتم استخدام إعادة التوازن المحلية. إذا كانت محلية = 0 - ممتلئة.

ولا تنس تعيين المقياس الأمثل لورقة المعالجة قبل بدء التصور ، وإلا فلن يتم احتواء الصفيف الإضافي على الشاشة.