فرز الأعداد الصحيحة

تعتمد الحدود الزمنية لخوارزميات فرز الأعداد الصحيحة عادةً على ثلاثة معايير: عدد قيم البيانات (n) المراد فرزها، وقيمة أكبر مفتاح ممكن (K) المراد فرزه، وعدد البتات (w) التي يمكن تمثيلها في كلمة واحدة من كلمات الآلة في الحاسوب الذي تُنفَّذ عليه الخوارزمية. ويُفترض عادةً أن w ≥ log₂ ₍ max( n , K )) ؛ أي أن كلمات الآلة كبيرة بما يكفي لتمثيل فهرس في تسلسل بيانات الإدخال، وكبيرة بما يكفي لتمثيل مفتاح واحد. ^{[ 2 ]}

تُصمَّم خوارزميات فرز الأعداد الصحيحة عادةً للعمل في نموذجي الحوسبة: آلة المؤشر وآلة الوصول العشوائي . ويكمن الاختلاف الرئيسي بين هذين النموذجين في كيفية عنونة الذاكرة. تسمح آلة الوصول العشوائي باستخدام أي قيمة مُخزَّنة في سجل كعنوان لعمليات قراءة وكتابة الذاكرة، بتكلفة وحدة واحدة لكل عملية. تُمكِّن هذه الخاصية من تنفيذ بعض العمليات المعقدة على البيانات بسرعة باستخدام البحث في الجداول. في المقابل، في نموذج آلة المؤشر، تستخدم عمليات القراءة والكتابة عناوين مُخزَّنة في مؤشرات، ولا يُسمح بإجراء عمليات حسابية على هذه المؤشرات. في كلا النموذجين، يُمكن جمع قيم البيانات، كما يُمكن عادةً إجراء عمليات منطقية ثنائية وعمليات إزاحة ثنائية عليها، بتكلفة وحدة واحدة لكل عملية. مع ذلك، تفترض خوارزميات فرز الأعداد الصحيحة المختلفة افتراضات متباينة حول ما إذا كان ضرب الأعداد الصحيحة مسموحًا به كعملية بوحدة زمنية. ^{[ 3 ]} كما تم النظر في نماذج حوسبة أخرى أكثر تخصصًا، مثل آلة الوصول العشوائي المتوازية . ^{[ 4 ]}

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

في نماذج الحوسبة ذات الذاكرة الخارجية ، لا توجد خوارزمية فرز أعداد صحيحة معروفة أسرع من فرز المقارنة. وقد أظهر الباحثون أنه في هذه النماذج، لا يمكن لفئات محدودة من الخوارزميات، التي تُقيّد طريقة معالجتها للمفاتيح، أن تكون أسرع من فرز المقارنة، ^{[ 5 ]} وأن وجود خوارزمية فرز أعداد صحيحة أسرع من فرز المقارنة سيؤدي إلى دحض فرضية قياسية في ترميز الشبكات . ^{[ 6 ]}

قائمة الانتظار ذات الأولوية هي بنية بيانات تُستخدم لإدارة مجموعة من العناصر ذات الأولويات العددية، وتتضمن عمليات لإيجاد العنصر ذي أقل قيمة أولوية وإزالته. تستغرق قوائم الانتظار ذات الأولوية القائمة على المقارنة، مثل الكومة الثنائية، وقتًا لوغاريتميًا لكل تحديث، بينما قد تكون بنى أخرى، مثل شجرة فان إمده بواس أو قائمة الانتظار ذات الدلو ، أسرع للمدخلات ذات الأولويات الصغيرة. يمكن استخدام هذه البنى في خوارزمية فرز التحديد ، التي تُرتّب مجموعة من العناصر من خلال البحث المتكرر عن أصغر عنصر في المجموعة وإزالته، ثم إعادة العناصر بالترتيب الذي وُجدت به. يمكن استخدام قائمة الانتظار ذات الأولوية لإدارة مجموعة العناصر في هذه الخوارزمية، ويمكن تحديد زمن تنفيذ هذه الخوارزمية على مجموعة من n عنصرًا بالوقت اللازم لتهيئة قائمة الانتظار ذات الأولوية، ثم إجراء n عملية بحث وإزالة. على سبيل المثال، يؤدي استخدام الكومة الثنائية كقائمة انتظار ذات أولوية في فرز التحديد إلى خوارزمية فرز الكومة ، وهي خوارزمية فرز مقارنة تستغرق وقتًا قدره O ( n log n ) . بدلاً من ذلك، فإن استخدام فرز التحديد مع قائمة انتظار دلو يعطي شكلاً من أشكال فرز الحمام ، واستخدام أشجار فان إمدي بواس أو قوائم انتظار الأولوية الصحيحة الأخرى يؤدي إلى خوارزميات فرز صحيحة سريعة أخرى. ^{[ 7 ]}

