CALM/arwiki huggingface dataset:
في عام 2009، اقترح فلاديمير ياروسلافسكي تطبيق ترتيب سريع جديدًا باستخدام محورين بدلاً من واحد. في القوائم البريدية لمكتبة جافا الأساسية، بدأ نقاشًا يدعي فيه أن خوارزميته الجديدة متفوقة على طريقة فرز مكتبة وقت التشغيل، والتي كانت تعتمد في ذلك الوقت على المتغير المستخدم على نطاق واسع والمضبوط بعناية من ترتيب سريع الكلاسيكي بواسطة بنتلي وماكلروي. تم اختيار الترتيب السريع لـ ياروسلافسكي كخوارزمية فرز افتراضية جديدة في مكتبة وقت تشغيل جافا 7 من أوراكل بعد اختبارات أداء تجريبية مكثفة.
عن التفضيلات والخوارزمية.
تنبني الخوارزمية على وضع العنصر الأول في المصفوفة (بإتخاذه محورًا), ثم ترتيب ووضع العناصر الأكبر من هذا المحور إلى جهة اليمنى من المصفوفة ووضع العناصر الأصغر في الجهة اليسرى. بهذه الطريقة يعتبر المحور في مكانه النهائي المرتّب. تسمى هذه العملية تجزئة ليتبقى من المصفوفة جزئين لم يتم ترتيبهما. نقوم بعد ذلك بإعادة هذه الطريقة على الجزئين المتبقيين من المصفوفة وهكذا نحدد محورا جديدا ونعيد عملية التجزئة. تتكرر هذه العملية إلى أن نحصل على مجموعة مرتبة.
إذا تم اختيار المحور بطريقة صحيحة، نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة، مع تعقيد بformula_1. والتي قد تتحول إلى formula_2 في الحالة الأصعب، وهي حالة جدول عناصره مرتبة أصلا. ولكن هذه الحالة بديهية لأن المجموعة مرتبة أصلا.
في الناحية العملية، بالنسبة للتجزئات مع عدد قليل لا يتجاوز بضع عشرات من العناصر، يتم اللجوء عادة إلى الترتيب بالإدراج الذي يكون أفضل من الترتيب السريع.
و بصفة عامة يعتبر الترتيب السريع الأكثر شيوعا (شعبية) من بين جميع خوارزميات الترتيب.
المشكلة الوحيدة تتمثل في كيفية اختيار المحور.
اختيار أفضل مؤشر.
عند استعمال الترتيب السريع لمجموعة مرتبة مسبقا، وبطريقة اعتباطية، يستغرق كما قلنا وقتا كبيرا، وذلك راجع لأن أول عنصر هو الذي يعتبر محورا، الشيء الذي يؤدي إلى عدم تقسيم المجموعة إلى قسمين أكبر وأصغر من المحور. لحل المشكل يتم اختيار العنصر الأوسط، كما يمكن اختياره عشوائيا من عنصرين متواجدين حول المركز، حيث أن عملية اختيار المحور أو الأساس تحدد أداء الخوارزمية وتأرجحها بين وقت التشغيل N*Log n وN^2 بصيغة Big O Notation.
تحسينات أخرى.
عند استعمال الترتيب السريع لترتيب مجموعة ذات عناصر كبيرة، يمكن تغيير تقنية الترتيب عند الوصول إلى مجموعة جزئية غير مرتبة عدد عناصرها صغير،10 أو أقل. الترتيب بالاختيار مناسب في هذه الحالة.
ترتيب سريع هي خوارزمية فرق تسد . يقوم أولاً بتقسيم مصفوفة الإدخال إلى مصفوفتين فرعيتين أصغر: العناصر المنخفضة والعناصر العالية. ثم يقوم بفرز المصفوفات الفرعية بشكل متكرر. خطوات الترتيب السريع الموضعي هي:
الحالة الأساسية للتكرار هي مصفوفات بحجم صفر أو واحد، وهي مرتبة حسب التعريف، لذلك لا تحتاج أبدًا إلى الفرز.
يمكن إجراء خطوات التحديد والتقسيم المحوري بعدة طرق مختلفة ؛ يؤثر اختيار مخططات التنفيذ المحددة بشكل كبير على أداء الخوارزمية.
مخطط تقسيم لوموتو.
يُنسب هذا المخطط إلى نيكو لوموتو وشاعه بنتلي في كتابه "برمجة بيرلز وكورمين وآخرون." في كتابهم "مقدمة في الخوارزميات". يختار هذا النظام المحور الذي يكون عادةً العنصر الأخير في المصفوفة. الخوارزمية تحتفظ بالفهرس لأنه يمسح المصفوفة باستخدام فهرس آخر مثل أن العناصر الموجودة في خلال الصغرى (شامل) أقل من المحور والعناصر الموجودة في خلال (شاملة) تساوي أو أكبر من المحور. نظرًا لأن هذا المخطط أكثر إحكاما وسهل الفهم، فإنه يستخدم بشكل متكرر في المواد التمهيدية، على الرغم من أنه أقل كفاءة من مخطط هور الأصلي، على سبيل المثال، عندما تكون جميع العناصر متساوية. يتحلل هذا المخطط إلى عندما تكون الصفيف في حالة جيدة بالفعل. كانت هناك متغيرات مختلفة مقترحة لتعزيز الأداء بما في ذلك طرق مختلفة لتحديد المحور، والتعامل مع العناصر المتساوية، واستخدام خوارزميات الفرز الأخرى مثل تصنيف الإدراج للمصفوفات الصغيرة وما إلى ذلك. في سودوكود، وهو تصنيف سريع يقوم بفرز العناصر في خلال الصغرى (شامل) للمصفوفة على النحو التالي:
algorithm quicksort(A, lo, hi) is
if lo &lt; hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] &lt; pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
يتم فرز المجموعة بأكملها بواسطة .
مخطط تقسيم هور.
يستخدم مخطط التقسيم الأصلي الذي وصفه توني هور مؤشرين يبدأان في نهايات المصفوفة التي يتم تقسيمها، ثم ينتقلان باتجاه بعضهما البعض، حتى يكتشفوا انعكاسًا: زوج من العناصر، واحد أكبر من أو يساوي المحور، واحد أقل من أو يساوي، بترتيب خاطئ بالنسبة لبعضها البعض. ثم يتم تبديل العناصر المقلوبة. عندما تلتقي المؤشرات، تتوقف الخوارزمية وتعيد الفهرس النهائي. يعتبر مخطط هور أكثر كفاءة من مخطط تقسيم لوموتو لأنه يقوم بإجراء مقايضات أقل بثلاث مرات في المتوسط، كما أنه ينشئ أقسامًا فعالة حتى عندما تكون جميع القيم متساوية.   ] مثل مخطط تقسيم لوموتو، سيؤدي تقسيم هور أيضًا إلى تدهور ترتيب سريع إلى للمدخلات التي تم فرزها بالفعل، إذا تم اختيار المحور ليكون العنصر الأول أو الأخير. مع وجود العنصر الأوسط كمحور، ينتج عن البيانات المصنفة (تقريبًا) عدم وجود مقايضات في أقسام متساوية الحجم تؤدي إلى أفضل سلوك حالة لـ ترتيب سريع، أي . مثل الآخرين، لا ينتج تقسيم هور نوعًا مستقرًا. في هذا المخطط، لا يكون الموقع النهائي للمحور بالضرورة في الفهرس الذي يتم إرجاعه، حيث يمكن أن ينتهي المحور والعناصر التي تساوي المحور في أي مكان داخل القسم بعد خطوة القسم، وقد لا يتم فرزها حتى الحالة الأساسية لـ يتم الوصول إلى القسم الذي يحتوي على عنصر واحد عبر العودية. المقطعان التاليان اللذان تكررهما الخوارزمية الرئيسية هما (العناصر ≤ المحور) و (العناصر ≥ المحور) مقابل و كما في مخطط لوموتو. ومع ذلك، فإن خوارزمية التقسيم تضمن مما يعني أن كلا القسمين الناتجين غير فارغين، وبالتالي لا يوجد خطر من التكرار اللانهائي. في الكود الزائف،
quicksort(A, lo, p)
pivot := A[ floor((hi + lo) / 2) ]
i := lo - 1
j := hi + 1
while A[i] &lt; pivot do
j := j - 1
while A[j] &gt; pivot
if i ≥ j then
return j
يتم تقريب التقسيم المحوري لأسفل، كما هو موضح هنا بواسطة دالة الأرضية ؛ هذا يتجنب استخدام A [hi] كمحور، مما قد يؤدي إلى تكرار لا نهائي.
يتم فرز المجموعة بأكملها حسب .
قضايا التنفيذ.
اختيار المحور.
في الإصدارات المبكرة جدًا من الترتيب السريع، غالبًا ما يتم اختيار العنصر الموجود في أقصى اليسار كعنصر محوري. لسوء الحظ، يتسبب هذا في سلوك أسوأ حالة على المصفوفات التي تم فرزها بالفعل، وهي حالة استخدام شائعة إلى حد ما. تم حل المشكلة بسهولة عن طريق اختيار إما فهرس عشوائي للمحور، أو اختيار المؤشر الأوسط للقسم أو (خاصة للأقسام الأطول) باختيار وسيط العنصر الأول والمتوسط والأخير من القسم للمحور (على النحو الموصى به من قبل عالم الكمبيوتر روبرت سيدجويك). تقاوم قاعدة "الوسيط من ثلاثة" حالة الإدخال المصنف (أو الفرز العكسي)، وتعطي تقديرًا أفضل للمحور الأمثل (الوسيط الحقيقي) بدلاً من تحديد أي عنصر فردي، في حالة عدم وجود معلومات حول ترتيب الإدخال معروف.
مقتطف رمز متوسط من ثلاثة لقسم لوموتو:
mid := ⌊(lo + hi) / 2
⌋ if A[mid] &lt; A[lo]
swap A[lo] with A[mid]
if A[hi] &lt; A[lo]
swap A[lo] with A[hi]
if A[mid] &lt; A[hi]
swap A[mid] with A[hi]
يضع الوسيط في codice_1 أولاً، ثم يتم استخدام القيمة الجديدة لـ codice_1 للمحور، كما هو الحال في الخوارزمية الأساسية المعروضة أعلاه.
على وجه التحديد، العدد المتوقع من المقارنات اللازمة لفرز العناصر (انظر ) مع الاختيار المحوري العشوائي هو . يؤدي متوسط ثلاثة محاور إلى خفض هذا إلى ، على حساب زيادة قدرها ثلاثة بالمائة في العدد المتوقع من المقايضات. قاعدة تمحور أقوى، للمصفوفات الأكبر، هي اختيار التاسع، وهو متوسط تكراري من ثلاثة (Mo3)، كما هو محدد.
يعد تحديد عنصر محوري أمرًا معقدًا أيضًا بسبب وجود تجاوز عدد صحيح . إذا كانت مؤشرات الحدود للمصفوفة الفرعية التي يتم فرزها كبيرة بدرجة كافية، فإن التعبير الساذج للفهرس الأوسط، ، سيؤدي إلى تجاوز التدفق وتوفير فهرس محوري غير صالح. يمكن التغلب على ذلك باستخدام، على سبيل المثال، لفهرسة العنصر الأوسط، على حساب حسابي أكثر تعقيدًا. تظهر مشكلات مماثلة في بعض الطرق الأخرى لاختيار العنصر المحوري.
عناصر متكررة.
باستخدام خوارزمية التقسيم مثل مخطط تقسيم لوموتو الموضح أعلاه (حتى إذا كان يختار قيمًا محورية جيدة)، يُظهر الترتيب السريع أداءً ضعيفًا للمدخلات التي تحتوي على العديد من العناصر المتكررة. تظهر المشكلة بوضوح عندما تكون جميع عناصر الإدخال متساوية: في كل تكرار، يكون القسم الأيسر فارغًا (لا توجد قيم إدخال أقل من المحور)، ويكون القسم الأيمن قد انخفض بمقدار عنصر واحد فقط (تتم إزالة المحور). وبالتالي، فإن مخطط تقسيم لوموتو يأخذ الوقت من الدرجة الثانية لفرز مجموعة من القيم متساوية. ومع ذلك، باستخدام خوارزمية التقسيم مثل نظام تقسيم هور، تؤدي العناصر المتكررة عمومًا إلى تقسيم أفضل، وعلى الرغم من إمكانية حدوث مبادلات غير ضرورية للعناصر المساوية للمحور، فإن وقت التشغيل ينخفض بشكل عام مع زيادة عدد العناصر المتكررة (مع ذاكرة التخزين المؤقت تقليل حجم المبادلة). في حالة تساوي جميع العناصر، يقوم مخطط تقسيم هور بتبديل العناصر دون داع، ولكن التقسيم نفسه هو أفضل حالة، كما هو مذكور في قسم قسم هور أعلاه.
لحل مشكلة مخطط تقسيم لوموتو (تسمى أحيانًا مشكلة العلم الوطني الهولندي )، يمكن استخدام روتين بديل لتقسيم الوقت الخطي يفصل القيم إلى ثلاث مجموعات: القيم الأقل من المحور، والقيم التي تساوي المحور، والقيم الأكبر من المحور. (يسمي بنتلي وماكلروي هذا "قسمًا سمينًا" وقد تم تنفيذه بالفعل في من الإصدار 7 يونكس . ) القيم التي تساوي المحور تم فرزها بالفعل، لذا يجب فرز الأقسام الأصغر من والأكبر من فقط بشكل متكرر. في الكود الزائف، تصبح خوارزمية الفرز السريع
p := pivot(A, lo, hi)
left, right := partition(A, p, lo,
hi) // note: multiple return values
quicksort(A, lo, left - 1)
quicksort(A, right + 1, hi)
يقوم codice_3 بإرجاع المؤشرات إلى العنصر الأول ("أقصى اليسار") وإلى العنصر الأخير ("أقصى اليمين") من القسم الأوسط. كل عنصر من القسم يساوي codice_4 وبالتالي يتم فرزها. وبالتالي، لا يلزم تضمين عناصر القسم في الاستدعاءات المتكررة codice_5 .
تحدث أفضل حالة للخوارزمية الآن عندما تكون جميع العناصر متساوية (أو يتم اختيارها من مجموعة صغيرة من ). في حالة كل العناصر المتساوية، سينفذ التصنيف السريع المعدل مكالمتين متتاليتين فقط على المصفوفات الفرعية الفارغة، وبالتالي ينتهي في الوقت الخطي (بافتراض أن codice_3 الفرعي لا يستغرق أكثر من الوقت الخطي).
هناك نوعان من التحسينات المهمة الأخرى، التي اقترحها سيدجويك والمستخدمة على نطاق واسع في الممارسة، هي:
التوازي.
صيغة ترتيب سريع الخاصة بفرق تسد تجعلها قابلة للتوازي باستخدام توازي المهام . يتم إنجاز خطوة التقسيم من خلال استخدام خوارزمية مجموع البادئة المتوازية لحساب فهرس لكل عنصر مصفوفة في قسمها من المصفوفة المقسمة. بالنظر إلى مجموعة من الحجم ، تقوم خطوة التقسيم بتنفيذ العمل في الوقت وتتطلب مساحة خدش إضافية. بعد تقسيم المصفوفة، يمكن فرز القسمين بشكل متكرر على التوازي. المتوازي يفرز مجموعة من الحجم في تعمل في الوقت باستخدام مساحة إضافية.
لدى ترتيب سريع بعض العيوب عند مقارنتها بخوارزميات الفرز البديلة، مثل دمج الفرز، مما يعقد موازنتها الفعالة. يؤثر عمق شجرة الانقسام والقهر في التصنيف السريع بشكل مباشر على قابلية توسيع الخوارزمية، ويعتمد هذا العمق بشكل كبير على اختيار الخوارزمية للمحور. بالإضافة إلى ذلك، من الصعب موازاة خطوة التقسيم بكفاءة في مكانها. يعمل استخدام مساحة التسويد على تبسيط خطوة التقسيم، ولكنه يزيد من أثر ذاكرة الخوارزمية والنفقات العامة الثابتة.
يمكن أن تحقق خوارزميات الفرز المتوازي الأخرى الأكثر تعقيدًا حدودًا زمنية أفضل. على سبيل المثال، في عام 1991، وصف ديفيد باورز الفرز السريع المتوازي (وفرز الجذر المرتبط) الذي يمكن أن يعمل في وقت على القراءة المتزامنة والكتابة المتزامنة (CRCW) وآلة الوصول العشوائي المتوازية (PRAM) مع معالجات بواسطة أداء التقسيم ضمنيًا.
التحليل الرسمي.
تحليل الحالة الأسوأ.
يحدث القسم غير المتوازن عندما تكون إحدى القوائم الفرعية التي يتم إرجاعها بواسطة إجراء التقسيم بحجم . قد يحدث هذا إذا كان المحور هو أصغر أو أكبر عنصر في القائمة، أو في بعض عمليات التنفيذ (على سبيل المثال، نظام تقسيم لوموتو كما هو موضح أعلاه) عندما تكون جميع العناصر متساوية.
إذا حدث هذا بشكل متكرر في كل قسم، فإن كل مكالمة متكررة تعالج قائمة بحجم أقل من القائمة السابقة. وبالتالي، يمكننا إجراء قبل أن نصل إلى قائمة الحجم 1. هذا يعني أن شجرة الاستدعاء عبارة عن سلسلة خطية من المكالمات المتداخلة عشر دعوة يفعل العمل للقيام به القسم، و formula_3، وذلك في هذه الحالة فرز سريع يأخذ وقت
تحليل أفضل حالة.
في الحالة الأكثر توازناً، في كل مرة نقوم فيها بإجراء قسم، نقسم القائمة إلى قسمين متساويين تقريبًا. هذا يعني أن كل مكالمة متكررة تعالج قائمة من نصف الحجم. ونتيجة لذلك، يمكننا أن نجعل فقط المتداخلة المكالمات قبل أن نصل إلى قائمة حجم 1. هذا يعني أن عمق شجرة الاستدعاء هو . لكن لا يوجد مكالمتان على نفس المستوى من شجرة الاستدعاء تعالج نفس الجزء من القائمة الأصلية ؛ وبالتالي، فإن كل مستوى من المكالمات يحتاج فقط إلى وقت معًا (كل مكالمة لها بعض الحمل الثابت، ولكن نظرًا لوجود في كل مستوى، يتم تضمين ذلك في عامل). والنتيجة هي أن الخوارزمية تستخدم الوقت فقط.
تحليل متوسط الحالة.
لفرز مجموعة من العناصر المتميزة في التوقع، بمتوسط كل تباديل عناصر باحتمالية متساوية . نسرد هنا ثلاثة أدلة شائعة لهذا الادعاء تقدم رؤى مختلفة حول طريقة عمل الترتيب السريع.
باستخدام النسب المئوية.
إذا كان لكل محور مرتبة في مكان ما في منتصف 50 بالمائة، أي بين 25 بالمائة و 75 بالمائة، فإنه يقسم العناصر بنسبة 25٪ على الأقل و 75٪ على الأكثر على كل جانب. إذا تمكنا من اختيار هذه المحاور باستمرار، فسنضطر فقط إلى تقسيم القائمة على الأكثر formula_4 مرات قبل الوصول إلى قوائم الحجم 1، مما ينتج عنه خوارزمية
عندما يكون الإدخال تبديلًا عشوائيًا، يكون للمحور ترتيب عشوائي، وبالتالي لا يمكن ضمان أن يكون في منتصف 50 بالمائة. ومع ذلك، عندما نبدأ من التقليب العشوائي، في كل استدعاء تكراري، يكون للمحور ترتيب عشوائي في قائمته، وبالتالي فهو في منتصف 50 بالمائة تقريبًا نصف الوقت. هذا جيد بما فيه الكفاية. تخيل أن عملة انقلبت: الرؤوس تعني أن رتبة المحور في منتصف 50 بالمائة، والذيل يعني أنه ليس كذلك. تخيل الآن أن العملة انقلبت مرارًا وتكرارًا حتى تحصل على شكل . على الرغم من أن هذا قد يستغرق وقتًا طويلاً، إلا أنه في المتوسط فقط، واحتمال عدم حصول العملة المعدنية على رؤوس أمر غير محتمل للغاية (يمكن جعل هذا صارمًا باستخدام حدود تشيرنوف). من خلال نفس الوسيطة، سينتهي عودية ترتيب سريع في المتوسط عند عمق مكالمة فقط formula_5 . ولكن إذا كان متوسط عمق المكالمة هو ، وكل مستوى من عمليات شجرة الاستدعاء في معظم العناصر، فإن إجمالي مقدار العمل المنجز في المتوسط هو المنتج . لا يتعين على الخوارزمية التحقق من أن المحور يقع في النصف الأوسط - إذا ضربناه بأي جزء ثابت من المرات، فهذا يكفي للتعقيد المطلوب.
باستخدام التكرارات.
طريقة بديلة هي إنشاء علاقة تكرار ، الوقت اللازم لفرز قائمة بالحجم . في أكثر الحالات غير المتوازنة، تتضمن مكالمة الفرز السريع الفردية العمل بالإضافة إلى مكالمتين متكررتين على قوائم الحجم و ، وبالتالي فإن علاقة التكرار هي
هذه هي نفس العلاقة بالنسبة لفرز الإدراج وفرز التحديد، وهي تحل أسوأ حالة .
في الحالة الأكثر توازناً، تتضمن مكالمة الفرز السريع الفردية عمل بالإضافة إلى مكالمتين متكررتين على قوائم بحجم ، وبالتالي فإن علاقة التكرار هي
هذا يعني أن الترتيب السريع، في المتوسط، يؤدي فقط نحو 39٪ أسوأ مما كان عليه في أفضل حالاته. وبهذا المعنى، فهي أقرب إلى الحالة الأفضل من الحالة الأسوأ. لا يمكن لفرز المقارنة استخدام مقارنات أقل من في المتوسط لفرز العناصر (كما هو موضح في مقالة فرز المقارنة ) وفي حالة الكبيرة، ينتج عن تقريب ستيرلينغ ، لذا فإن الترتيب السريع ليس أسوأ بكثير من نوع المقارنة المثالي. يعد متوسط وقت التشغيل السريع هذا سببًا آخر للهيمنة العملية للفرز السريع على خوارزميات الفرز الأخرى.
استخدام شجرة بحث ثنائية.
تتوافق شجرة البحث الثنائية التالية (BST) مع كل تنفيذ للفرز السريع: المحور الأولي هو العقدة الجذرية ؛ محور النصف الأيسر هو جذر الشجرة الفرعية اليسرى، ومحور النصف الأيمن هو جذر الشجرة الفرعية اليمنى، وهكذا. عدد مقارنات تنفيذ الفرز السريع يساوي عدد المقارنات أثناء إنشاء BST من خلال سلسلة من عمليات الإدراج. لذا، فإن متوسط عدد المقارنات للفرز السريع العشوائي يساوي متوسط تكلفة إنشاء BST عند إدراج القيم formula_13 تشكيل تبديل عشوائي.
ضع في اعتبارك BST تم إنشاؤه عن طريق إدراج تسلسل formula_13 من القيم التي تشكل التقليب العشوائي. دع تشير إلى تكلفة إنشاء BST. نملك formula_15 هو متغير عشوائي ثنائي يعبر عما إذا كان أثناء إدخال formula_16 كانت هناك مقارنة formula_17 .
حسب خطية التوقع، القيمة المتوقعة formula_18 من هو formula_19 بمجرد الفرز، حدد فترات الملاحظة الهيكلية الأساسية هي أن formula_16 بالمقارنة مع formula_17 في الخوارزمية إذا وفقط إذا formula_16 يقع داخل أحد الفترتين المتجاورتين لـ formula_17 .
لاحظ ذلك منذ ذلك الحين formula_13 هو تبديل عشوائي، formula_25 هو أيضًا تبديل عشوائي، لذا فإن الاحتمال formula_16 مجاور ل formula_17 هو بالضبط formula_28 .
ننتهي بحساب قصير:
formula_29 مقارنات (قريبة من الحد الأدنى النظري للمعلومات) و formula_30 عمليات؛ في أسوأ الأحوال يؤدونها formula_31 المقارنات (وكذلك العمليات) ؛ هذه في مكانها، وتتطلب إضافية فقط formula_32 الفراغ. تم إثبات الكفاءة العملية والتباين الأصغر في الأداء مقابل الأنواع السريعة المحسّنة (لسيارات سيدجويك وجون بنتلي - دوغلاس ماكلروي ).
جِرمة مدينة أثرية ليبية في الجزء الجنوب الغربي من البلاد بالصحراء الكبرى تنسب إلى سكانها القدامى الجرمنت. المدينة غير مسكونة حاليا.
بناها الجرمنتيون في القرن الأول للميلاد كعاصمة لدولتهم، وتعد من أهم وأقدم الشواهد والآثار في ليبيا الدالة عن تاريخ الليبيين القدماء.
اشتهر الجرمنتيون بجرأتهم الكبيرة وقدرتهم على اختراق الصحراء وشجاعتهم النادرة في التصدي للغزاة، فقاوموا النفوذ الروماني بالتحالف مع القبائل الليبية الأخرى حتى تمكنوا مجتمعين من الوصول إلى أبواب لبدة سنة 70م. ولم تقم علاقات سلمية مع الرومان إلا في عهد الإمبراطور الليبي الأصل (سيبتيموس سيفيروس) في القرن الثاني الميلادي، حيث نشطت التجارة وبلغت جرمة أوج ازدهارها في القرنين الثاني والثالث الميلاديين.
افتتحها عقبة بن نافع عام 49 هـ (حوالي 669 م).
اكتشفت مؤخرا بقايا مدينة جرمة الشهيرة، عاصمة الجرمنتيين تحت المدينة الإسلامية التي تحمل نفس الاسم والتي كانت تعد محطة مهمة لتجار القوافل. حيث كانت مدينة جرمة عامرة عندما فتحها المسلمون في القرن السابع الميلادي.
ويدل العدد الهائل من المدافن الجرمنتية المكتشفة في وادي الحياة على أنهم كانوا كثيرين. كما كشفت مواقع جرمنتية أخرى في مناطق متسعة تشمل كذلك وادي الشاطئ والمناطق المحيطة بزويلة ومرزق وغدوه ووادي برجوج. وهذا يدل على الانتشار السكاني كما يدل على انتعاش الزراعة في منطقة متسعة من الجنوب. هذا، ولقد ظهرت نقوشهم في المقابر والمعابد الفرعونية القديمة.
غير أن أغلب المعلومات الأثرية المتوفرة تخص المدافن الجرمنتية التي كان بعضها على شكل (أهرامات الحطية) والبعض الآخر على هيئة قباب تستند على قواعد مربعة (المقابر الملكية) ومقابر أبو درنه. وتتميز القبور الجرمنتية بأن لها شواهد على شكل راحة اليد (خميسة) تتقدمها موائد قربان حجرية. وتتراوح هذه الشواهد في الحجم من الصغير الذي لا يتعدى ارتفاعه 50سم إلى شواهد ضخمة ترتفع لمترين.
مجزرة صبرا وشاتيلا قد تعني:
حزب الكتائب اللبنانية، أحد أبرز الأحزاب السياسية اللبنانية. تأسس كحركة قومية شبابية سنة 1936 على يد بيار الجميل. كانت الحركة مستوحاة من الأحزاب الفاشية الأوروبية، أهمها الحزب النازي الألماني وحزب الكتائب الإسبانية، وذلك بعد زيارة مؤسسه لألمانيا خلال الحقبة النازية ليشارك بالألعاب الأولمبية. تحول إلى حزب سياسي سنة 1952. وقف الحزب مع الرئيس كميل شمعون خلال أحداث 1958. وشكل سنة 1968 الحلف الثلاثي مع حزب الوطنيين الأحرار والكتلة الوطنية متحصلا على 9 مقاعد خلال الانتخابات النيابية لتلك السنة.
وكان الحزب أهم فصيل يميني خلال بدايات الحرب الأهلية اللبنانية، وكان أبرز المساهمين في تكوين القوات اللبنانية. إلا أن الحزب تقلص دوره تدريجياً مع وفاة مؤسسه سنة 1984 وتراجع تاثيره على عمليات القوات اللبنانية. وشهد الحزب بعد الحرب عدة انقسامات.
في سنة 2001 انتخب كريم بقرادوني رئيساً للحزب، لكنه ما لبث أن دخل في نزاع مع أمين الجميل حول زعامة الحزب، وانتهى النزاع بتولي الجميّل منصب الرئيس الأعلى المستحدث وبقاء بقرادوني في موقع الرئيس.
شارك الحزب في الانتخابات النيابية لسنة 2005 وحصل فيها على 3 مقاعد لكل من بيار أمين الجميل عن دائرة المتن الشمالي، وصولانج الجميل عن دائرة بيروت الأولى، وأنطوان غانم عن دائرة بعبدا - عاليه، بالإضافة إلى نادر سكر الذي انتخب على لائحة حزب الله في دائرة بعلبك - الهرمل، وشارك الحزب في الحكومة التي تشكلت بعد الانتخابات عبر وزير الصناعة بيار أمين الجميل وذلك إلى اغتياله في 21 نوفمبر 2006. وفي 19 سبتمبر 2007 تلقى الحزب ضربة موجعة أخرى باغتيال أنطوان غانم أحد أبرز قيادييه.
وقد شارك الحزب في الانتخابات النيابية لدورة عام 2009 واستطاع الحصول على 5 مقاعد لكل من سامي الجميل عن دائرة المتن الشمالي، ونديم الجميل عن دائرة بيروت الأولى، وفادي الهبر عن دائرة عاليه، وإيلي ماروني عن دائرة زحلة، وسامر سعادة عن دائرة طرابلس.
أما في انتخابات عام 2018 حصل حزب الكتائب على 3 مقاعد في المجلس النيابي لكل من سامي الجميل و الياس حنكش عن دائرة المتن الشمالي، و نديم الجميل عن دائرة بيروت الأولى.
الخمسينيات.
تعود الاتصالات الأولى بين الكتائب وإسرائيل إلى 1951، فقد طلبت قيادة الحزب مساعدة ماليّة تحضيرًا للانتخابات النيابية. قدّم وزير الخارجية الإسرائيلي موشيه شاريت لها حوالي 3000 دولارًا أمريكيًا، على الرغم من تشكيكه بحظوظهم بالفوز في الانتخابات.
في 13 إبريل 1975 قامت ميليشيا الكتائب بعملية الحافلة (بوسطة عين الرمانة)، والتي يعتبرها البعض الشرارة التي بدأت الحرب الأهلية اللبنانية. في الأيام التالية لتلك العملية، قامت الكتائب مع بعض الحلفاء، مثل ميليشيا نمور الأحرار، بقتال الشوارع ضد ميليشيات الفلسطينية وميليشيا الحركة الوطنية اللبنانية.
وفي 16 سبتمبر 1982، قام إيلي حُبيقة، أحد قائدي الكتائب باقتراف مذبحة صبرا وشاتيلا حيث تم قتل حوالي 500 لاجئ فلسطيني في حي صبرا ومخيم شاتيلا المطوقين بقوات الجيش الإسرائيلي. وتمت العملية، والمعروفة بمذبحة صبرا وشاتيلا، بسماح الجيش الإسرائيلي للكتائب بالدخول إلى المنطقة بينما قام الجيش الإسرائيلي بمحاصرة وإنارة المنطقة ليلاً بالقنابل المضيئة، ومنع هرب أي شخص وعزل صبرا وشاتيلا عن العالم. كتبت جريدة الغارديان البريطانية أن إيلي حُبيقة كان قد تأثر بشدة لمذبحة خطيبته والكثير من أهله في مجزرة الدامور اللبنانية، عام 1976، على أيدي الميليشيات الفلسطينية وميليشيا الحركة الوطنية اللبنانية.
سراج الدين البُلْقِيْنيّ (724هـ - 805هـ) هو عمر بن رسلان بن نصير بن صالح بن عبد الخالق بن عبد الحق الكناني، سراج الدين أبو حفص العسقلاني الكناني من قبيلة كنانة العدنانية، أحد كبار الشافعية بمصر ولد ببلقينة أحد قرى مدينة المحلة الكبرى سنة 724 هـ .
ولد في أوائل القرن السابع في الثالث من شهر رمضان وتوفى في عام 805هـ. حج بيت الله مرتين سنة 740 هجريه وعام 747 هجريه. حفظ القرأّن الكريم وعمره سبع سنين وهي سن صغيره لم يضارعه فيها الا اطفال قلائل مثل العلامة ابن حجر العسقلاني كما حفظ البلقينى "المحرر" في الفقه و"الكافيه" في النحو لابن مالك ومختصر ابن الحاجب في أصول الفقه و"الشاطبيه" في القراءات، وكل ذلك في بلدته بلقينا. يقال إن صالح الجد الثالث لسراج الدين هو أول من سكن بلقينه ولذلك كان لقب البلقينى وهي قرية تابعه لمركز المحلة الكبرى محافظة الغربية بطريق طنطا. ومن المعروف أن بيت البلقينى بيت علم وفضل ورياسه وكرم، منهم من دفن بالقرية ومنهم من دفن بعيدا عنها.
وذكره أيضا العلامة الشيخ عبد الفتاح أبو علم وهو من نفس القرية التي ولد بها العلامة سراج الدين وكان الشيخ عبد الفتاح أبو علم يوصى بأهل بلقينا خيرا فهي أرض العلم والعلماء.
تزوج الشيخ سراج الدين ابنة العلامة الشيخ "ابن عقيل" ولازمته في شبيبته. أما أولاده فقد رزق بعدة منهم أشهر من نبغ في العلم منهم:
قدومه إلى القاهرة.
أتى به أبوه إلى القاهرة وعمره إثنا عشرة سنة. فطلب العلم ودرس على علماء عصره من أمثال العلامة "الميدومى" وقرأ الأصول على يد شيخه شمس الدين "الأصفهانى" والنحو على يد شيخه "أبى حيان" وقد أذن له بالفتوى وهو ابن خمة عشرة سنة.
فاق الأقران والزملاء واجتمعت فيه شروط الاجتهاد على وجهها الصحيح فقيل إنه "مجدد القرن التاسع الهجرى" وأثنى عليه شيوخه وزملاؤه وهو شاب، وانتهت به دراسة العلم في أقطار الأرض، وقصده العلماء والطلاب من كل صوب، واتته الفتوى من كل ناحية.
تولى عدة وظائف منها إفتاء دار العدل وسافر إلى دمشق سنة 769 هجريه فباشره مدة قصيره ثم عاد. وفي عام 793 هجريه سافر إلى حلب بصحبة السلطان "برقوق بن أنس العثماني " ودرس بها ثم عاد إلى القاهرة مع السلطان وعظم شأنه، وصار يجلس في مجلس السلطان بجواره وفوق قضاة القضاة، وعكف التدريس والتصنيف وانتفع به عامة الطلبة.
برقوق ابن انس العثماني هو أول سلاطين دولة المماليك الجراكسه العظماء وهو الذي دافع عن الحضارة الإسلامية ضد الموجه الشرسه الثانية من المغول بعد أن قتلوا العلماء والنساء والأطفال في دمشق، فقاد جيشا ضخما وزحف اليهم بالشام، لكنهم فروا خوفا منه وكان خيرا يعطف على الفقراء.
تتلمذ على يد الشيخ سراج الدين البلقينى تلاميذ كثيرة جدا منهم: حافظ دمشق "ابن ناصر الدين" والحافظ ابن حجر، الذي قال عنه خرجت له أربعين حديثا عن أربعين شيخا حدث بها مرارا وقرأت عليه دلائل النبوة " للبيهقى فشهد لى بالحفظ في المجلس العام. من تلاميذه أيضا الشيخ "برهان الدين المحدث: الذي قال عنه رأيته فريد دهره، فلم تر عينى أحفظ منه للفقه ولأحاديث الاحكام.
أنشأ العلامة سراج الدين البلقينى مدرسه بخط "بين السيارج" بحى باب الشعرية الآن بالقاهرة. خرجت ألاف العلماء وجمع فيها كل مريديه ومحبيه من نوابغ الطلاب وأوقف عليها الأوقاف الكثيرة مما تفضل الله بها عليه. تعلم في هذه المدرسة أيضا أولاده وأحفاده من علماء بيت البلقينى وكان ابن حجر أحد طلاب هذه المدرسة ودفن البلقينى بها.
كما ورد في كلمة الدكتور / مجاهد توفيق.. في مجلة منبر الإسلام
مؤلفاته وحلقاته بالجامع الأزهر.
كان لشيخ الإسلام سراج الدين حلقه كبيرة بالجامع الأزهر في الفقه الشافعي وغيره وكان يجلس فيها محبيه وأتباعه. ذلك بالإضافة إلى دروسه في مدرسته المشهورة وله مؤلفات كثيرة منها:
الموجود منه الجزء الرابع فقط يبتدئ بكتاب الأضحية وينتهى إلى كتاب الشهادات في مجلد بقلم معتاد قديم في 222 ورقه ويوجد تحت رقم 2132 ورقم 535 28 عام بمكتبة الأزهر تحت فن "فقه الشافعى".
توفى الشيخ عمر سراج الدين البلقينى نهار الجمعة العاشر من ذى القعدة وصلى عليه ولده جلال الدين ودفن بمدرسته بعد عمر مديد قضاه في خدمة الإسلام وعلومه فعليه سحائب الرحمة والرضوان. وقد رثاه تلميذه ابن حجر وغيره بقصائد طويله يقول ابن حجر في مطلعها:
يا عين جودى لفقد البحر بالمطر ** وأدرى الدموع ولا تبقى ولا تذرى
أقضى نهارى في هم وفي حزن *** وطول ليلى في فكر وفي سهر
وغاص قلبى في بحر الهموم أما *** ترى سقيط دموعى منه كالدرر
فرحمة الله والرضوان يشمله *** سلامة ما بلى باك على عمرى
لقد أقام منار الدين متضحا ** سراجه فأضاء الكون للبشر
من لو رأه ابن ادريس الإمام اذن ** أقرا وقر عيونا منه بالنظر
فحقق كم له بالفتح من مدد ** تحقيق رجوى نبى الله في عمر
والقصيدة طويلة جدا ولمن يريد مراجعتها فهي في كتاب بدائع الزهور لابن إياس الجزء الأول قسم 2
خيوة مدينة كانت تابعة لإقليم خراسان الكبرى، وتقع اليوم في غرب أوزبكستان. الاسم القديم والتاريخي لمدينة خيوة هو خوارزم. ولد بها العديد من العلماء المسلمين. وتقع ضمن مدينة خيوة قلعة إيجان وهي مدرجة على قائمة اليونسكو للتراث العالمي.