فرز الصبر

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

اسم الخوارزمية مشتق من نسخة مبسطة من لعبة الصبر الورقية. تبدأ اللعبة بمجموعة أوراق لعب مختلطة. تُوزع الأوراق واحدة تلو الأخرى في سلسلة من الأكوام على الطاولة، وفقًا للقواعد التالية. ^{[ 2 ]}

1. في البداية، لا توجد أكوام. البطاقة الأولى التي يتم توزيعها تشكل كومة جديدة تتكون من البطاقة الوحيدة.
2. يتم وضع كل بطاقة لاحقة على الكومة الموجودة الموجودة في أقصى اليسار والتي تكون قيمة البطاقة العلوية فيها أكبر من أو تساوي قيمة البطاقة الجديدة، أو على يمين جميع الكومات الموجودة، وبالتالي تشكيل كومة جديدة.
3. عندما لا يتبقى أي أوراق للتوزيع، تنتهي اللعبة.

تُحوّل لعبة الورق هذه إلى خوارزمية فرز ثنائية المراحل، كما يلي: بفرض وجود مصفوفة من n عنصرًا من مجال مُرتب ترتيبًا كليًا ، تُعتبر هذه المصفوفة مجموعة من البطاقات، ويتم محاكاة لعبة فرز الصبر. عند انتهاء اللعبة، يُستعاد التسلسل المُرتب عن طريق سحب أصغر بطاقة مرئية بشكل متكرر؛ أي يُجرى دمج k -way للمجموعات p ، حيث تكون كل مجموعة مُرتبة داخليًا.

فيما يلي تطبيق تكراري لخوارزمية فرز الصبر، ويتم تشغيل هذا التطبيق في${\displaystyle O(n^{2})}$.

