فرز الكتل

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

فرز الكتل (المصفوفة) قوة_العدد_اثنان = FloorPowerOfTwo (حجم_المصفوفة) المقياس = حجم المصفوفة / قوة العدد اثنين // 1.0 ≤ المقياس < 2.0// فرز الإدراج 16-31 عنصرًا في كل مرة for (merge = 0; merge < power_of_two; merge += 16) البداية = الدمج * المقياس النهاية = البداية + 16 * المقياس فرز الإدراج (المصفوفة، [البداية، النهاية)) for (length = 16; length < power_of_two; length += length) for (merge = 0; merge < power_of_two; merge += length * 2) البداية = الدمج * المقياس المنتصف = (الدمج + الطول) * المقياس النهاية = (الدمج + الطول * 2) * المقياس إذا كان (array[end − 1] < array[start]) // النطاقان بترتيب عكسي، لذا يكفي تدويرهما لدمجهما. Rotate (array, mid − start, [start, end)) وإلا إذا كان (array[mid − 1] > array[mid]) Merge (array, A = [start, mid), B = [mid, end)) // وإلا فإن النطاقين مرتبان بشكل صحيح بالفعل

يمكن أيضًا استخدام العمليات الحسابية ذات النقطة الثابتة ، وذلك بتمثيل عامل المقياس ككسر integer_part + numerator/denominator:

فرز الكتل (المصفوفة) قوة_العدد_اثنان = FloorPowerOfTwo (حجم_المصفوفة) المقام = قوة العدد اثنين / 16 numerator_step = array.size % denominator integer_step = floor (array.size/denominator) // فرز الإدراج 16 – 31 عنصرًا في المرة الواحدةبينما (الخطوة_الصحيحة < حجم_المصفوفة) الجزء الصحيح = البسط = 0 بينما (الجزء_الصحيح < حجم_المصفوفة) // الحصول على نطاقات A و B البداية = الجزء_الصحيح integer_part += integer_step البسط += خطوة_البسط إذا كان (البسط ≥ المقام) البسط - = المقام integer_part++ mid = الجزء_الصحيح integer_part += integer_step البسط += خطوة_البسط إذا كان (البسط ≥ المقام) البسط −= المقام integer_part++ النهاية = الجزء_الصحيح إذا كان (array[end − 1] < array[start]) قم بتدوير (array, mid − start, [start, end)) وإلا إذا كان (array[mid − 1] > array[mid]) قم بدمج (array, A = [start, mid), B = [mid, end)) integer_step += integer_step numerator_step += numerator_step إذا كان (البسط_الخطوة ≥ المقام) خطوة_البسط −= المقام integer_step++

يتم إنشاء المخزنين الداخليين اللازمين لكل مستوى من مستويات خطوة الدمج عن طريق نقل أول 2√A من قيمها داخل مصفوفة فرعية A إلى بداية A. في البداية ، يتم المرور على عناصر A وحساب القيم الفريدة المطلوبة، ثم يتم تطبيق تدوير المصفوفة لنقل هذه القيم الفريدة إلى البداية. ^{[ 6 ]} إذا لم تحتوي A على عدد كافٍ من القيم الفريدة لملء المخزنين (بحجم √A لكل منهما)، فيمكن استخدام B بنفس الكفاءة. في هذه الحالة، يتم نقل آخر نسخة من كل قيمة إلى نهاية B ، مع استبعاد هذا الجزء من B أثناء عمليات الدمج.

بينما (الخطوة_الصحيحة < حجم_المصفوفة) حجم الكتلة = √ الخطوة الصحيحة حجم المخزن المؤقت = عدد صحيح_الخطوة/حجم_الكتلة + 1 [استخراج مخزنين مؤقتين بحجم 'buffer_size' لكل منهما]

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

حجم المخزن المؤقت = [عدد القيم الفريدة التي تم العثور عليها] حجم الكتلة = الخطوة الصحيحة / حجم المخزن المؤقت + 1 الجزء الصحيح = البسط = 0 بينما (الجزء_الصحيح < حجم_المصفوفة) [احصل على نطاقات A و B] [اضبط A و B بحيث لا تشمل النطاقات المستخدمة بواسطة المخازن المؤقتة]

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