بدلاً من استخدام قائمة انتظار ذات أولوية للأعداد الصحيحة في خوارزمية الفرز، يمكن اتباع نهج معاكس، واستخدام خوارزميات فرز الأعداد الصحيحة كإجراءات فرعية ضمن بنية بيانات قائمة انتظار ذات أولوية للأعداد الصحيحة. استخدم ثورب (2007) هذه الفكرة لإثبات أنه إذا أمكن إجراء فرز الأعداد الصحيحة في زمن T ( n ) لكل مفتاح، فإن نفس الحد الزمني ينطبق على زمن كل عملية إدراج أو حذف في بنية بيانات قائمة انتظار ذات أولوية. يُعد اختزال ثورب معقدًا ويفترض توفر عمليات ضرب سريعة أو عمليات بحث في الجداول، ولكنه يقدم أيضًا قائمة انتظار ذات أولوية بديلة تستخدم عمليات الجمع والعمليات المنطقية فقط بزمن T ( n ) + T (log n ) + T (log log n ) + ... لكل عملية، مع ضرب الزمن على الأكثر في لوغاريتم متكرر . ^{[ 7 ]}

تُستخدم خوارزميات فرز الأعداد الصحيحة الكلاسيكية، مثل فرز الحمام ، وفرز العد ، وفرز الجذر ، على نطاق واسع وتُعدّ عملية. ^{[ 8 ]} ركّزت معظم الأبحاث اللاحقة على خوارزميات فرز الأعداد الصحيحة بشكل أقل على الجانب العملي وأكثر على التحسينات النظرية في تحليل أسوأ الحالات ، ولا يُعتقد أن الخوارزميات الناتجة عن هذا البحث عملية بالنسبة لبنى الحواسيب الحالية ذات 64 بت ، على الرغم من أن التجارب أظهرت أن بعض هذه الطرق قد تُحسّن فرز الجذر للبيانات التي تحتوي على 128 بت أو أكثر لكل مفتاح. ^{[ 9 ]} بالإضافة إلى ذلك، بالنسبة لمجموعات البيانات الكبيرة، قد تُعيق أنماط الوصول إلى الذاكرة شبه العشوائية للعديد من خوارزميات فرز الأعداد الصحيحة أدائها مقارنةً بخوارزميات فرز المقارنة المصممة مع مراعاة التسلسل الهرمي للذاكرة . ^{[ 10 ]}

يوفر فرز الأعداد الصحيحة أحد المعايير الستة في مجموعة معايير الرياضيات المنفصلة لأنظمة الحوسبة عالية الإنتاجية التابعة لـ DARPA ، ^{[ 11 ]} وأحد المعايير الأحد عشر في مجموعة معايير NAS Parallel .

يمكن استخدام شجرة فان إمده بواس كطابور أولوية لفرز مجموعة من n مفتاحًا، يتراوح كل منها بين 0 و K − 1 ، في زمن قدره O ( n log log K ) . يُعد هذا تحسينًا نظريًا على فرز الجذر عندما تكون قيمة K كبيرة بما يكفي. مع ذلك، يتطلب استخدام شجرة فان إمده بواس إما ذاكرة قابلة للعنونة المباشرة بسعة K كلمة، أو محاكاتها باستخدام جدول تجزئة ، مما يقلل المساحة إلى خطية ولكنه يجعل الخوارزمية عشوائية. يُعد طابور الأولوية Y-fast لـ Willard (1983) طابور أولوية آخر ذو أداء مشابه (بما في ذلك الحاجة إلى العشوائية في شكل جداول تجزئة) .

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

تسمح خوارزمية عشوائية معقدة لهان وثورب (2002) في نموذج حساب ذاكرة الوصول العشوائي للكلمات بتقليل هذه الحدود الزمنية إلى O( n √ log log K ) .

يُقال إن خوارزمية فرز الأعداد الصحيحة غير محافظة إذا تطلبت حجم كلمة w أكبر بكثير من log max( n , K ) . ^{[ 15 ]} كمثال متطرف، إذا كان w ≥ K ، وكانت جميع المفاتيح متميزة، فيمكن فرز مجموعة المفاتيح في وقت خطي بتمثيلها كمتجه بت ، مع بت 1 في الموضع i عندما يكون i أحد مفاتيح الإدخال، ثم إزالة البت الأقل أهمية بشكل متكرر. ^{[ 16 ]}

تستخدم خوارزمية الفرز المُعبأ غير المحافظة لألبرز وهاجيروب (1997) روتينًا فرعيًا، مبنيًا على شبكة الفرز الثنائي لكين باتشر ، لدمج سلسلتين مُرتبتين من المفاتيح، بحيث تكون كل سلسلة قصيرة بما يكفي لتعبئتها في كلمة واحدة. يتم تحويل مُدخل خوارزمية الفرز المُعبأ، وهو عبارة عن سلسلة من العناصر المخزنة عنصرًا واحدًا في كل كلمة، إلى شكل مُعبأ، أي سلسلة من الكلمات تحتوي كل منها على عدة عناصر مُرتبة، وذلك باستخدام هذا الروتين الفرعي بشكل متكرر لمضاعفة عدد العناصر المُعبأة في كل كلمة. بمجرد أن تصبح السلسلة في شكل مُعبأ، يستخدم ألبرز وهاجيروب نوعًا من فرز الدمج لفرزها؛ وعند دمج سلسلتين لتكوين سلسلة واحدة أطول، يمكن استخدام نفس روتين الفرز الثنائي لاستخراج الكلمات المُعبأة بشكل متكرر، والتي تتكون من أصغر العناصر المتبقية من السلسلتين. تُحقق هذه الخوارزمية تسارعًا كافيًا من تمثيلها المُعبأ لفرز مُدخلاتها في وقت خطي كلما أمكن أن تحتوي كلمة واحدة على Ω(log n log log n ) مفتاحًا. أي عندما يكون log K log n log log n ≤ cw لبعض الثوابت c > 0 .

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

