فرز Bitonic

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 52 صور
الموسوعة الحرة

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

المتتالية المرتبة هي متتالية رتيبة ، أي متتالية إما غير متناقصة أو غير متزايدة. وتكون المتتالية ثنائية الرتابة عندما تتكون من متتالية غير متناقصة متبوعة بمتتالية غير متزايدة، أي عندما يوجد دليلم{\displaystyle m}والتيx0≤⋯≤xم≥⋯≥xن-1.{\displaystyle x_{0}\leq \cdots \leq x_{m}\geq \cdots \geq x_{n-1}.}[ 3 ]

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

تعرض الأقسام التالية الخوارزمية في صيغتها الأصلية، والتي تتطلب سلسلة إدخال طولهان{\displaystyle n}هو قوة مثالية للعدد اثنين. لذلك سنسمحك=سجل2⁡(ن){\displaystyle k=\log _{2}(n)}ليكن العدد الصحيح الذين=2ك{\displaystyle n=2^{k}}وهذا يعني أنه يمكن تعداد أجهزة الفرز ثنائية اللون بترتيب تصاعدي للحجم من خلال النظر في القيم المتتالية.ك=1،2،3،...{\displaystyle k=1,2,3,\ldots }.

فرز ثنائي الاتجاه

تُظهر هذه الصورة مُقارِنًا له مدخلان مُعَلَّمان بـ X و Y، ومخرجان بـ H و L.
مقارن عادي ذو مدخلين

جهاز فرز ثنائي الاتجاه لـك=1{\displaystyle k=1}(ن=2){\displaystyle (n=2)}هو ببساطة مُقارِن. [ 3 ] ويتضح ذلك من خلال تخطيط الصندوق المعطى، حيث يمثل X وY المدخلات، بينما يمثل H وL المخرجات العليا والدنيا، على التوالي.

مع جهاز الفرز لـك=1{\displaystyle k=1}يمكننا إنشاء مُصنِّف من رتبة أعلى بشكل متكرر. على سبيل المثال، انظر إلى ما يليك=2{\displaystyle k=2}(ن=4){\displaystyle (n=4)}[ 3 ]​

تُظهر هذه الصورة جهاز فرز دمج ثنائي الاتجاه بأربعة مداخل. على اليسار، توجد المداخل من x1 إلى x4. هذه المداخل متصلة بمقارنين، حيث يتصل x1 و x3 بأحدهما، بينما يتصل x2 و x4 بالآخر. جميع المخارج ذات القيم المنخفضة تدخل إلى أحد المقارنين، وجميع المخارج ذات القيم العالية تدخل إلى الآخر.
أن=4{\displaystyle n=4}(ك=2){\displaystyle (k=2)}فرز الدمج ثنائي الاتجاه

يتكون فارز البتون من طبقتين: طبقة إعادة التركيب، التي تعيد تركيب مدخلات البتون في سلسلتين جديدتين من البتون، كل منهما نصف طول السلسلة الأصلية، وطبقة فرز البتون التي تتكون من فارزين للبتون من الرتبةك-1{\displaystyle k-1}، حيث يقوم كل منها بفرز إحدى المتتاليتين الثنائيتين اللتين تنتجهما الطبقة السابقة. ويمكن توسيع هذا الهيكل بشكل متكرر لقيم أعلى منك{\displaystyle k}من خلال ضمان أن يقبل كل مُقارِن دائمًا مُدخلًا واحدًا من كل نصف من نصفي التسلسل الثنائي الذي يُفترض أن يُساعد في فرزه. يوضح الرسم التوضيحي التالي هذه الاتصالات بشكل تخطيطي. [ 3 ]

امتحان
امتحان

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

صحة جهاز الفرز ثنائي النواة

قدّم كين باتشر في بحثه [ 3 ] بعض الملخصات الرياضية للبرهان. وبدون فقدان للعمومية، يُفترض أن يكون تسلسل الإدخال الثنائي هوأ1≤أ2≤⋯≤أج-1≤أج≥أج+1≥⋯≥أ2ن{\displaystyle a_{1}\leq a_{2}\leq \dots \leq a_{j-1}\leq a_{j}\geq a_{j+1}\geq \dots \geq a_{2n}}مع1≤ج≤2ن{\displaystyle 1\leq j\leq 2n}وبدون فقدان للعمومية، يمكن عكس التسلسل، وبالتالي يمكننا أن نفترضن≤ج≤2ن{\displaystyle n\leq j\leq 2n}.

الحالة 1 : إذاأن≤أ2ن{\displaystyle a_{n}\leq a_{2n}}عندئذٍ يكون كل عنصر من عناصر المتتاليتين الجزئيتين أصغر. في هذه الحالةدأنا=أأنا{\displaystyle d_{i}=a_{i}}وهـأنا=أن+أنا{\displaystyle e_{i}=a_{n+i}}مع1≤أنا≤ن{\displaystyle 1\leq i\leq n}وبالتاليدأنا{\displaystyle d_{i}}وهـأنا{\displaystyle e_{i}}هي ثنائية التوتر بشكل بديهي.

