فرز سريع

خوارزمية Flashsort هي خوارزمية فرز توزيعي تتميز بتعقيد حسابي خطي O ( n ) لمجموعات البيانات الموزعة بشكل منتظم، ومتطلبات ذاكرة إضافية قليلة نسبيًا. نُشر العمل الأصلي عام 1998 بواسطة كارل-ديتريش نيوبيرت. ^{[ 1 ]}

خوارزمية Flashsort هي تطبيق فعال لخوارزمية فرز المدرج التكراري ، وهي نوع من أنواع فرز الدلو . تقوم هذه الخوارزمية بتخصيص كل عنصر من عناصر الإدخال البالغ عددها n إلى أحد الدلو البالغ عددها m ، ثم تعيد ترتيب الإدخال بكفاءة لوضع الدلو بالترتيب الصحيح، ثم تقوم بفرز كل دلو. تقوم الخوارزمية الأصلية بفرز مصفوفة الإدخال A على النحو التالي:

1. باستخدام عملية أولية على المدخلات أو المعرفة المسبقة ، ابحث عن مفاتيح الفرز الدنيا والقصوى.
2. قسّم النطاق [ A _min , A _max ] خطيًا إلى m خانات.
3. قم بمسح المدخلات مرة واحدة، واحسب عدد العناصر A _i التي تقع في كل خانة. (يُطلق نيوبيرت على الخانات اسم "الفئات" وعلى تعيين العناصر لخاناتها اسم "التصنيف").)
4. حوّل عدد العناصر في كل مجموعة إلى مجموع بادئ ، حيث يمثل L _{_b} عدد العناصر A_{_i} في المجموعة b أو أقل. ( L _₀ = 0 و L _{_m} = n ).
5. أعد ترتيب المدخلات بحيث يتم تخزين جميع عناصر كل دلو b في المواضع A _i حيث L _{b − 1} < i ≤ L _b .
6. قم بفرز كل مجموعة باستخدام خوارزمية فرز الإدراج .

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

ما يميز فرز الفلاش هو الخطوة 5: خوارزمية فعالة من نوع O ( n ) في مكانها لجمع عناصر كل دلو معًا بالترتيب النسبي الصحيح باستخدام m كلمة فقط من الذاكرة الإضافية.

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

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

لفهم ذلك باستخدام متغيرين لكل دلو، افترض وجود مصفوفتين من m كلمة إضافية: K _b هو الحد الأعلى (الثابت) للدلو b (و K ₀ = 0 )، بينما L _b هو مؤشر (قابل للتحريك) في الدلو b ، لذا K _{b − 1} ≤ L _b ≤ K _b .

نحافظ على شرط الحلقة الثابت بأن كل خانة تُقسّم بواسطة L_{_b} إلى بادئة غير مصنفة (العناصر A _i، حيث K_{_b − 1} < i ≤ L _{_b،} لم تُنقل بعد إلى خاناتها المستهدفة) ولاحقة مصنفة (العناصر A _{_i} ، حيث L_{_b} < i ≤ K_{_b}، جميعها في الخانة الصحيحة ولن تُنقل مرة أخرى). في البداية، L _{_b} = K_{_b} وجميع العناصر غير مصنفة. مع استمرار عملية الفرز، تُنقص قيمة L_{_b حتى تصبح} L _{_b} = K_{_b − 1} لجميع قيم b ، وتُصنّف جميع العناصر في الخانة الصحيحة.

تبدأ كل جولة بإيجاد أول مجموعة غير مصنفة بالكامل c (والتي يكون فيها K _{c − 1} < L _c ) وأخذ أول عنصر غير مصنف في تلك المجموعة A _i حيث i = K _{c − 1} + 1. (يُطلق نيوبيرت على هذا اسم "قائد الدورة"). انسخ A _i إلى متغير مؤقت t وكرر العملية.

