الفرز الجزئي

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

من حيث المؤشرات، في قائمة مرتبة جزئيًا، لكل مؤشر i من 1 إلى k، يكون العنصر i في نفس المكان الذي سيكون فيه في القائمة المرتبة بالكامل: العنصر i من القائمة المرتبة جزئيًا يحتوي على إحصائية الترتيب i من قائمة الإدخال.

مشاكل في وضع عدم الاتصال

حل قائم على الكومة

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

الحل عن طريق تحديد التقسيم

يُتيح تبسيطٌ إضافي، يقتصر على قائمةٍ بأصغر $k$ عنصر دون اشتراط ترتيبها، إمكانيةَ مُكافئةٍ للاختيار القائم على التقسيم ؛ إذ يُمكن حلّ مُشكلة الفرز الجزئي الأصلية باستخدام خوارزمية اختيارٍ كهذه للحصول على مصفوفةٍ تكون فيها العناصر $k$ الأولى هي أصغر $k$ عنصر ، ثم فرزها، بتكلفةٍ إجماليةٍ قدرها $O (n + k log k)$ عملية. ومن الخيارات الشائعة لتنفيذ مخطط الخوارزمية هذا دمجُ خوارزميتيّ الاختيار السريع والفرز السريع ؛ ويُطلق على النتيجة أحيانًا اسم "الفرز السريع المُدمج". ^{[ 1 ]}

من الشائع في تطبيقات C++ STL الحالية (حتى عام 2022) تمرير عملية اختيار الكومة لقائمة من k عنصر، متبوعة بعملية فرز الكومة للنتيجة النهائية. ^{[ 2 ]}

خوارزميات فرز متخصصة

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

دالة الفرز الجزئي السريع (A، i، j، k) هي إذا كان i < j ثم p ← pivot(A, i, j) p ← partition(A, i, j, p) partial_quicksort(A, i, p-1, k) إذا كان p < k-1، فقم بتنفيذ partial_quicksort(A, p+1, j, k)

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

الفرز التدريجي

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

تؤدي الأكوام إلى حل "اختيار الكومة عبر الإنترنت" من رتبة $O (n + k log n)$ لفرز جزئي متزايد: أولاً، يتم "تكوين الكومة"، في وقت خطي، لمصفوفة الإدخال الكاملة لإنتاج كومة دنيا. ثم يتم استخراج الحد الأدنى من الكومة $k$ مرة. ^{[ 1 ]}

يمكن الحصول على فرز تزايدي مختلف عن طريق تعديل دالة quickselect. تحتفظ النسخة التي طورها باريديس ونافارو بمجموعة من العناصر المحورية عبر الاستدعاءات، بحيث يمكن إنجاز الفرز التزايدي عن طريق طلب أصغر عنصر في المصفوفة $A$ بشكل متكرر من الخوارزمية التالية: ^{[ 4 ]}

تُعيد الخوارزمية $IQS(A : مصفوفة، i : عدد صحيح، S : مكدس) أصغر عنصر رقم$ $i$ في $المصفوفة A.$

إذا كان i = أعلى( S ) :
- بوب $إس$
- أعد $A [i]$
ليكن $pivot \leftarrow random[i, top(S))$
تحديث $المحور \leftarrow تقسيم(A [i : أعلى(S)), A [المحور])$
ادفع $المحور$ إلى $S$
أرجع $IQS(A, i, S)$

يتم تهيئة المكدس $S$ ليحتوي فقط على المصفوفة $A$ بطول $n$ . يتم فرز المصفوفة $k -sorting باستدعاء الدالة$ $IQS($ $A$ $,$ $i$ $,$ $S$ $)$ حيث $i$ $= 0, 1, 2, ...$ ؛ يبلغ متوسط تعقيد هذه العملية $O$ $($ $n$ $+$ $k$ $log$ $k$ $)$ ، وهو ما يعادل تقريبًا $O$ $($ $n$ $+$ $k$ $log$ $n$ $)$ . يكون زمن أسوأ حالة تربيعيًا، ولكن يمكن تحسين ذلك باستبدال اختيار المحور العشوائي بخوارزمية وسيط الوسائط . ^[⁴^]

دعم اللغة/المكتبة

يحدد معيار C ++ دالة مكتبة تسمى std::partial_sort.
تتضمن مكتبة بايثون القياسية وظائف nlargestفي nsmallestوحدتها heapq.
تتضمن مكتبة جوليا القياسية خوارزمية مستخدمةPartialQuickSort في partialsort!ومتغيرات.

انظر أيضاً

خوارزمية الاختيار

مراجع

1 2 3 4 5 كونرادو مارتينيز (2004). حول الفرز الجزئي (ملف PDF) . الندوة العاشرة حول تحليل الخوارزميات.
↑ "std::partial_sort" . en.cppreference.com .
↑ مارتينيز، كونرادو (2004). فرز سريع جزئي (PDF) . وقائع ورشة عمل ACM-SIAM السادسة حول هندسة الخوارزميات والتجارب وورشة عمل ACM-SIAM الأولى حول الخوارزميات التحليلية والتوافقية.
1 2 3 باريديس، رودريغو؛ نافارو، غونزالو (2006). "الفرز التزايدي الأمثل". وقائع ورشة العمل الثامنة حول هندسة الخوارزميات والتجارب (ALENEX) . الصفحات 171-182 . CiteSeerX 10.1.1.218.4119 . doi : 10.1137/1.9781611972863.16 . ISBN 978-1-61197-286-3.

روابط خارجية

جيه إم تشامبرز (1971). الفرز الجزئي . CACM 14 (5):357–358.

[aofa04slides-1] 1 2 3 4 5 كونرادو مارتينيز (2004). حول الفرز الجزئي (ملف PDF) . الندوة العاشرة حول تحليل الخوارزميات.

[2] "std::partial_sort" . en.cppreference.com .

[3] مارتينيز، كونرادو (2004). فرز سريع جزئي (PDF) . وقائع ورشة عمل ACM-SIAM السادسة حول هندسة الخوارزميات والتجارب وورشة عمل ACM-SIAM الأولى حول الخوارزميات التحليلية والتوافقية.

[paredes-4] 1 2 3 باريديس، رودريغو؛ نافارو، غونزالو (2006). "الفرز التزايدي الأمثل". وقائع ورشة العمل الثامنة حول هندسة الخوارزميات والتجارب (ALENEX) . الصفحات 171-182 . CiteSeerX 10.1.1.218.4119 . doi : 10.1137/1.9781611972863.16 . ISBN 978-1-61197-286-3.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]