الحالة الثانية : وإلا فإنه يوجدك{\displaystyle k}بحيث يكون العنصرأك{\displaystyle a_{k}}حجم التسلسل الفرعي الأول أكبر منأك{\displaystyle a_{k}}من التسلسل الفرعي الثاني، بينما يكون العكس صحيحًا بالنسبة لـأك+1{\displaystyle a_{k+1}}وهذا يعني أنأك≤أك+ن{\displaystyle a_{k}\leq a_{k+n}}وأك+1>أك+ن+1{\displaystyle a_{k+1}>a_{k+n+1}}صحيح بالنسبة لنوع محددك{\displaystyle k}لذلك، نعلم الآن أن:

1. لـ1≤أنا≤ك{\displaystyle 1\leq i\leq k}التسلسلات هيدأنا=أأنا{\displaystyle d_{i}=a_{i}}وهـأنا=أن+أنا{\displaystyle e_{i}=a_{n+i}}

2. لـك<أنا≤2ن{\displaystyle k<i\leq 2n}تُعرَّف المتتاليات بأنها عكس العدد 1، معدأنا=أن+أنا{\displaystyle d_{i}=a_{n+i}}وهـأنا=أأنا{\displaystyle e_{i}=a_{i}}

ثم يدعي في الورقة الأصلية أن المتباينات التالية تنتج عن تلك التعريفات: [ 3 ]

متابعةً للنقطة 1 :

  • ل1≤أنا≤ك{\displaystyle 1\leq i\leq k}الذي - التيدأنا≤دأنا+1{\displaystyle d_{i}\leq d_{i+1}}
  • لج-ن≤أنا≤ك{\displaystyle jn\leq i\leq k}الذي - التيهـأنا≥هـأنا+1{\displaystyle e_{i}\geq e_{i+1}}
  • ل1≤أنا≤ج-ن{\displaystyle 1\leq i\leq jn}الذي - التيهـأنا≤هـأنا+1{\displaystyle e_{i}\leq e_{i+1}}

متابعةً للنقطة 2 :

  • لك<أنا≤2ن{\displaystyle k<i\leq 2n}الذي - التيدأنا≥دأنا+1{\displaystyle d_{i}\geq d_{i+1}}
  • لك<أنا≤2ن{\displaystyle k<i\leq 2n}الذي - التيهـأنا≤هـأنا+1{\displaystyle e_{i}\leq e_{i+1}}

من كلا الطرفين:هـن≤هـ1{\displaystyle e_{n}\leq e_{1}}

يستنتج من الورقة البحثية أن التسلسلاتدأنا{\displaystyle d_{i}}وهـأنا{\displaystyle e_{i}}هي في الواقع ثنائية التوتر. [ 3 ]

شبكات الفرز ثنائية الاتجاه (فرز الدمج ثنائي الاتجاه)

تُنشأ شبكة فرز ثنائية باستخدام عدة خوارزميات فرز ثنائية. تُستخدم هذه الخوارزميات بشكل متكرر لإنشاء متتابعتين رتيبتين، إحداهما متناقصة والأخرى متزايدة، ثم تُوضعان في المرحلة التالية. ينتج عن ذلك سلسلة ثنائية للمرحلة التالية، والتي بدورها تستخدم هذه السلسلة الثنائية كسلسلة رتيبة للمرحلة التالية. لنأخذ المثال التالي كمثال.ن=4{\displaystyle n=4} شبكة فرز ثنائية النغمة. [ 3 ]

تيستا
امتحان

شبكة الفرز ثنائية الاتجاه لـك=2{\displaystyle k=2}يمكن إنشاؤها باستخدامك=2{\displaystyle k=2}جهاز فرز ثنائي القاعدة واثنينك=كصرهـv-1{\displaystyle k=k_{prev}-1}الفرزان. يُنشئ الفرزان تسلسلًا مُرتبًا تنازليًا أو تصاعديًا لإنشاء مُدخل ثنائي لفرز البيانات الثنائي. تُستخدم شبكات الفرز الثنائي ذات الرتبة المنخفضة في الغالب للفرزين الأوليين؛ لذلك، يُمكن وصف تعريف تكراري لشبكة الفرز الثنائي انطلاقًا من الفرزين الثنائيين. في المثال أعلاه، شبكتا الفرز الثنائي هما ك=1{\displaystyle k=1}الشبكات؛ لذا فهي مجرد أداة للمقارنة. [ 3 ] يوضح الشكل التالي المخطط العام.

تيستا
امتحان

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

الشفرة الزائفة