قدم أجتاي وفريدمان وكوملوس (1984) نتيجة مبكرة في هذا الاتجاه باستخدام نموذج الحوسبة القائم على فحص الخلايا (وهو نموذج اصطناعي تُقاس فيه تعقيدات الخوارزمية بعدد عمليات الوصول إلى الذاكرة التي تُجريها فقط). واستنادًا إلى عملهم، وصف فريدمان وويلارد (1994) بنيتين للبيانات، هما كومة Q والكومة الذرية، واللتان يمكن تنفيذهما على جهاز ذي وصول عشوائي. تُعد كومة Q نسخة متوازية بتات من شجرة ثنائية ، وتتيح تنفيذ عمليات قائمة الانتظار ذات الأولوية واستعلامات الخلف والسابق في وقت ثابت لمجموعات من O ((log N ) ^1/4 ) عنصرًا، حيث N ≤ ^2w هو حجم الجداول المحسوبة مسبقًا اللازمة لتنفيذ بنية البيانات. أما الكومة الذرية فهي شجرة B حيث يُمثل كل عقدة في الشجرة بكومة Q؛ وتتيح عمليات قائمة الانتظار ذات الأولوية في وقت ثابت (وبالتالي الفرز) لمجموعات من (log N ) ^{O (1)} عنصرًا.

قدم أندرسون وآخرون (1998) خوارزمية عشوائية تُسمى فرز التوقيع، تسمح بفرز مجموعات تصل إلى 2O((log w) 1/2 − ε) عنصرًا في وقت خطي ، ^{لأي ثابت ε > 0. وكما في خوارزمية} كيركباتريك وريش ، يُجرون اختزال النطاق باستخدام تمثيل للمفاتيح كأرقام في النظام العددي ذي الأساس b، مع اختيار دقيق لقيمة b . تستبدل خوارزمية اختزال النطاق كل رقم بتوقيع، وهو قيمة مُجزأة بـ O (log n ) بت، بحيث يكون لكل رقم توقيع مختلف. إذا كانت n صغيرة بما يكفي، ستكون الأرقام الناتجة عن عملية الاستبدال هذه أصغر بكثير من المفاتيح الأصلية، مما يسمح لخوارزمية الفرز المُعبأ غير المُحافظة لألبرز وهاجيروب (1997) بفرز الأرقام المُستبدلة في وقت خطي. من القائمة المرتبة للأرقام المستبدلة، من الممكن تشكيل شجرة مضغوطة للمفاتيح في وقت خطي، ويمكن فرز أبناء كل عقدة في الشجرة بشكل متكرر باستخدام مفاتيح بحجم b فقط ، وبعد ذلك ينتج عن اجتياز الشجرة الترتيب المرتب للعناصر. 

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

منذ ذلك الحين، تم تطوير خوارزميات أفضل. على سبيل المثال، من خلال تطبيق تقنية كيركباتريك-رايش لتقليل النطاق بشكل متكرر حتى تصبح المفاتيح صغيرة بما يكفي لتطبيق خوارزمية فرز ألبرز-هاجيروب المعبأة، يصبح من الممكن الفرز في زمن O ( n log log n ) ؛ ومع ذلك، يتطلب جزء تقليل النطاق في هذه الخوارزمية إما ذاكرة كبيرة (تتناسب مع √K ) أو عشوائية على شكل جداول تجزئة. ^{[ 17 ]}

أظهر هان وثورب (2002) كيفية الفرز في زمن عشوائي O( n √ log log n ) . تعتمد تقنيتهما على استخدام أفكار متعلقة بفرز التوقيعات لتقسيم البيانات إلى قوائم فرعية صغيرة متعددة، بحجم صغير بما يكفي ليتمكن فرز التوقيعات من فرز كل منها بكفاءة. من الممكن أيضًا استخدام أفكار مماثلة لفرز الأعداد الصحيحة بشكل حتمي في زمن O ( n log log n ) ومساحة خطية. ^{[ 18 ]} باستخدام عمليات حسابية بسيطة فقط (بدون ضرب أو بحث في الجداول)، يمكن الفرز في زمن متوقع عشوائي O ( n log log n ) ^{[ 19 ]} أو بشكل حتمي في زمن O ( n (log log n ) ^{1 + ε} ) لأي ثابت ε > 0. ^{[ 1 ]}