// blockA هو نطاق كتل A المتبقية، // و firstA هي كتلة A الأولى ذات الحجم غير المتساوي blockA = [A.start, A.end) firstA = [A.start, A.start + |blockA| % block_size) // تبديل القيمة الثانية لكل كتلة A مع القيمة الموجودة في المخزن المؤقت buffer1 for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) Swap (array[buffer1.start + index], array[indexA]) فهرس++ lastA = firstA blockB = [B.start, B.start + minimum (block_size, |B|)) blockA.start += |firstA|

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

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

 minA = blockA.start indexA = 0 بينما (صحيح) // إذا كان هناك كتلة B سابقة وكانت القيمة الأولى للكتلة A الدنيا ≤ // القيمة الأخيرة للكتلة B السابقة، فقم بإسقاط تلك الكتلة A الدنيا خلفها. // أو إذا لم تكن هناك كتل B متبقية، فاستمر في إسقاط كتل A المتبقية. إذا ((|lastB| > 0 و array[lastB.end - 1] ≥ array[minA]) أو |blockB| = 0) // حدد مكان تقسيم كتلة B السابقة، وقم بتدويرها عند نقطة التقسيم B_split = BinaryFirst (array, array[minA], lastB) B_remaining = lastB.end - B_split // تبديل كتلة A الدنيا إلى بداية كتل A المتداولة BlockSwap (array, blockA.start, minA, block_size) // استعادة القيمة الثانية للكتلة A Swap (array[blockA.start + 1], array[buffer1.start + indexA]) مؤشر A++ // تدوير الكتلة A إلى داخل الكتلة B السابقة Rotate (array, blockA.start - B_split, [B_split, blockA.start + block_size)) // دمج محليًا كتلة A السابقة مع قيم B التي تليها، // باستخدام المخزن المؤقت الداخلي الثاني كمساحة تبديل (إن وُجد) إذا كان (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B_split), buffer2) else MergeInPlace (array, lastA, [lastA.end, B_split)) // تحديث نطاق الكتل المتبقية من النوع A، // والنطاق المتبقي من الكتلة B بعد تقسيمها lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size) lastB = [lastA.end، lastA.end + B_remaining) // إذا لم يتبق أي كتل من النوع A، فقد انتهت هذه الخطوة blockA.start = blockA.start + block_size إذا كانت قيمة (|blockA| = 0) فاخرج من الحلقة minA = [أصغر كتلة A جديدة] (انظر أدناه) وإلا إذا كان (|blockB| < حجم الكتلة) // انقل كتلة B الأخيرة، ذات الحجم غير المتساوي، // إلى ما قبل كتل A المتبقية، باستخدام تدوير Rotate (array, blockB.start - blockA.start, [blockA.start, blockB.end)) lastB = [blockA.start, blockA.start + |blockB|) blockA.start += |blockB| blockA.end += |blockB| minA += |blockB| blockB.end = blockB.start وإلا // قم بتدوير الكتلة A الموجودة في أقصى اليسار إلى النهاية عن طريق تبديلها مع الكتلة B التالية BlockSwap (array, blockA.start, blockB.start, block_size) lastB = [blockA.start، blockA.start + block_size) إذا كان (minA = blockA.start) minA = blockA.end blockA.start += block_size blockA.end += block_size blockB.start += block_size // هذا يعادل الحد الأدنى (blockB.end + block_size, B.end)، // ولكن هذا قد يؤدي إلى تجاوز الحد الأقصى إذا (blockB.end > B.end - block_size) blockB.end = B.end آخر blockB.end += block_size // دمج كتلة A الأخيرة مع قيم B المتبقية إذا كان (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B.end), buffer2) else MergeInPlace (array, lastA, [lastA.end, B.end))

إحدى التحسينات التي يمكن تطبيقها خلال هذه الخطوة هي تقنية الثقب العائم . ^{[ 7 ]} عندما يتم إسقاط كتلة A الدنيا خلف كتلة B السابقة، ثم تدويرها إليها، وبعد ذلك يتم تبديل محتوياتها إلى المخزن المؤقت الداخلي الثاني لعمليات الدمج المحلية، سيكون من الأسرع تبديل كتلة A إلى المخزن المؤقت مسبقًا، والاستفادة من حقيقة أن محتويات هذا المخزن المؤقت لا تحتاج إلى الاحتفاظ بأي ترتيب. لذا، بدلًا من تدوير المخزن المؤقت الثاني (الذي كان كتلة A قبل تبديل الكتل) إلى كتلة B السابقة عند الفهرس 1 ، يمكن ببساطة تبديل قيم كتلة B بعد الفهرس 1 مع آخر عناصر المخزن المؤقت.

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

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