يصف الكود الزائف التالي عملية الفرز. في هذا الكود، aيُمثل المصفوفة المراد فرزها، lowو فهرس العنصر الأول في المصفوفة الفرعية المراد فرزها، kو countعدد العناصر في المصفوفة الفرعية التي يتم فرزها في هذه الدالة. directionقيمة منطقية تُحدد ما إذا كان يتم فرز المصفوفة الفرعية بترتيب تصاعدي أو تنازلي.

bitonicSort(a, 0, n, 1)يتم استخدام استدعاء الدالة للفرز a(تصاعديًا)، حيث nيمثل عدد العناصر في a.

الدالة bitonicMerge( a , low , count , direction ) هي: إذا كان count > 1 ، فإن k ← count / 2 // قارن العناصر وبدّلها بين النصفين for i ← low to low + k do // تحديد ما إذا كان عنصران من a غير مرتبين بالنسبة لاتجاه الفرز. if ( direction == 1 AND a [i] > a [i + k]) OR ( direction == 0 AND a [i] < a [i + k]) THEN swap a [i] with a [i + k] // دمج النصفين بشكل متكرر bitonicMerge ( أ , منخفض , ك , اتجاه ) bitonicMerge ( أ , منخفض + ك , ك , اتجاه ) // هذا يعمل فقط عندما يكون حجم الإدخال قوة للعدد 2. الدالة bitonicSort( a , low , count , direction ) هي: إذا كان count > 1 ، فإن k ← count / 2 // فرز النصف الأول/الثاني بترتيب تصاعدي/تنازلي bitonicSort ( a , low , k, 1) bitonicSort ( a , low + k, k, 0) // دمج التسلسل بأكمله بالترتيب المطلوب bitonicMerge ( a , low , count , direction )

تعقيد

في هذا القسم، نفترض أن جهاز الفرز الخاص بنا لديهن=2ك{\displaystyle n=2^{k}}عناصر الإدخال كما كانت سابقاً.

تضيف كل عملية تكرار في شبكة فرز ثنائية النغمة فرزًا من رتبةكنهـxت=كصرهـv-1{\displaystyle k_{next}=k_{prev}-1}، والتي تتكون من ثنائي القاعدةكنهـxت{\displaystyle k_{next}}الفرز والتكرار التالي. بما أن كلا الفرزين الفرعيين يمكن تنفيذهما بالتوازي، تتم إضافة مستوى واحد فقط لكل مستوى في كلا الفرزين الفرعيين. لذلك، يحتوي كل فرز ثنائي على طبقة إعادة تركيب واحدة وفرز ثنائي منخفض الرتبة لتكراره. ينتج عن ذلكك{\displaystyle k}عدد المستويات لكل فارز ثنائي. لذلك، يمكننا وصف مستويات هذا البناء على النحو التالي:∑أنا=1كأنا{\displaystyle \sum _{i=1}^{k}i}.

يمكن اختزال هذا المجموع باستخدام صيغة مجموع جاوس.∑أنا=1كأنا=12ك(ك+1){\displaystyle \sum _{i=1}^{k}i={\dfrac {1}{2}}k(k+1)}

وبالتالي، فإن عدد المستويات التي يمكن فيها إجراء كل مقارنة بالتوازي يُعطى بواسطة12ك(ك+1){\displaystyle {\dfrac {1}{2}}k(k+1)}[ 3 ] مما يعطينايا(ك2+ك)=يا(ك2)=يا((سجل2⁡ن)2){\displaystyle {\mathcal {O}}(k^{2}+k)={\mathcal {O}}(k^{2})={\mathcal {O}}((\log _{2}n)^{2})}بافتراضن{\displaystyle n}يمكن إجراء المقارنات بالتوازي.

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

انظر أيضاً

مراجع

  1. ميغا ، جاين؛ سانجاي، كومار؛ في كي، باتل (مارس 2015). " خوارزمية الفرز الثنائي: مراجعة" . المجلة الدولية لتطبيقات الحاسوب . 113 ( 13): 40-43 . Bibcode : 2015IJCA..113m..40J . doi : 10.5120/19890-1930 . تاريخ الاسترجاع: 14 مايو 2025 .
  2. 1 2 3 4 5 رانكوفيتش، فوكاسين؛ كوس، انطون؛ ميلوتينوفيتش ، فيليكو (يوليو 2013). “تنفيذ فرز دمج Bitonic على نظام الحوسبة الفائقة Maxeler Dataflow” (PDF) . معاملات IPSI BGD على أبحاث الإنترنت . 9 (2): 5- 10 . تم الاسترجاع في 14 مايو 2025 .
  3. 1 2 3 4 5 6 7 8 9 10 11 12 13 باتشر، ك. إي. (30 أبريل 1968). "شبكات الفرز وتطبيقاتها". وقائع المؤتمر المشترك للحاسوب الربيعي المنعقد في الفترة من 30 أبريل إلى 2 مايو 1968 - AFIPS '68 (ربيع) . الصفحات 307-314 . doi : 10.1145/1468075.1468121 .