• احسب المجموعة b التي ينتمي إليها t .
• ليكن j = L _b هو الموقع الذي سيتم فيه تخزين t .
• قم بتبديل t مع A _j ، أي قم بتخزين t في A _j أثناء جلب القيمة السابقة A _j التي تم إزاحتها.
• قم بإنقاص قيمة L _b لتعكس حقيقة أن A _j مصنفة الآن بشكل صحيح.
• إذا كان j ≠ i ، فأعد تشغيل هذه الحلقة باستخدام t الجديد .
• إذا كان j = i ، فقد انتهت هذه الجولة، وابحث عن أول عنصر غير مصنف جديد A _i .
• عندما لا يتبقى أي عناصر غير مصنفة، يكتمل التوزيع في مجموعات.

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

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

لنفترض أننا صنفنا جميع العناصر حتى i − 1 ، ونعتبر A _i قائدًا محتملاً لدورة جديدة. من السهل حساب مجموعته المستهدفة b . وفقًا لثابت الحلقة، يُصنف العنصر إذا كان L _b < i ≤ K _b ، ولا يُصنف إذا كان i خارج هذا النطاق. يسهل اختبار المتباينة الأولى ، لكن يبدو أن الثانية تتطلب القيمة K _b .

اتضح أن فرضية الاستقراء التي تنص على أن جميع العناصر حتى i − 1 مصنفة تعني أن i ≤ K _b ، لذلك ليس من الضروري اختبار المتباينة الثانية.

لنفترض المجموعة c التي يقع فيها العنصر i . أي أن K _{_{c - 1}} < i ≤ K _{_c} . وفقًا لفرضية الاستقراء، فإن جميع العناصر التي تقع أسفل i ، والتي تشمل جميع المجموعات حتى K _{_{c - 1}} < i ، مصنفة تصنيفًا كاملًا. أي أنه لا توجد عناصر تنتمي إلى تلك المجموعات في بقية المصفوفة. لذلك، من غير الممكن أن يكون b < c .

الحالة المتبقية الوحيدة هي b ≥ c ، مما يعني أن K _b ≥ K _c ≥ i ، وهو المطلوب إثباته.

وبناءً على ذلك، تبدأ خوارزمية توزيع الفرز السريع بـ L كما هو موضح أعلاه و i = 1. ثم تابع: ^{[ 1 ] [ 2 ]}

• إذا كان i > n ، فإن التوزيع يكون كاملاً.
• بفرض A _i ، احسب المجموعة b التي ينتمي إليها.
• إذا كان i ≤ L _b ، فإن A _i غير مصنف. انسخه إلى متغير مؤقت t و:
  • ليكن j = L _b هو الموقع الذي سيتم فيه تخزين t .
  • قم بتبديل t مع A _j ، أي قم بتخزين t في A _j أثناء جلب القيمة السابقة A _j التي تم إزاحتها.
  • قم بإنقاص قيمة L _b لتعكس حقيقة أن A _j مصنفة الآن بشكل صحيح.
  • إذا كان j ≠ i ، فقم بحساب الحاوية b التي ينتمي إليها t وأعد تشغيل هذه الحلقة (الداخلية) مع t الجديد .
• تم تصنيف العنصر _i بشكل صحيح الآن. قم بزيادة قيمة i وأعد تشغيل الحلقة (الخارجية).

على الرغم من توفيرها للذاكرة، إلا أن خوارزمية Flashsort تعاني من عيب يتمثل في إعادة حساب خانة التخزين للعديد من العناصر المصنفة مسبقًا. يتم ذلك بالفعل مرتين لكل عنصر (مرة أثناء مرحلة عدّ خانات التخزين، ومرة ​​ثانية عند نقل كل عنصر)، ولكن البحث عن أول عنصر غير مصنف يتطلب عملية حسابية ثالثة لمعظم العناصر. قد يكون هذا مكلفًا إذا تم تعيين خانات التخزين باستخدام صيغة أكثر تعقيدًا من الاستيفاء الخطي البسيط. يقلل أحد المتغيرات عدد العمليات الحسابية من حوالي 3n إلى 2n + m − 1 كحد     أقصى ، وذلك بأخذ آخر عنصر غير مصنف في خانة تخزين غير مكتملة كقائد للدورة.

