ما معنى Ordered Array (المصفوفة المرتّبة) في الخوارزميات وهياكل البيانات؟

المصفوفة المرتّبة (Ordered Array أو Sorted Array) هي ببساطة مصفوفة تُحافظ عناصرها دائمًا على ترتيب معيّن حسب قيمتها — تصاعديًا (من الأصغر إلى الأكبر) أو تنازليًا — بحيث لا يكفي أن تُضيف عنصرًا في نهاية المصفوفة، بل يجب أن تضعه في موضعه الصحيح ضمن الترتيب. هذا الشرط البسيط هو مصدر أهم ميزة فيها وأهم عيب في آن واحد: البحث يصبح سريعًا جدًا، لكن الإضافة والحذف يصبحان أبطأ.

انتبه إلى نقطة يخلط فيها كثيرون: كلمة «مرتّبة» هنا لا تعني ترتيب الفهارس (index)، فالمصفوفة العادية أصلًا لها فهارس مرتّبة 0، 1، 2… بل تعني أن القيم نفسها مرتّبة. فمصفوفة مثل [3, 8, 8, 15, 42] مرتّبة، أما [8, 3, 42, 8, 15] فغير مرتّبة رغم أن كلتيهما لهما نفس الفهارس.

لماذا تُهِمّ المصفوفة المرتّبة؟

الفائدة الأكبر هي إمكانية استخدام البحث الثنائي (Binary Search). بدل أن تمرّ على العناصر واحدًا واحدًا، تقارن بالعنصر الأوسط وتتجاهل نصف المصفوفة في كل خطوة. النتيجة: زمن بحث بمرتبة O(log n) بدل O(n) في البحث الخطي. عمليًا، البحث في مليون عنصر يحتاج نحو 20 مقارنة فقط بدل مليون.

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

الثمن: الإضافة والحذف

لا شيء بالمجّان. للحفاظ على الترتيب عند إضافة عنصر جديد، عليك:

1. تحديد الموضع الصحيح للعنصر (يمكن إيجاده بالبحث الثنائي بسرعة).
2. إزاحة كل العناصر التي تليه خطوة واحدة إلى اليمين لتفريغ مكانه.
3. وضع العنصر في مكانه.

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

المصفوفة المرتّبة أم غير المرتّبة؟

العملية	مصفوفة مرتّبة	مصفوفة غير مرتّبة
البحث عن قيمة	O(log n) بالبحث الثنائي	O(n) بحث خطي
الوصول عبر الفهرس	O(1)	O(1)
الإضافة	O(n) (بسبب الإزاحة)	O(1) في النهاية
الحذف	O(n)	O(n) (أو O(1) إن لم يهمّك الترتيب)
إيجاد الأصغر/الأكبر	O(1) (طرفا المصفوفة)	O(n)

الخلاصة: اختر المرتّبة حين يغلب على عملك البحث والاستعلام، واختر غير المرتّبة حين يغلب الإدخال السريع ولا يهمّك ترتيب البحث.

مثال عملي على البحث الثنائي

لنفترض المصفوفة المرتّبة [1, 3, 5, 7, 9, 11] ونريد قيمة 7:

1. قارن بالعنصر الأوسط 5. بما أن 7 > 5، تجاهل النصف الأيسر كله.
2. في النصف الأيمن [7, 9, 11] قارن بالأوسط 9. بما أن 7 < 9، انتقل يسارًا.
3. بقي العنصر 7، وهو المطلوب. وجدناه في 3 مقارنات فقط بدل احتمال 4 أو 5 في البحث الخطي.

أين تُستخدم عمليًا؟

المصفوفة المرتّبة ليست مجرد تمرين أكاديمي. تجدها في جداول البحث الثابتة (lookup tables) التي تُبنى مرة وتُقرأ كثيرًا، وفي أنظمة تخزين تعتمد على قوائم مرتّبة لدمجها بسرعة، وكأساس تعليمي لفهم هياكل أكثر تقدّمًا مثل أشجار البحث الثنائية (BST) والأكوام (Heaps)، التي وُجدت أصلًا لتقديم بحث سريع مع إضافة وحذف أسرع من O(n).

نصيحة من التجربة: إن كان جدول بياناتك يتغيّر باستمرار وتحتاج بحثًا سريعًا في آن واحد، فالمصفوفة المرتّبة غالبًا ليست الأداة الأمثل — فكّر في شجرة بحث متوازنة أو جدول تجزئة (Hash Table). أما إن كانت البيانات شبه ثابتة، فمصفوفة مرتّبة + بحث ثنائي حلٌّ بسيط وفعّال وموفّر للذاكرة.

الأسئلة الشائعة

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

ما الفرق بين المصفوفة المرتّبة وخوارزمية الفرز؟ الفرز عملية تُجرى مرة لترتيب مصفوفة غير مرتّبة. أما المصفوفة المرتّبة فبنية تُحافظ على الترتيب دائمًا مع كل إضافة، فلا تحتاج إعادة فرز.

هل يعمل البحث الثنائي على أي مصفوفة؟ لا. يشترط أن تكون المصفوفة مرتّبة. تطبيقه على مصفوفة غير مرتّبة يُعطي نتائج خاطئة.

متى أُفضّل جدول التجزئة (Hash Table) عليها؟ حين تحتاج بحثًا بمرتبة O(1) وإضافة سريعة ولا يهمّك ترتيب العناصر أو إيجاد أصغر/أكبر قيمة بسرعة.