مصفوفة مرتبة

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

تُعد المصفوفات المرتبة أكثر هياكل البيانات كفاءة من حيث المساحة مع أفضل موضع مرجعي للبيانات المخزنة بشكل تسلسلي.

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

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

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

يمكن البحث عن العناصر في مصفوفة مرتبة بواسطة فهرسها ( الوصول العشوائي ) في وقت O(1)، وهي عملية تستغرق O(log n ) أو O( n ) من الوقت بالنسبة لهياكل البيانات الأكثر تعقيدًا.

كتب جون فون نيومان أول برنامج لفرز المصفوفات ( فرز الدمج ) في عام 1945، عندما كان أول حاسوب يعمل بنظام البرامج المخزنة لا يزال قيد الإنشاء. ^{[ 1 ] [ 2 ]}

• خوارزمية الفرز
• خوارزمية البحث الثنائي
• الكومة (هيكل البيانات)
• بنية بيانات البحث