دالة PatienceSorting( array arr) هي n ← طول (arr) أكوام ← قائمة فارغة من القوائملـ i = 0 إلى n - 1 ، إذا كان طول (الأكوام) يساوي 0، فقم بإنشاء قائمة جديدة مؤقتة. tmp.append(arr[i]) piles.append(tmp) آخر تم وضعه ← خطأ لكل j ← 0 إلى طول(الأكوام) - 1 ، إذا كان arr[i] < العنصر الأخير من piles[j] ، piles[j].append(arr[i]) تم وضعه ← صحيح استراحة إذا كانت قيمة `placed` تساوي `false` ، مؤقت ← قائمة جديدة tmp.append(arr[i]) piles.append(tmp) أعد دمج الأكوام (الأكوام) دالة MergePiles(قائمة من القوائم piles) هي النتيجة ← قائمة فارغةصحيح ، لكن minValue ← ∞ minIndex ← -1 لـ i ← 0 إلى طول(الأكوام) - 1 ، إذا كان طول(الأكوام[i]) > 0 و]الأكوام[i][طول(الأكوام[i]) - 1] < القيمة الدنيا ، minValue ← piles[i][length(piles[i]) - 1] minIndex ← i إذا كان الحد الأدنى للمؤشر يساوي -1، استراحة result.append(minValue) piles[minIndex].remove(piles[minIndex][length(piles[minIndex]) - 1] إذا كان طول (piles[minIndex]) يساوي صفرًا ، piles.remove(piles[minIndex]) إرجاع النتيجة

يمكن تنفيذ المرحلة الأولى من فرز الصبر، وهي محاكاة لعبة الورق، بحيث تستغرق O ( n log n ) مقارنة في أسوأ الحالات لمصفوفة إدخال مكونة من n عنصرًا: سيكون هناك على الأكثر n كومة، وبحسب التصميم، تشكل البطاقات العلوية للكومات تسلسلًا متزايدًا من اليسار إلى اليمين، لذا يمكن العثور على الكومة المطلوبة عن طريق البحث الثنائي . ^{[ 1 ]} يمكن تنفيذ المرحلة الثانية، وهي دمج الكومات، في${\displaystyle O(n\log n)}$الوقت وكذلك باستخدام قائمة انتظار ذات أولوية . ^{[ 1 ]}

عندما تحتوي بيانات الإدخال على "سلاسل" طبيعية، أي مصفوفات فرعية غير متناقصة، يمكن أن يكون الأداء أفضل بكثير. في الواقع، عندما تكون مصفوفة الإدخال مرتبة بالفعل، تشكل جميع القيم كومة واحدة، وتستغرق كلتا المرحلتين وقتًا قدره O ( n ) . يظل تعقيد الحالة المتوسطة O ( n log n ) : أي تسلسل عشوائي منتظم من القيم سينتج عددًا متوقعًا من${\displaystyle O({\sqrt {n}})}$الأكوام، ^{[ 3 ]} التي تأخذ${\displaystyle O(n\log {\sqrt {n}})=O(n\log n)}$الوقت اللازم للإنتاج والدمج. ^{[ 1 ]}

قدّم تشاندرا مولي وغولدشتاين تقييمًا للأداء العملي لخوارزمية فرز الصبر، حيث أظهرا أن النسخة البسيطة منها أبطأ بنحو عشرة إلى عشرين مرة من خوارزمية الفرز السريع المتطورة في مسألة معيارية. ويعزو الباحثان ذلك إلى قلة الأبحاث التي أُجريت على خوارزمية فرز الصبر، وقاما بتطوير العديد من التحسينات التي جعلت أداءها أقرب إلى ضعف أداء خوارزمية الفرز السريع. ^{[ 1 ]}

إذا كانت قيم البطاقات في النطاق 1، ...، n ، فهناك تطبيق فعال مع${\displaystyle O(n\log n)}$أسوأ وقت تشغيل لوضع البطاقات في أكوام، بالاعتماد على شجرة فان إمدي بواس . ^{[ 3 ]}

تُشبه لعبة فرز الصبر إلى حد كبير لعبة ورق تُسمى لعبة فلويد. هذه اللعبة تُشبه إلى حد كبير اللعبة التي تم شرحها سابقًا: ^{[ 2 ]}

1. تشكل البطاقة الأولى التي يتم توزيعها كومة جديدة تتكون من البطاقة الوحيدة.
2. يتم وضع كل بطاقة لاحقة على كومة موجودة تكون قيمة البطاقة العلوية فيها لا تقل عن قيمة البطاقة الجديدة، أو على يمين جميع الأكوام الموجودة، مما يشكل كومة جديدة.
3. عندما لا يتبقى أي أوراق للتوزيع، تنتهي اللعبة.

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

يقترح ألدوس ودياكونيس تعريف 9 أكوام أو أقل على أنها نتيجة رابحة لـ n = 52 ، وهو ما يحدث باحتمالية 5٪ تقريبًا. ^{[ 4 ]}

أطلق كولين لينغوود مالوز اسم "فرز الصبر "، ونسب اختراعه إلى إيه إس سي روس في أوائل الستينيات. ^{[ 1 ]} ووفقًا لألدوس ودياكونيس، ^{[ 4 ]} فقد تم التعرف على فرز الصبر لأول مرة كخوارزمية لحساب أطول سلسلة فرعية متزايدة الطول بواسطة هامرسلي. ^{[ 5 ]} وقد تعرف كل من إيه إس سي روس وروبرت دبليو فلويد بشكل مستقل على فرز الصبر كخوارزمية فرز. وأجرى مالوز التحليل الأولي. ^{[ 6 ]} وقد طور فلويد لعبته بالتواصل مع دونالد كنوث . ^{[ 2 ]}

يمكن تطبيق خوارزمية فرز الصبر على التحكم في العمليات . ضمن سلسلة من القياسات، يمكن استخدام وجود سلسلة فرعية متزايدة طويلة كمؤشر للاتجاه. تتضمن مقالة نُشرت عام 2002 في مجلة SQL Server تطبيقًا بلغة SQL، في هذا السياق، لخوارزمية فرز الصبر لحساب طول أطول سلسلة فرعية متزايدة. ^{[ 7 ]}