MergeInternal (array, A, B, buffer) // تبديل القيم في A مع القيم الموجودة في 'buffer' BlockSwap (array, A.start, buffer.start, |A|) عدد العناصر A = 0، عدد العناصر B = 0، عدد العناصر المُدرجة = 0 بينما (عدد عناصر A < |A| وعدد عناصر B < |B|) إذا (array[buffer.start + عدد عناصر A] ≤ array[B.start + عدد عناصر B]) قم بتبديل (array[A.start + insert], array[buffer.start + عدد عناصر A]) عدد A++ وإلا قم بتبديل (array[A.start + insert], array[B.start + B_count]) B_count++ إدراج++ // تبديل الجزء المتبقي من المخزن المؤقت مع الجزء المتبقي من المصفوفة BlockSwap (array, buffer.start + A_count, A.start + insert, |A| - A_count)

إذا لم يكن المخزن المؤقت الثاني موجودًا، فيجب إجراء عملية دمج في مكانها تمامًا، مثل نسخة تعتمد على الدوران من خوارزمية هوانغ ولين، ^{[ 7 ] [ 8 ]} خوارزمية دودزينسكي وديدك، ^{[ 9 ]} أو بحث ثنائي متكرر وتدوير.

MergeInPlace (array, A, B) while (|A| > 0 and |B| > 0) // ابحث عن أول مكان في B حيث يجب إدراج العنصر الأول في A mid = BinaryFirst (array, array[A.start], B) // قم بتدوير A إلى مكانه المبلغ = منتصف - نهاية أ. تدوير (المصفوفة، الكمية، [A.start، منتصف)) // حساب نطاقي A و B الجديدين B = [mid, B.end) أ = [أ.البداية + الكمية، المنتصف) A.start = BinaryLast (array, array[A.start], A)

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

minA = blockA.start for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size) if (array[findA + 1] < array[minA + 1]) minA = findA

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

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

لاحظ أنه يمكن إعادة استخدام المخازن الداخلية لكل مجموعة من المصفوفات الفرعية A و B لهذا المستوى من فرز الدمج، ولا يلزم إعادة استخراجها أو تعديلها بأي شكل من الأشكال.

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

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

تشمل التطبيقات المعروفة لخوارزمية فرز الكتل ما يلي:

• تطبيق كوتزنر وكيم في لغة C++. ^{[ 11 ]}
• Wikisort، وهو تطبيق مايك مكفادين المستند إلى ورقة كوتزنر وكيم. ^{[ 12 ]}
• GrailSort (و HolyGrailSort المعاد كتابتها)، تطبيق أندريه أستريلين المستند إلى هوانغ ولانغستون (1992)، ^{[ 13 ]} والذي يصف في النهاية خوارزمية مشابهة جدًا. ^{[ 14 ]}
• خوارزمية الفرز الافتراضية في المكتبة القياسية لـ Zig ^{[ 15 ] [ 16 ]} منذ الإصدار 0.2.0 ^{[ 17 ]} .

تبدأ عملية فرز الكتل بإجراء فرز الإدراج على مجموعات من 16 إلى 31 عنصرًا في المصفوفة. فرز الإدراج عملية من ^رتبة O ( n² ) ، لذا فإن هذا يؤدي إلى زمن يتراوح بين O (16² ^× n / 16) و O (31² ^× n / 31) ، وهو O ( n ) عند حذف العوامل الثابتة . يجب أيضًا تطبيق فرز الإدراج على المخزن المؤقت الداخلي الثاني بعد اكتمال كل مستوى من مستويات الدمج. ومع ذلك، نظرًا لأن هذا المخزن المؤقت كان محدودًا بـ${\displaystyle {\sqrt {A}}}$من حيث الحجم،${\displaystyle O({\sqrt {n}}^{2})}$وتنتهي العملية أيضًا بـ O ( n ) .

بعد ذلك، يجب استخراج مخزنين داخليين لكل مستوى من مستويات فرز الدمج. يتم ذلك من خلال المرور على عناصر المصفوفتين الفرعيتين A وB وزيادة عداد كلما تغيرت القيمة، وعند العثور على عدد كافٍ من القيم، يتم تدويرها إلى بداية A أو نهاية B. في أسوأ الأحوال، سينتهي الأمر بالبحث في المصفوفة بأكملها قبل العثور على القيمة المطلوبة.${\displaystyle {\sqrt {A}}}$القيم الفريدة غير المتجاورة، الأمر الذي يتطلب O ( n ) من المقارنات و${\displaystyle {\sqrt {A}}}$دورات لـ${\displaystyle {\sqrt {A}}}$القيم. وهذا يؤدي إلى${\displaystyle O(n+{\sqrt {n}}\times {\sqrt {n}})}$أو O ( n ) .

