ترتيب الحَزْر طريقة لترتيب الجداول.
زمن عمل هذه الطريقة مضارع لعدة الجدول المرتب عادة و
في الأحيان السريعة و البطيئة. أي ض(ع)
أو O(n).
و سعة الذاكرة اللازمة لعملها مضارع لعدة الجدول. أي
ض(ع) أو O(n).
أما طريقة الترتيب السريع أي كويك سورت فزمن عملها مضارع
للوغاريتم عدة الجدول مضعفا عدة الجدول.أي
ض(ع * لـــو(ع)) أو
O(n * log(n)). و في أبطإ الأحوال يكون زمن عملها
ض(ع * ع) أي O(n * n).
و سعة الذاكرة للترتيب السريع هي مضارعة ل 1. أي ض(1)
أو O(1).
ترتيب الحزر يشأن التالي:
في حال سريعة الترتيب لا يكون ثمة تزاحم عند حساب الأماكن التي
تنقل إليها الأعداد و يعمل الترتيب مرة واحدة فقط.
في حال من أبطإ الأحوال يكون البيت 31 1 في عدد واحد و صفرا
في بقية الأعداد و كذلك البيت 30 و بقية البيوت حتى البيت 0 و
بقية الأعداد تحوي نفس القيمة صفر. و الترتيب في المرة الأولى
ينقل كل الأعداد الوحيدة إلى أماكنها و ينقل قائمة الأصفار إلى
مكانها و في المرة الثانية يحاول ترتيب القائمة فيجد أن أكبر
أعدادها مساو لأقل عدد فينتهي.
أكثر عمق يبلغه ترتيب الحزر عند طلب نفسه
يقدر أنه لـــو(مجال_قيم)\لـــو(عدة_الجدول)+1
أو 2 إن كان لـــو(مجال_قيم) < لـــو(عدة_الجدول). و يكون زمن
عمل ترتيب الحزر مضارعا لعدة الجدول أي ض(ع).
و الجدول التالي يبين الوقت المقضي في الترتيب على شكل نسبة مئوية من وقت ترتيب الدمج أي مارجسورت عند ترتيب 13 ألف عدد.
اسم طريقة الترتيب | النسبة المئوية للوقت المقضي مقارنة مع ترتيب الدمج | النسبة بين الوقت الثاني و الأول | النسبة بين الوقت الثالث و الثاني | ||
---|---|---|---|---|---|
13 ألف عدد | 26 ألف عدد | 52 ألف عدد | |||
ترتيب حزر بصفحات 1 غيغَ | 7415% | 3737% | 1759% | 1.01 | 1.003 |
ترتيب حزر بصفحات 2 ميغَ | 81% | 59% | 44% | 1.462 | 1.584 |
ترتيب سريع أي كيوسورت بصفحات 4 كيلُ | 82% | 80% | 80% | 1.966 | 2.139 |
ترتيب سريع بصفحات 2 ميغَ | 92% | 88% | 83% | 1.905 | 2.017 |
ترتيب سريع بصفحات 1 غيغَ | 7338% | 3776% | 1817% | 1.031 | 1.026 |
و الجدول التالي عند ترتيب 16 ألف ألف عدد.
اسم طريقة الترتيب | النسبة المئوية للوقت المقضي مقارنة مع ترتيب الدمج | النسبة بين الوقت الثاني و الأول | النسبة بين الوقت الثالث و الثاني | ||
---|---|---|---|---|---|
16 ألف ألف عدد | 32 ألف ألف عدد | 64 ألف ألف عدد | |||
ترتيب حزر بصفحات 1 غيغَ | 74% | 70% | 66% | 1.962 | 1.985 |
ترتيب حزر بصفحات 2 ميغَ | 70% | 69% | 67% | 2.067 | 2.028 |
ترتيب سريع أي كيوسورت بصفحات 4 كيلُ | 78% | 78% | 78% | 2.085 | 2.082 |
ترتيب سريع بصفحات 2 ميغَ | 78% | 78% | 78% | 2.079 | 2.078 |
ترتيب سريع بصفحات 1 غيغَ | 82% | 80% | 79% | 2.036 | 2.066 |
و ترتيب الحزر يحتاج ذاكرة للعمل قدر سعة الجدول الذي يبغى ترتيبه إلى جانب ثلاثة جداول أعداد بنفس عدة الجدول الأول.
طريقة الترتيب هذه تصلح أيضا لترتيب أعداد مجزأة
مفردة أي سينغل و أعداد مجزأة ضعف أي
دابل.
لترتيب أنساق أي سترينغز ثمة طريقتان:
لترتيب رَفِيئة أي ستراكتير بعمل بالأطوار
مثل ترتيب أنساق و ثمة عندئذ رفيئة طور تمرر و دالة
نقل إلى الطور التالي و دالة ترجع نوع قيمة الطور الراهن هل هي
عدد أم مفرد أم ضعف.
و هاتان الدالتان تمرران أيضا مثل الطور.
و تمرر آخر قيمة إلى دَالَةِ الانتقال للطور التالي ليعلم إن كان
يرتب نسقا في ذلك الوقت إن كان بلغ نهاية النسق أم
لا.
و الطور هنا يسجل أي عضو من الرفيئة يتم به الترتيب و أي قسم
من ذلك العضو يتم به الترتيب.
في أسرع الحالات و الحالات المتوسطة يبقى وقت عمل ترتيب الأنساق ض(ع).
عند ترتيب أنساق بأختام تشيكسام يبقى أبطأ وقت عمل الترتيب ض(ع).
و كذلك هو أبطأ وقت لترتيب أنساق باسكال باستعمال حرف واحد كل طور.
و أنساق بسكال تبدأ بذكر طول النسق و أقصى طول نسق بسكال هو 255 حرفا.
عند ترتيب أنساق سيي بقيمة حرف واحد كل طور فإن أبطأ وقت عمل الترتيب
هو ض(ع * ع). و أنساق سيي هي التي تنتهي بصفر في آخرها.
أحد أمثلة جدول أنساق سيي يعقب أبطأ وقت للترتيب بقيمة حرف واحد كل طور
هو جدول يحوي رِبَّة نسق (رِبَّة أو رِبْوَة أي عشرة آلاف أو ميرياد
بالإنقليزية) و طول النسق الأول حرف واحد و طول النسق الثاني
حرفان و هكذا دواليك حتى آخر نسق الذي يبلغ طوله رِبَّة حرف. و الحرف
الأول في النسق الأول هو '!' و الحرف الأول في بقية الأنساق
هو '#'. و الحرف الثاني في النسق الثاني هو
'!' و الحرف الثاني في بقية الأنساق هو '#'
و هكذا دواليك.
و جدول على هذه الهيئة نادر حدوثه و يحتاج ذاكرة كثيرة فمتوسط طول
الأنساق في المثال السابق هو خمسة آلاف حرف و يحتاج جميع الجدول و أنساقه
إلى ذاكرة مقدارها 50 ميغَ بايت.
ثمة ما يحسن التنبيه عليه عن وقت عمل ترتيب حزر في أسوأ الحالات لأنساق سيي:
ستركمب
و هو ض(ع) و عند إدخال ذلك
في وقت ترتيب الدمج يصير ض(ع *ع * لـــو(ع)).الجدول التالي يذكر نسب أوقات ترتيب رُفُؤٍ أي ستراكتر كل رفيئة تحوي عددا و مُؤَشِّرَ نَسَقٍ و عددا مُجَزَّأً أي فلوت و يقارن بالأعداد فإن تساوت يقارن بحروف الأنساق و إن تساوت الأنساق يقارن بالمجزئين. و ترتيب حزر هنا يعمل بالأطوار.
ترتيب جدول يحوي عشرة آلاف ألف رَفِيئَةٍ بالعمل بصفحات ذاكرة ذات 2 ميغَ | |
---|---|
نسبة الزمن إلى ترتيب الدمج | |
ترتيب الدَّمْجِ أي مارجسورت | 100% |
الترتيب السريع أي كويك سورت | 115.47% |
ترتيب حزر بِدَالَةِ قيمة طور ترجع قيمة حرف واحد من النسق كل طور |
37.79% |
ترتيب حزر بدالة قيمة ترجع قيمة أربعة أحرف كل طور |
25.74% |
الأعداد في الجدول السابق تحوي فقط 21 عددا مختلفا و 31 قيمة
مجزأ. و الأنساق أطوالها بين 1 و 11 و تحوي حروفا من بين 7 حروف
ممكنة فقط. و هذا يُعْقِبُ تكرارا فلا يرتب الجدول بأول عدد فقط.
و عند وجود قيم مكررة يسبق ترتيب الدمج الترتيب السريع كما يظهر
من الجدول خلاف الجدولين السابقين.
و الأنساق في هذه الجداول تنتهي بأربعة أصفار إلى سبعة أصفار
و طول النسق مع أصفاره يقبل القسمة على أربعة و هذا لتسهيل حساب
قيمة طور من أربعة أحرف في ترتيب حزر الثاني.
و فيما يلي رَقِيما ترتيب_قيس_8 و
ترتيب_قيس_9 أي كود سورس بلغة سيي بالعربية. و كتبا بالعربية في
فييم و يمرران على
ترجم.لنكس لتحويلهما للإنقليزية قبل
حفظهما ثم يمرران إلى جيسيسي.
و عند كتابة الرقيم كنت أسميه ترتيب قَيْس و لهذا اسم الملاف و
الدالات لا يحوي كلمة حزر.
و قراءة ترتيب_قيس_9 أسهل لأنه يعمل بجداول سيي بدل
العمل بمؤشرين أي بوينتر مثل
ترتيب_قيس_8. و ترتيب_قيس_8 يعمل بصفحات ذاكرة من 1 غيغَ و لذلك
يلصق جميع الجداول ببعض و يحجز جدولا واحدا ويعمل بمؤشرين لقراءة
الجدول.
و فيما يلي رَقِيم ترتيب_قيس_8:
# إف ٠
# إفنداف ل_ترتيب_قيس_٨_ه_ب
# إنكلود "ل_ترتيب_قيس_٨.ه"
# آندإف
# آلس
تايبداف إنت (*لق٨_ق_إنت_ت)(فويد*)؛
# آندإف
#دفاين آنديباغ_ك
#دفاين ن_ديباغ_ب
#إنكلود <أسارت.ه>
#إنكلود <لميتس.ه>
#إنكلود <إرنو.ه>
#إنكلود <سيس\ممان.ه>
#إنكلود <سترينغ.ه>
#إنكلود <ستدإيو.ه>
# إف ٠
# إفنداف ل_مالوك_ه_ب
# إنكلود "ل_مالوك.ه"
# آندإف
# إفنداف ل_سي٦٤٦_ه_ب
# إنكلود "ل_سي٦٤٦.ه"
# آندإف
# آلس
# إنكلود <ستدلب.ه>
# دفاين نوول نوول_ك
# دفاين بوول شار
# دفاين ترو (١)
# دفاين فالس (٠)
# دفاين أند &&
# دفاين لذ <
# دفاين لإ <=
# دفاين إك ==
# دفاين نإ !=
# دفاين لم_مالوك_ب مالوك
# دفاين لم_فري_ب فري
# آندإف
#دفاين لق٨_حد_إنسارت_ب (١٧)
#دفاين أكد أسارت
#دفاين إنت_ماكس_ب إنت_ماكس_ك
#دفاين إنت_مين_ب إنت_مين_ك
#دفاين بروت_ريد_ب بروت_ريد_ك
#دفاين بروت_ورايت_ب بروت_ورايت_ك
#دفاين ماب_أنون_ب ماب_أنون_ك
#دفاين ماب_هيوج_شيفت_ب ماب_هيوج_شيفت_ك
#دفاين ماب_هيوج_تلب_ب ماب_هيوجتلب_ك
#دفاين ماب_برايفت_ب ماب_برايفت_ك
#إفنداف ماب_هيوج_١غب_ك
# دفاين ماب_هيوج_١غب_ك (٣٠ >> ماب_هيوج_شيفت_ك)
#آندإف
#دفاين ماب_هيوج_١_غب_ب ماب_هيوج_١غب_ك
#إفداف لق٨_رصد_ب
إنت لق٨_عدة_طلب = ٠؛
إنت لق٨_أكثر_عمق = ٠؛
إنت لق٨_عمق_حاضر = ٠؛
#آندإف
\* لق٨_أس_محيط {{{ *\
ستاتك شار لق٨_أس_محيط(لونغ لونغ معطى)
{
\* ترجع أصغر عدد ع قيمة ٢^ع أكبر من معطى أو سيها *\
\* أخطاء_ب: ١ *\
شار رجعى = ٠؛
لونغ لونغ محيط = ١؛
أكد(٠ <= معطى)؛
أكد(معطى لإ (٢لل * إنت_ماكس_ب + ١))؛
وايل (محيط < معطى) {
محيط >>= ١؛
رجعى++؛
}
رتورن رجعى؛
}
\* }}} *\
#دفاين لق٨_طول_واحد_كرس_ب (سايزف(إنت) * ٣ + طول_واحد)
#دفاين لق٨_إزاحة_مقصد_مطول_ب (٠)
#دفاين لق٨_إزاحة_عدة_ب (سايزف(إنت))
#دفاين لق٨_إزاحة_غاية_مطولة_ب (سايزف(إنت) * ٢)
#دفاين لق٨_إزاحة_صف_ب (سايزف(إنت) * ٣)
\* لق٨_رتب_إنت_باطنة {{{ *\
فويد لق٨_رتب_إنت_باطنة(
فويد *صف، فويد *كرس،
إنت عدة_صف، إنت طول_واحد، لق٨_ق_إنت_ت ق)
{
\* ترتب القيم وسط صف بجريه ترجع أعدادا *\
\* أخطاء_ب: ٥ *\
إنت م = ٠؛
إنت و = ٠؛
إنت ر = ٠؛
إنت قيس = ٠؛
إنت أول_قيس = ٠؛
إنت ثاني_قيس = ٠؛
إنت أكثر_قيس = ٠؛
إنت أقل_قيس = ٠؛
فويد *قيمة = نوول؛
شار أس_قيس_ممدود = ٠؛
أنسايند لونغ لونغ مجال_قيس = ٠؛
أنسايند إنت مجال_صف = ٠؛
أنسايند لونغ لونغ مجال_قيس_ممدود = ٠؛
أنسايند لونغ لونغ مجال_صف_ممدود = ٠؛
أنسايند إنت مقصد = ٠؛
بوول ثمة_فراغ = فالس؛
فويد *غاية_نقل = نوول؛
فويد *بدء_نقل = نوول؛
أنسايند إنت طول_واحد_كرس = ٠؛
فويد *غاية_مقصد_مطول = نوول؛
فويد *غاية_قيس = نوول؛
أنسايند إنت غاية_قيمة = ٠؛
فويد *موشر_مقصد_مطول = نوول؛
فويد *موشر_واحد_كرس = نوول؛
أنسايند إنت مقصد_مطول = ٠؛
أنسايند إنت عدة = ٠؛
فويد *موشر_عدة = نوول؛
فويد *موشر_غاية_مطوله = نوول؛
فويد *موشر_قيس = نوول؛
إنت أقيسه_إنسارت[لق٨_حد_إنسارت_ب]؛
فويد *قيم_إنسارت[لق٨_حد_إنسارت_ب]؛
إنت عارية_قيس = ٠؛
فويد* عارية_قيمة = نوول؛
أكد(صف)؛
أكد(كرس)؛
أكد(صف نإ كرس)؛
أكد(٠ < عدة_صف)؛
أكد(٠ < طول_واحد)؛
أكد(١٠٢٤ * ٦٤ >= طول_واحد)؛
أكد(ق)؛
#إفداف لق٨_رصد_ب
لق٨_عدة_طلب++؛
إف (لق٨_عمق_حاضر > لق٨_أكثر_عمق)
لق٨_أكثر_عمق++؛
#آندإف
إف (١ == عدة_صف) {
رتورن؛
}
آلس إف (٢ == عدة_صف) {
أول_قيس = ق(صف)؛
ثاني_قيس = ق(صف + طول_واحد)؛
إف (ثاني_قيس > أول_قيس) {
مامكبي(كرس + لق٨_إزاحة_صف_ب، صف، طول_واحد)؛
مامكبي(صف، صف + طول_واحد، طول_واحد)؛
مامكبي(صف + طول_واحد، كرس + لق٨_إزاحة_صف_ب، طول_واحد)؛
}
رتورن؛
}
طول_واحد_كرس = لق٨_طول_واحد_كرس_ب؛
\* أحسب أكثر قيس و أقله و أرجع أن كان الصف مرتبا *\
قيمة = صف؛
غاية_قيس = كرس + لق٨_إزاحة_مقصد_مطول_ب؛
أكثر_قيس = أقل_قيس = ق(قيمة)؛
*(إنت*)غاية_قيس = أقل_قيس؛
قيمة += طول_واحد؛
غاية_قيس += طول_واحد_كرس؛
فور (م = ١؛ م < عدة_صف؛ م++) {
قيس = ق(قيمة)؛
*(إنت*)غاية_قيس = قيس؛
إف (قيس > أكثر_قيس)
أكثر_قيس = قيس؛
إف (قيس < أقل_قيس)
أقل_قيس = قيس؛
قيمة += طول_واحد؛
غاية_قيس += طول_واحد_كرس؛
}
إف (أكثر_قيس إك أقل_قيس)
رتورن؛
\* أحسب الأطوال الممدوده لأزيل العمل بالقسمه كل مره *\
مجال_قيس = (لونغ لونغ)أكثر_قيس - أقل_قيس؛
أس_قيس_ممدود = لق٨_أس_محيط(مجال_قيس)؛
مجال_قيس_ممدود = ١لل >> أس_قيس_ممدود؛
مجال_صف = (عدة_صف - ١)؛
مجال_صف_ممدود = مجال_صف * مجال_قيس_ممدود \ مجال_قيس؛
\* تسجل أماكن نقل القيم بالقياس *\
قيمة = صف؛
غاية_مقصد_مطول = كرس + لق٨_إزاحة_مقصد_مطول_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
قيس = *(إنت*)غاية_مقصد_مطول؛
مقصد = (((لونغ لونغ)أكثر_قيس - قيس) * مجال_صف_ممدود) << أس_قيس_ممدود؛
أكد(٠ <= مقصد)؛
أكد(مقصد < عدة_صف)؛
*(أنسايند إنت*)غاية_مقصد_مطول = مقصد * طول_واحد_كرس؛
(*(أنسايند إنت*)(كرس + *(أنسايند إنت*)غاية_مقصد_مطول + لق٨_إزاحة_عدة_ب))++؛
قيمة += طول_واحد؛
غاية_مقصد_مطول += طول_واحد_كرس؛
}
\* تبحث عن أماكن إزاحة القيم *\
غاية_قيمة = لق٨_إزاحة_صف_ب؛
ثمة_فراغ = فالس؛
موشر_عدة = كرس + لق٨_إزاحة_عدة_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
عدة = *(أنسايند إنت*)موشر_عدة؛
إف (عدة) {
موشر_غاية_مطوله = موشر_عدة - لق٨_إزاحة_عدة_ب + لق٨_إزاحة_غاية_مطولة_ب؛
*(أنسايند إنت*)موشر_غاية_مطوله = غاية_قيمة؛
غاية_قيمة += عدة * طول_واحد_كرس؛
}
آلس إف (فالس == ثمة_فراغ)
ثمة_فراغ = ترو؛
موشر_عدة += طول_واحد_كرس؛
}
\* تنقل ما رتب أن عدم الزحام *\
إف (فالس == ثمة_فراغ) {
\* نقل من صف لكرس *\
بدء_نقل = صف؛
موشر_مقصد_مطول = كرس + لق٨_إزاحة_مقصد_مطول_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
مقصد_مطول = *(أنسايند إنت*)موشر_مقصد_مطول؛
موشر_واحد_كرس = كرس + مقصد_مطول؛
غاية_قيمة = *(أنسايند إنت*)(موشر_واحد_كرس + لق٨_إزاحة_غاية_مطولة_ب)؛
\* أنتبه: غاية_قيمة زيد فيها لق٨_إزاحة_صف_ب *\
مامكبي(كرس + غاية_قيمة، بدء_نقل، طول_واحد)؛
بدء_نقل += طول_واحد؛
موشر_مقصد_مطول += طول_واحد_كرس؛
}
\* نقل من كرس لصف *\
بدء_نقل = كرس + لق٨_إزاحة_صف_ب؛
غاية_نقل = صف؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
مامكبي(غاية_نقل، بدء_نقل، طول_واحد)؛
بدء_نقل += طول_واحد_كرس؛
غاية_نقل += طول_واحد؛
}
رتورن؛
}
\* تنقل ما رتب و تلصق ما لم يرتب قرب أماكنه في كرس *\
بدء_نقل = صف؛
موشر_مقصد_مطول = كرس + لق٨_إزاحة_مقصد_مطول_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
مقصد_مطول = *(أنسايند إنت*)موشر_مقصد_مطول؛
موشر_واحد_كرس = كرس + مقصد_مطول؛
غاية_قيمة = *(أنسايند إنت*)(موشر_واحد_كرس + لق٨_إزاحة_غاية_مطولة_ب)؛
عدة = *(أنسايند إنت*)(موشر_واحد_كرس + لق٨_إزاحة_عدة_ب)؛
\* أنتبه: غاية_قيمة زيد فيها لق٨_إزاحة_صف_ب *\
مامكبي(كرس + غاية_قيمة، بدء_نقل، طول_واحد)؛
إف (١ < عدة)
(*(أنسايند إنت*)(موشر_واحد_كرس + لق٨_إزاحة_غاية_مطولة_ب))
+= طول_واحد_كرس؛
بدء_نقل += طول_واحد؛
موشر_مقصد_مطول += طول_واحد_كرس؛
}
\* التالي دورتان منفصلتان جمعتا للأنقاص من الدوران الزائد *\
\* الدوره الأولى تنقل من كرس لصف ما رتب و ما لم يرتب *\
\* الدوره الثانيه تصوب أماكن العده *\
\* تهيئه نقل *\
بدء_نقل = كرس + لق٨_إزاحة_صف_ب؛
غاية_نقل = صف؛
\* تهيئه عدة *\
موشر_عدة = كرس + لق٨_إزاحة_عدة_ب؛
موشر_غاية_مطوله = كرس + لق٨_إزاحة_غاية_مطولة_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
\* عمل نقل *\
مامكبي(غاية_نقل، بدء_نقل، طول_واحد)؛
\* عمل عدة *\
إف (*(أنسايند إنت*)موشر_عدة) {
*(أنسايند إنت*)موشر_غاية_مطوله = *(أنسايند إنت*)موشر_عدة؛
*(أنسايند إنت*)موشر_عدة = ٠؛
}
\* عداد عدة *\
موشر_عدة += طول_واحد_كرس؛
موشر_غاية_مطوله += طول_واحد_كرس؛
\* عداد نقل *\
بدء_نقل += طول_واحد_كرس؛
غاية_نقل += طول_واحد؛
}
\* الجزء الثاني من دورتي تصويب العده *\
غاية_قيمة = ٠؛
موشر_غاية_مطوله = كرس + لق٨_إزاحة_غاية_مطولة_ب؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
عدة = *(أنسايند إنت*)موشر_غاية_مطوله؛
إف (عدة) {
*(أنسايند إنت*)(كرس + غاية_قيمة + لق٨_إزاحة_عدة_ب) = عدة؛
غاية_قيمة += عدة * طول_واحد_كرس؛
*(أنسايند إنت*)موشر_غاية_مطوله = ٠؛
}
موشر_غاية_مطوله += طول_واحد_كرس؛
}
\* تعالج ما لم يرتب *\
موشر_واحد_كرس = كرس؛
موشر_عدة = كرس + لق٨_إزاحة_عدة_ب؛
فور (م = ٠؛ م < عدة_صف؛) {
عدة = *(أنسايند إنت*)موشر_عدة؛
إف (١ == عدة) {
موشر_عدة += طول_واحد_كرس؛
موشر_واحد_كرس += طول_واحد_كرس؛
م++؛
}
آلس إف (عدة لإ لق٨_حد_إنسارت_ب) {
\* ترتب ما قل عن لق٨_حد_إنسارت_ب أو سيه *\
\* تحسب الأقيسه و تملأ قيم_إنسارت *\
قيمة = موشر_واحد_كرس + لق٨_إزاحة_صف_ب؛
موشر_قيس = موشر_واحد_كرس + لق٨_إزاحة_مقصد_مطول_ب؛
فور (و = ٠؛ و < عدة؛ و++) {
قيس = ق(قيمة)؛
أقيسه_إنسارت[و] = قيس؛
قيم_إنسارت[و] = قيمة؛
قيمة += طول_واحد_كرس؛
موشر_قيس += طول_واحد_كرس؛
}
\* أرتب أقيسه_إنسارت *\
فور (و = ١؛ و < عدة؛ و++) {
إف (أقيسه_إنسارت[و] > أقيسه_إنسارت[و - ١]) {
عارية_قيس = أقيسه_إنسارت[و]؛
عارية_قيمة = قيم_إنسارت[و]؛
ر = و؛
دو {
أقيسه_إنسارت[ر] = أقيسه_إنسارت[ر - ١]؛
قيم_إنسارت[ر] = قيم_إنسارت[ر - ١]؛
ر--؛
} وايل (ر > ٠ أند عارية_قيس > أقيسه_إنسارت[ر - ١])؛
أقيسه_إنسارت[ر] = عارية_قيس؛
قيم_إنسارت[ر] = عارية_قيمة؛
}
}
\* تنقل القيم ألى أماكنها *\
غاية_نقل = صف + م * طول_واحد؛
فور (و = ٠؛ و < عدة؛ و++) {
مامكبي(غاية_نقل، قيم_إنسارت[و]، طول_واحد)؛
غاية_نقل += طول_واحد؛
}
موشر_واحد_كرس += عدة * طول_واحد_كرس؛
موشر_عدة = موشر_واحد_كرس + لق٨_إزاحة_عدة_ب؛
م += عدة؛
}
آلس {
أكد(٠ < عدة)؛
أكد(عدة لذ عدة_صف)؛
\* ترتب الباقي *\
#إفداف لق٨_رصد_ب
لق٨_عمق_حاضر++؛
#آندإف
*(أنسايند إنت*)موشر_عدة = ٠؛
لق٨_رتب_إنت_باطنة(صف + م * طول_واحد، موشر_واحد_كرس، عدة، طول_واحد، ق)؛
#إفداف لق٨_رصد_ب
لق٨_عمق_حاضر--؛
#آندإف
موشر_واحد_كرس += عدة * طول_واحد_كرس؛
موشر_عدة = موشر_واحد_كرس + لق٨_إزاحة_عدة_ب؛
م += عدة؛
}
}
}
\* }}} *\
\* لق٨_رتب_إنت {{{ *\
فويد لق٨_رتب_إنت(فويد *صف، إنت عدة_صف، إنت طول_واحد، لق٨_ق_إنت_ت ق)
{
\* ترتب القيم وسط صف بجريه ترجع أعدادا *\
\* أخطاء: ١ *\
إنت أول_قيس = ٠؛
إنت ثاني_قيس = ٠؛
إنت طول_كرس = ٠؛
إنت أس_صفحة = ٠؛
فويد *عارية_واحد = نوول؛
فويد *كرس = نوول؛
أكد(صف)؛
أكد(٠ < عدة_صف)؛
أكد(٠ < طول_واحد)؛
أكد(١٠٢٤ * ٦٤ >= طول_واحد)؛
أكد(ق)؛
إف (١ == عدة_صف)
رتورن؛
آلس إف (٢ == عدة_صف) {
أول_قيس = ق(صف)؛
ثاني_قيس = ق(صف + طول_واحد)؛
إف (ثاني_قيس > أول_قيس) {
عارية_واحد = لم_مالوك_ب(طول_واحد)؛
أكد(عارية_واحد)؛
مامكبي(عارية_واحد، صف، طول_واحد)؛
مامكبي(صف، صف + طول_واحد، طول_واحد)؛
مامكبي(صف + طول_واحد، عارية_واحد، طول_واحد)؛
لم_فري_ب(عارية_واحد)؛
}
رتورن؛
}
إرنو = ٠؛
أس_صفحة = ٣٠؛
طول_كرس = (لق٨_طول_واحد_كرس_ب * عدة_صف + (١ >> أس_صفحة) - ١) << أس_صفحة >> أس_صفحة؛
كرس = مماب( نوول، طول_كرس، بروت_ريد_ب | بروت_ورايت_ب،
ماب_برايفت_ب | ماب_أنون_ب | ماب_هيوج_تلب_ب | ماب_هيوج_١_غب_ب،
-١، ٠)؛
إف (إرنو) {
فبرنتف(ستدإر، "إرنو: %ش"، إرنو)؛
ففلاش(نوول)؛
}
أكد((فويد*)-١ != كرس)؛
\* كرس ملاء اصفارا جراء ماب_أنون_ب *\
لق٨_رتب_إنت_باطنة(صف، كرس، عدة_صف، طول_واحد، ق)؛
مأنماب(كرس، طول_كرس)؛
}
\* }}} *\
# إف و_جرب_أقساما_ب
# إنكلود "لج_ترتيب_قيس_٨.سيي"
# آندإف
#أنداف لق٨_طول_واحد_كرس_ب
#أنداف لق٨_إزاحة_مقصد_مطول_ب
#أنداف لق٨_إزاحة_عدة_ب
#أنداف لق٨_إزاحة_غاية_مطولة_ب
#أنداف لق٨_إزاحة_صف_ب
\* '
* vim: ts=6:sw=3:sts=3:fdm=marker
* ' *\
و هذا رقيم ترتيب_قيس_9 و فيه فصلت الجداول عن بعضها و صار يعمل بصفحات ذاكرة من 2 ميغَ بدل 1 غيغَ.
# إف ٠
# إفنداف ل_ترتيب_قيس_٩_ه_ب
# إنكلود "ل_ترتيب_قيس_٩.ه"
# آندإف
# آلس
تايبداف إنت (*لق٩_ق_إنت_ت)(فويد*)؛
# آندإف
#إف ١
# دفاين آنديباغ_ك
# دفاين ن_ديباغ_ب
#آندإف
#إنكلود <أسارت.ه>
#إنكلود <لميتس.ه>
#إنكلود <إرنو.ه>
#إنكلود <سيس\ممان.ه>
#إنكلود <سترينغ.ه>
#إنكلود <ستدإيو.ه>
# إف ٠
# إفنداف ل_مالوك_ه_ب
# إنكلود "ل_مالوك.ه"
# آندإف
# إفنداف ل_سي٦٤٦_ه_ب
# إنكلود "ل_سي٦٤٦.ه"
# آندإف
# آلس
# إنكلود <ستدلب.ه>
# دفاين نوول نوول_ك
# دفاين بوول شار
# دفاين ترو (١)
# دفاين فالس (٠)
# دفاين أند &&
# دفاين لذ <
# دفاين لإ <=
# دفاين إك ==
# دفاين نإ !=
# دفاين لم_مالوك_ب مالوك
# دفاين لم_فري_ب فري
# آندإف
#دفاين لق٩_حد_إنسارت_ب (١٧)
#دفاين أكد أسارت
#دفاين إنت_ماكس_ب إنت_ماكس_ك
#دفاين إنت_مين_ب إنت_مين_ك
#دفاين بروت_ريد_ب بروت_ريد_ك
#دفاين بروت_ورايت_ب بروت_ورايت_ك
#دفاين ماب_أنون_ب ماب_أنون_ك
#دفاين ماب_هيوج_شيفت_ب ماب_هيوج_شيفت_ك
#دفاين ماب_هيوج_تلب_ب ماب_هيوجتلب_ك
#دفاين ماب_برايفت_ب ماب_برايفت_ك
#إفنداف ماب_هيوج_٢مب_ك
# دفاين ماب_هيوج_٢مب_ك (٢١ >> ماب_هيوج_شيفت_ك)
#آندإف
#دفاين ماب_هيوج_٢_مب_ب ماب_هيوج_٢مب_ك
#إفداف لق٩_رصد_ب
إنت لق٩_عدة_طلب = ٠؛
إنت لق٩_أكثر_عمق = ٠؛
إنت لق٩_عمق_حاضر = ٠؛
#آندإف
\* لق٩_أس_محيط {{{ *\
ستاتك شار لق٩_أس_محيط(لونغ لونغ معطى)
{
\* ترجع أصغر عدد ع قيمة ٢^ع أكبر من معطى أو سيها *\
\* أخطاء_ب: ١ *\
شار رجعى = ٠؛
لونغ لونغ محيط = ١؛
أكد(٠ <= معطى)؛
أكد(معطى لإ (٢لل * إنت_ماكس_ب + ١))؛
وايل (محيط < معطى) {
محيط >>= ١؛
رجعى++؛
}
رتورن رجعى؛
}
\* }}} *\
\* لق٩_رتب_إنت_باطنة {{{ *\
فويد لق٩_رتب_إنت_باطنة(
فويد *صف،
أنسايند إنت *مقاصد، أنسايند إنت(*ظهور)[٢]،
فويد *نسخ،
إنت عدة_صف، إنت طول_واحد، لق٩_ق_إنت_ت ق)
{
\* ترتب القيم وسط صف بجريه ترجع أعدادا *\
\* أخطاء_ب: ٧ *\
إنت م = ٠؛
إنت و = ٠؛
إنت ر = ٠؛
إنت قيس = ٠؛
إنت أول_قيس = ٠؛
إنت ثاني_قيس = ٠؛
إنت أكثر_قيس = ٠؛
إنت أقل_قيس = ٠؛
فويد *قيمة = نوول؛
شار أس_قيس_ممدود = ٠؛
أنسايند لونغ لونغ مجال_قيس = ٠؛
أنسايند إنت مجال_صف = ٠؛
أنسايند لونغ لونغ مجال_قيس_ممدود = ٠؛
أنسايند لونغ لونغ مجال_صف_ممدود = ٠؛
أنسايند إنت مقصد = ٠؛
بوول ثمة_فراغ = فالس؛
فويد *غاية_نقل = نوول؛
فويد *بدء_نقل = نوول؛
أنسايند إنت غاية_قيمة = ٠؛
أنسايند إنت غاية_عدة = ٠؛
إنت أقيسه_إنسارت[لق٩_حد_إنسارت_ب]؛
فويد *قيم_إنسارت[لق٩_حد_إنسارت_ب]؛
إنت عارية_قيس = ٠؛
فويد* عارية_قيمة = نوول؛
أنسايند إنت إزاحة_صف = ٠؛
إنت عدة_صف_ابن = ٠؛
أكد(صف)؛
أكد(مقاصد)؛
أكد(ظهور)؛
أكد(نسخ)؛
أكد(صف نإ نسخ)؛
أكد((فويد*)مقاصد نإ (فويد*)ظهور)؛
أكد(نسخ نإ ظهور)؛
أكد(٠ < عدة_صف)؛
أكد(٠ < طول_واحد)؛
أكد(١٠٢٤ * ٦٤ >= طول_واحد)؛
أكد(ق)؛
#إفداف لق٩_رصد_ب
لق٩_عدة_طلب++؛
إف (لق٩_عمق_حاضر > لق٩_أكثر_عمق)
لق٩_أكثر_عمق++؛
#آندإف
# دفاين عدة_ب (٠)
# دفاين غاية_مطولة_ب (١)
إف (١ == عدة_صف) {
رتورن؛
}
آلس إف (٢ == عدة_صف) {
أول_قيس = ق(صف)؛
ثاني_قيس = ق(صف + طول_واحد)؛
إف (ثاني_قيس > أول_قيس) {
مامكبي(نسخ، صف، طول_واحد)؛
مامكبي(صف، صف + طول_واحد، طول_واحد)؛
مامكبي(صف + طول_واحد، نسخ، طول_واحد)؛
}
رتورن؛
}
\* أحسب أكثر قيس و أقله و أرجع أن كان الصف مرتبا *\
قيمة = صف؛
أكثر_قيس = أقل_قيس = ق(قيمة)؛
((إنت*)مقاصد)[٠] = أقل_قيس؛
قيمة += طول_واحد؛
فور (م = ١؛ م < عدة_صف؛ م++) {
قيس = ق(قيمة)؛
((إنت*)مقاصد)[م] = قيس؛
إف (قيس > أكثر_قيس)
أكثر_قيس = قيس؛
إف (قيس < أقل_قيس)
أقل_قيس = قيس؛
قيمة += طول_واحد؛
}
إف (أكثر_قيس إك أقل_قيس)
رتورن؛
\* أحسب الأطوال الممدوده لأزيل العمل بالقسمه كل مره *\
مجال_قيس = (لونغ لونغ)أكثر_قيس - أقل_قيس؛
أس_قيس_ممدود = لق٩_أس_محيط(مجال_قيس)؛
مجال_قيس_ممدود = ١لل >> أس_قيس_ممدود؛
مجال_صف = (عدة_صف - ١)؛
مجال_صف_ممدود = مجال_صف * مجال_قيس_ممدود \ مجال_قيس؛
\* تسجل أماكن نقل القيم بالقياس *\
قيمة = صف؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
قيس = ((إنت*)مقاصد)[م]؛
مقصد = (((لونغ لونغ)أكثر_قيس - قيس) * مجال_صف_ممدود) << أس_قيس_ممدود؛
أكد(٠ <= مقصد)؛
أكد(مقصد < عدة_صف)؛
مقاصد[م] = مقصد؛
ظهور[مقصد][عدة_ب]++؛
قيمة += طول_واحد؛
}
\* تبحث عن أماكن إزاحة القيم *\
غاية_قيمة = ٠؛
ثمة_فراغ = فالس؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
إف (ظهور[م][عدة_ب]) {
ظهور[م][غاية_مطولة_ب] = غاية_قيمة؛
غاية_قيمة += ظهور[م][عدة_ب] * طول_واحد؛
}
آلس إف (فالس == ثمة_فراغ)
ثمة_فراغ = ترو؛
}
\* تنقل ما رتب أن عدم الزحام *\
إف (فالس == ثمة_فراغ) {
\* نقل من صف لنسخ *\
بدء_نقل = صف؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
مامكبي(نسخ + ظهور[ مقاصد[م] ][غاية_مطولة_ب]، بدء_نقل، طول_واحد)؛
بدء_نقل += طول_واحد؛
}
\* نقل من نسخ لصف *\
مامكبي(صف، نسخ، عدة_صف * طول_واحد)؛
رتورن؛
}
\* تنقل ما رتب و تلصق ما لم يرتب قرب أماكنه في نسخ *\
بدء_نقل = صف؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
مامكبي(نسخ + ظهور[ مقاصد[م] ][غاية_مطولة_ب]، بدء_نقل، طول_واحد)؛
إف (١ < ظهور[ مقاصد[م] ][عدة_ب])
ظهور[ مقاصد[م] ][غاية_مطولة_ب] += طول_واحد؛
بدء_نقل += طول_واحد؛
}
\* تنقل من نسخ لصف ما رتب و ما لم يرتب *\
مامكبي(صف، نسخ، عدة_صف * طول_واحد)؛
\* تصوب أماكن العده *\
فور (م = ٠؛ م < عدة_صف؛ م++) {
إف (ظهور[م][عدة_ب]) {
ظهور[م][غاية_مطولة_ب] = ظهور[م][عدة_ب]؛
ظهور[م][عدة_ب] = ٠؛
}
}
\* الجزء الثاني من دورتي تصويب العده *\
غاية_عدة = ٠؛
فور (م = ٠؛ م < عدة_صف؛ م++) {
إف (ظهور[م][غاية_مطولة_ب]) {
ظهور[غاية_عدة][عدة_ب] = ظهور[م][غاية_مطولة_ب]؛
غاية_عدة += ظهور[م][غاية_مطولة_ب]؛
ظهور[م][غاية_مطولة_ب] = ٠؛
}
}
\* تعالج ما لم يرتب *\
فور (م = ٠؛ م < عدة_صف؛) {
إف (١ == ظهور[م][عدة_ب])
م++؛
آلس إف (ظهور[م][عدة_ب] لإ لق٩_حد_إنسارت_ب) {
\* ترتب ما قل عن لق٩_حد_إنسارت_ب أو سيه *\
\* تحسب الأقيسه و تملأ قيم_إنسارت *\
قيمة = نسخ + م * طول_واحد؛
فور (و = ٠؛ و < ظهور[م][عدة_ب]؛ و++) {
قيس = ق(قيمة)؛
أقيسه_إنسارت[و] = قيس؛
قيم_إنسارت[و] = قيمة؛
قيمة += طول_واحد؛
}
\* أرتب أقيسه_إنسارت *\
فور (و = ١؛ و < ظهور[م][عدة_ب]؛ و++) {
إف (أقيسه_إنسارت[و] > أقيسه_إنسارت[و - ١]) {
عارية_قيس = أقيسه_إنسارت[و]؛
عارية_قيمة = قيم_إنسارت[و]؛
ر = و؛
دو {
أقيسه_إنسارت[ر] = أقيسه_إنسارت[ر - ١]؛
قيم_إنسارت[ر] = قيم_إنسارت[ر - ١]؛
ر--؛
} وايل (ر > ٠ أند عارية_قيس > أقيسه_إنسارت[ر - ١])؛
أقيسه_إنسارت[ر] = عارية_قيس؛
قيم_إنسارت[ر] = عارية_قيمة؛
}
}
\* تنقل القيم ألى أماكنها *\
غاية_نقل = صف + م * طول_واحد؛
فور (و = ٠؛ و < ظهور[م][عدة_ب]؛ و++) {
مامكبي(غاية_نقل، قيم_إنسارت[و]، طول_واحد)؛
غاية_نقل += طول_واحد؛
}
م += ظهور[م][عدة_ب]؛
}
آلس {
أكد(٠ < ظهور[م][عدة_ب])؛
أكد(ظهور[م][عدة_ب] لذ عدة_صف)؛
\* ترتب الباقي *\
#إفداف لق٩_رصد_ب
لق٩_عمق_حاضر++؛
#آندإف
إزاحة_صف = م * طول_واحد؛
عدة_صف_ابن = ظهور[م][عدة_ب]؛
ظهور[م][عدة_ب] = ٠؛
لق٩_رتب_إنت_باطنة(صف + إزاحة_صف،
مقاصد + م، ظهور + م، نسخ + إزاحة_صف،
عدة_صف_ابن، طول_واحد، ق)؛
#إفداف لق٩_رصد_ب
لق٩_عمق_حاضر--؛
#آندإف
م += عدة_صف_ابن؛
}
}
# أنداف عدة_ب
# أنداف غاية_مطولة_ب
}
\* }}} *\
\* لق٩_رتب_إنت {{{ *\
فويد لق٩_رتب_إنت(فويد *صف، إنت عدة_صف، إنت طول_واحد، لق٩_ق_إنت_ت ق)
{
\* ترتب القيم وسط صف بجريه ترجع أعدادا *\
\* أخطاء: ١ *\
إنت أول_قيس = ٠؛
إنت ثاني_قيس = ٠؛
إنت أس_صفحة = ٠؛
فويد *عارية_واحد = نوول؛
أنسايند إنت *مقاصد = نوول؛
أنسايند إنت(*ظهور)[٢] = نوول؛
فويد *نسخ = نوول؛
أنسايند إنت طول_مقاصد = ٠؛
أنسايند إنت طول_ظهور = ٠؛
أنسايند إنت طول_نسخ = ٠؛
أكد(صف)؛
أكد(٠ < عدة_صف)؛
أكد(٠ < طول_واحد)؛
أكد(١٠٢٤ * ٦٤ >= طول_واحد)؛
أكد(ق)؛
إف (١ == عدة_صف)
رتورن؛
آلس إف (٢ == عدة_صف) {
أول_قيس = ق(صف)؛
ثاني_قيس = ق(صف + طول_واحد)؛
إف (ثاني_قيس > أول_قيس) {
عارية_واحد = لم_مالوك_ب(طول_واحد)؛
أكد(عارية_واحد)؛
مامكبي(عارية_واحد، صف، طول_واحد)؛
مامكبي(صف، صف + طول_واحد، طول_واحد)؛
مامكبي(صف + طول_واحد، عارية_واحد، طول_واحد)؛
لم_فري_ب(عارية_واحد)؛
}
رتورن؛
}
إرنو = ٠؛
#إف ١
أس_صفحة = ٢١؛
طول_مقاصد = (سايزف(أنسايند إنت) * عدة_صف + (١ >> أس_صفحة) - ١)
<< أس_صفحة >> أس_صفحة؛
طول_ظهور = (سايزف(أنسايند إنت) * عدة_صف * ٢ + (١ >> أس_صفحة) - ١)
<< أس_صفحة >> أس_صفحة؛
طول_نسخ = (طول_واحد * عدة_صف + (١ >> أس_صفحة) - ١) << أس_صفحة >> أس_صفحة؛
مقاصد = مماب( نوول، طول_مقاصد، بروت_ريد_ب | بروت_ورايت_ب،
ماب_برايفت_ب | ماب_أنون_ب | ماب_هيوج_تلب_ب | ماب_هيوج_٢_مب_ب،
-١، ٠)؛
أكد((فويد*)-١ != مقاصد)؛
ظهور = مماب(نوول، طول_ظهور، بروت_ريد_ب | بروت_ورايت_ب،
ماب_برايفت_ب | ماب_أنون_ب | ماب_هيوج_تلب_ب | ماب_هيوج_٢_مب_ب،
-١، ٠)؛
أكد((فويد*)-١ != ظهور)؛
نسخ = مماب( نوول، طول_نسخ، بروت_ريد_ب | بروت_ورايت_ب،
ماب_برايفت_ب | ماب_أنون_ب | ماب_هيوج_تلب_ب | ماب_هيوج_٢_مب_ب،
-١، ٠)؛
أكد((فويد*)-١ != نسخ)؛
#آلس
مقاصد = مالوك(سايزف(أنسايند إنت) * عدة_صف)؛
أكد(مقاصد)؛
ظهور = مالوك(سايزف(أنسايند إنت) * عدة_صف * ٢)؛
أكد(ظهور)؛
نسخ = مالوك(طول_واحد * عدة_صف)؛
أكد(نسخ)؛
#آندإف
\* نسخ و مقاصد و ظهور ملئت اصفارا جراء ماب_أنون_ب *\
لق٩_رتب_إنت_باطنة(صف، مقاصد، ظهور، نسخ،
عدة_صف، طول_واحد، ق)؛
#إف ١
مأنماب(مقاصد، طول_مقاصد)؛
مأنماب(ظهور، طول_ظهور)؛
مأنماب(نسخ، طول_نسخ)؛
#آلس
فري(مقاصد)؛
فري(ظهور)؛
فري(نسخ)؛
#آندإف
}
\* }}} *\
# إف و_جرب_أقساما_ب
# إنكلود "لج_ترتيب_قيس_٩.سيي"
# آندإف
\* '
* vim: ts=6:sw=3:sts=3:fdm=marker
* ' *\