• احتفظ بمتغير c لتحديد أول مجموعة غير مصنفة بشكل كامل. لنفترض أن c = 1 في البداية، وعندما c > m ، يكون التوزيع كاملاً.
• لنفترض أن i = L _c . إذا كان i = L _{c − 1} ، فقم بزيادة قيمة c وأعد تشغيل هذه الحلقة. ( L ₀ = 0 ).
• احسب المجموعة b التي ينتمي إليها A _i .
• إذا كان b < c ، فإن L _c = K _{c − 1} ، وبذلك نكون قد انتهينا من التعامل مع المجموعة c . قم بزيادة قيمة c وأعد تشغيل هذه الحلقة.
• إذا كانت b = c ، فإن التصنيف بسيط. قلل قيمة L _c وأعد تشغيل هذه الحلقة.
• إذا كانت قيمة b أكبر من قيمة c ، فإن A _i غير مصنفة. قم بتنفيذ حلقة التصنيف نفسها كما في الحالة السابقة، ثم أعد تشغيل هذه الحلقة.

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

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

كما هو الحال مع جميع خوارزميات فرز الحاويات، يعتمد الأداء بشكل حاسم على توازن الحاويات. في الحالة المثالية لمجموعة بيانات متوازنة، يكون حجم كل حاوية متقاربًا. إذا كان عدد الحاويات (m) يتناسب طرديًا مع حجم المدخلات (n) ، فإن حجم كل حاوية يكون ثابتًا، وبالتالي فإن فرز حاوية واحدة باستخدام خوارزمية ذات تعقيد زمني O ( n² ⁾ مثل فرز الإدراج يكون تعقيدها الزمني O ( ^1² ) = O (1) . وعليه، فإن زمن تشغيل عمليات فرز الإدراج النهائية هو m ⋅ O(1) = O ( m ) = O ( n ) .

يُوازن اختيار قيمة m ، أي عدد المجموعات، بين الوقت المُستغرق في تصنيف العناصر (قيمة m عالية ) والوقت المُستغرق في خطوة فرز الإدراج النهائية (قيمة m منخفضة ⁾ . على سبيل المثال، إذا تم اختيار m بما يتناسب مع √n ، فإن زمن تشغيل فرز الإدراج النهائي يكون m ⋅ O( √n² ) = O ( n³ / ^² ) .

^{في أسوأ الحالات ،} حيث تتركز معظم العناصر في عدد قليل من المجموعات، يصبح تعقيد الخوارزمية محدودًا بأداء طريقة فرز المجموعات النهائية، وبالتالي ينخفض ​​إلى O ( n² ) . تعمل بعض تعديلات الخوارزمية على تحسين الأداء في أسوأ الحالات باستخدام طرق فرز أكثر كفاءة، مثل الفرز السريع أو الفرز الوميضي المتكرر، على المجموعات التي تتجاوز حدًا معينًا في الحجم. ^{[ 2 ] [ 3 ]}

بالنسبة لـ m = 0.1 n مع بيانات عشوائية موزعة بانتظام، يكون فرز الفلاش أسرع من فرز الكومة لجميع قيم n، وأسرع من فرز السرعة السريعة لـ n > 80. ويصبح أسرع بمرتين تقريبًا من فرز السرعة السريعة عند n = 10000. [ ^{1 ] تجدر} الإشارة إلى أن هذه القياسات أُجريت في أواخر التسعينيات، عندما كانت هياكل الذاكرة أقل اعتمادًا على التخزين المؤقت.

نظراً لعملية التبديل الموضعي التي تُجريها خوارزمية الفرز السريع (Flashsort) في عملية التصنيف، فإنها غير مستقرة . إذا كان الاستقرار مطلوباً، فمن الممكن استخدام مصفوفة ثانية لتصنيف العناصر بالتسلسل. مع ذلك، في هذه الحالة، ستحتاج الخوارزمية إلى ذاكرة إضافية مقدارها O ( n ) .

• البحث بالاستكمال ، باستخدام توزيع العناصر للبحث بدلاً من الفرز.

• تطبيقات الفرز العشوائي على الآلات المتوازية الكبيرة (1992)
• تنفيذ الخوارزميات المتوازية (1992)
• عرض مرئي لخوارزمية فرز الفلاش، مؤرشف بتاريخ 5 يوليو 2011 على موقع Wayback Machine