عندما لم تحتوي أي من المصفوفات الفرعية A أو B على${\displaystyle {\sqrt {A}}}$لإنشاء المخازن المؤقتة الداخلية باستخدام قيم فريدة، تُجرى عملية دمج موضعي غير مثالية عادةً، حيث تُكرر عمليات البحث الثنائي وتدوير المصفوفة A إلى B. ومع ذلك، فإن النقص المعروف في القيم الفريدة داخل أي من المصفوفات الفرعية يفرض حدًا صارمًا على عدد عمليات البحث الثنائي والتدوير التي ستُجرى خلال هذه الخطوة، وهو ما يُعد مرة أخرى${\displaystyle {\sqrt {A}}}$تم تدوير العناصر حتى${\displaystyle {\sqrt {A}}}$مرات، أو O ( n ) . يتم أيضًا تعديل حجم كل كتلة ليكون أصغر في الحالة التي تم العثور عليها فيها${\displaystyle {\sqrt {A}}}$قيم فريدة ولكن ليس 2${\displaystyle {\sqrt {A}}}$، مما يحد بشكل أكبر من عدد القيم الفريدة الموجودة داخل أي كتلة A أو B.

يتم تنفيذ عملية وضع العلامات على الكتل A${\displaystyle {\sqrt {A}}}$يتم تكرار ذلك عدة مرات لكل مصفوفة فرعية A، ثم يتم تمرير كتل A وإدراجها في كتل B حتى${\displaystyle {\sqrt {A}}}$مرات. تحتفظ عمليات الدمج المحلية بنفس تعقيد O ( n ) لعملية الدمج القياسية، وإن كان ذلك مع المزيد من عمليات الإسناد نظرًا لأنه يجب تبديل القيم بدلاً من نسخها. يتكرر البحث الخطي لإيجاد الحد الأدنى الجديد لكتلة A على${\displaystyle {\sqrt {A}}}$مكعبات${\displaystyle {\sqrt {A}}}$مرات. وعملية إعادة توزيع المخزن المؤقت مطابقة لعملية استخراج المخزن المؤقت ولكن بشكل عكسي، وبالتالي فإن لها نفس التعقيد O ( n ) .

بعد استبعاد جميع مستويات التعقيد باستثناء المستوى الأعلى ، ومع الأخذ في الاعتبار وجود log( n ) مستوى في حلقة الدمج الخارجية، ينتج عن ذلك تعقيد تقاربي نهائي قدره O ( n log( n )) في أسوأ الحالات ومتوسطها. أما في أفضل الحالات، حيث تكون البيانات مرتبة بالفعل، فإن خطوة الدمج تُجري n /16 مقارنة للمستوى الأول، ثم n /32 ، ثم n /64 ، ثم n /128 ، وهكذا. هذه متسلسلة رياضية معروفة تُختزل إلى O ( n ) .

بما أن فرز الكتل غير تكراري ولا يتطلب استخدام تخصيصات ديناميكية ، فإن هذا يؤدي إلى مساحة ثابتة في المكدس والكومة. يستخدم هذا الفرز ذاكرة مساعدة من رتبة O (1) في نموذج ثنائي التفرع ، والذي يقبل أن عدد البتات اللازمة لتتبع نطاقات A وB، والبالغة O (log n )، لا يمكن أن يتجاوز 32 بتًا على أنظمة الحوسبة 32 بت أو 64 بتًا على التوالي، وبالتالي يتبسط إلى مساحة O (1) لأي مصفوفة يمكن تخصيصها عمليًا.

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

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

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

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

فرز الكتل هو فرز تكيفي على مستويين: أولاً، يتخطى دمج المصفوفات الفرعية A وB المرتبة أصلاً. ثانياً، عندما تحتاج A وB إلى الدمج، وتكونان مقسمتين إلى كتل متساوية الحجم، يتم تمرير كتل A عبر B بالقدر اللازم فقط، ويتم دمج كل كتلة مع قيم B التي تليها مباشرة. كلما كانت البيانات أكثر ترتيباً في الأصل، قلّ عدد قيم B التي تحتاج إلى الدمج في A.