فرز العد المستقر: نهايات التراكم ومواضع السجلات المتعادلة

عد المفاتيح ثم وضع السجلات

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

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

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

تعريف فرز العد، مرجع التراكم والتوزيع المستقر، تعريف ثبات الفرز في Python.

ست هويات بمفاتيح غير مرتبة

قائمة الأصل بالترتيب هي M بمفتاح اثنين، و Z بسالب واحد، و A باثنين، و D بصفر، و B بسالب واحد، و F بواحد. المطلوب تصاعد المفتاح، فيكون الناتج المستقر Z ثم B ثم D ثم F ثم M ثم A. Z تسبق B في الأصل عند المفتاح سالب واحد، و M تسبق A عند المفتاح اثنين، ولذلك يبقى هذا الترتيب في مجموعتي التعادل.

الأسماء اختيرت لكي لا يختلط الثبات بفرز الهوية. الترتيب الأبجدي B قبل Z و A قبل M سيقلب الأصل في المجموعتين، رغم أن المفاتيح قد تبقى تصاعدية. نحتفظ بكل زوج من الهوية والمفتاح أثناء النقل، ولا ننشئ سجلًا جديدًا اسمه المفتاح وحده. صورة مفتاحين متساويين لا تكفي للتمييز أي نسخة منهما ظهرت أولًا.

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

إزاحة السالب إلى خانات من صفر

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

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

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

تكرارات اثنين وواحد وواحد واثنين

نمر على السجلات ونزيد عداد خانة كل مفتاح. سالب واحد ظهر في Z و B، فتكون خانته اثنين. الصفر ظهر في D مرة، والواحد في F مرة، والاثنان في M و A مرتين. صف التكرارات بحسب المفاتيح سالب واحد وصفر وواحد واثنين هو اثنان وواحد وواحد واثنان، ومجموعه ستة سجلات.

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

لهذا نحتفظ بالأصل حتى مرحلة وضع السجلات، ونفصل صف التكرار من صف آخر سيعني نهايات التراكم. قد يحمل الصفان العدد اثنين في خانة معينة، لكن ذلك اتفاق موضعي لا يجعل تعريفهما واحدًا. نكتب اسم الصف وما الذي يعده قبل استعمال أي قيمة منه فهرسًا أو حدًا لمجموعة في الناتج.

التراكم يحدد حدود مجموعات الناتج

نجمع التكرارات من المفاتيح الأصغر إلى الأكبر، فنحصل على نهايات اثنين وثلاثة وأربعة وستة. قيمة ثلاثة عند المفتاح صفر تعني أن ثلاثة سجلات لها مفتاح لا يزيد على صفر. لذلك تحتل مجموعة الصفر موضعًا بعد سجلَي سالب واحد، ولا نضعها عند الفهرس ثلاثة نفسه قبل مراجعة أن التراكم عدد عناصر وحد توقف غير مشمول.

مجموعات الناتج تكون [0,2) لسالب واحد، و[2,3) للصفر، و[3,4) للواحد، و[4,6) للاثنين. حدودها متجاورة وتغطي ستة مواضع دون تداخل. آخر موضع داخل المجموعة الأولى واحد، وآخر موضع داخل الأخيرة خمسة. إذا كانت نهاية مجموعة ستة، فالخانة الأخيرة المسموح بها فيها هي ستة ناقص واحد.

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

ابدأ من F ثم B ثم D

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

ثم يأتي D بمفتاح صفر، ونهاية مجموعته ثلاثة، فنضعه في موضع اثنين وننقص المؤشر إلى اثنين. ملأنا الآن مواضع واحد واثنين وثلاثة بسجلات B و D و F، لكن ذلك لا يعني أن ترتيب المرور هو ترتيب الناتج الأمامي. المواضع المعلنة هي التي تحدد أين سيظهر كل سجل عند قراءة القائمة المكتملة.

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

ثم A وZ وM وتكتمل المجموعات

السجل A بمفتاح اثنين يستعمل النهاية ستة، فيوضع في موضع خمسة وتصبح نهاية العمل خمسة. ثم Z بمفتاح سالب واحد يستعمل نهاية العمل واحدًا، فيوضع في موضع صفر وتنقص إلى صفر. وأخيرًا M بمفتاح اثنين يستعمل النهاية خمسة، فيوضع في موضع أربعة وتنقص إلى أربعة.

نقرأ المواضع من صفر إلى خمسة فنجد Z و B و D و F و M و A، مع المفاتيح سالب واحد وسالب واحد وصفر وواحد واثنين واثنين. نُقلت الهويات كلها مرة، وبقي Z قبل B و M قبل A. المرور من النهاية وضع المتأخر من المتساويات في خانة أعلى، ثم وضع الأسبق قبلَه عند رجوعنا إليه، فحفظ ترتيب الأصل في المجموعتين.

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

عرض الرسم بالحجم الكامل

المرور الأمامي مع النهايات يقلب التعادل

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

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

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

خانات فارغة لا تنشئ سجلات

نأخذ المثال المستقل G بسالب اثنين، و H بواحد، و I بسالب اثنين. المجال من سالب اثنين إلى واحد يحوي أربع خانات، لكن مفتاحين فقط ظهرا. التكرارات اثنان وصفر وصفر وواحد، والنهايات اثنان واثنان واثنان وثلاثة. لا تعني النهايتان المتساويتان وجود سجلين وهميين عند سالب واحد أو صفر؛ تكراراتهما صفر.

الناتج G ثم I ثم H، ويحفظ ترتيب النسختين ذواتي سالب اثنين. تعمل الإزاحة والتراكم رغم الخانات الخالية، لأن المجموعة الفارغة لا تحتاج أي خانة إخراج. وعندما نراجع الصف، نحفظ ترتيب قيم المجال ونبين ما تمثله كل خانة. لا نستخدم رقم الفهرس وحده اسمًا للمفتاح إذا كانت نقطة البداية سالبة.

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

طول المجال ليس عدد القيم المختلفة

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

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

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

نوع المفتاح وهوية السجل

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

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

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

تغيير الأصل أو المفتاح يغير معنى الثبات

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

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

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

كلفة عدد عناصر وعدد خانات

تمر النسخة على السجلات للعد، وعلى خانات المجال للتراكم، ثم على السجلات للتوزيع. في النموذج البسيط لعدد هذه الخطوات يظهر العمل مع عدد السجلات n وطول المجال K، وليس مع عدد السجلات وحده. نحتاج كذلك عدادات المجال وقائمة ناتج، ونحتفظ في نسختنا بأثر المواضع، فلا نصف الحفظ بأنه مجرد رقمين في الذاكرة.

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

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

مرجع مستقر يفحص السجلات كاملة

راجعنا 3280 قائمة بأطوال من صفر إلى سبعة، ومفاتيح من سالب اثنين وصفر وثلاثة. أعطينا الهويات ترتيبًا يخالف الأبجدي كي لا يمر فرز هويات عند التعادل كأنه ثبات. قارنا الناتج بفرز Python المضمون الاستقرار عند اختيار المفتاح وحده، وبمرجع آخر يجمع سجلات كل مفتاح حسب ترتيب الأصل، دون استعمال نهايات التراكم أو مواضع الإنقاص.

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

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