مفتوح ليلًا ونهارًاالدخول مجانيالمس المعروضات واكتشفها

القاعة F1 · الحوسبة

شاهد ست خوارزميات ترتيب تتسابق.

شغّل الترتيب الفقاعي والانتقائي والإدخالي والدمجي والسريع والكومي جنبًا إلى جنب. شاهد كل مقارنة وتبديل، وافهم لماذا يتوسع بعضها إلى ملايين العناصر بينما يتخلف بعضها الآخر.

كيف يعمل

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

أدوات التحكم تشبه مشغّل الفيديو لأن المحرك كذلك: تشغيل وإيقاف بشريط المسافة، وخطوة بخطوة بالسهم الأيمن، وإعادة بالزر R، وقائمة جديدة بالزر N، وخلط بالزر S، وسرعات من 0.25× إلى 8×. تُبرز لوحة الشيفرة كل سطر من الشيفرة الزائفة أثناء تنفيذه، فتتقدم الرسوم والبرنامج معًا. جرّب السباق نفسه مرتين: مرة بقائمة معكوسة، ومرة شبه مرتبة، وشاهد الترتيب الإدخالي يقفز من مؤخرة السباق إلى مقدمته.

الخوارزميات الست

ثلاث منها طرق تربيعية بسيطة — سهلة الكتابة، ومؤلمة على نطاق واسع. وثلاث طرقفعّالة تبلغ O(n log n)‎ بفرّق-تسد أو ببنية بيانات ذكية. كل مثال أدناه بايثون كاملة وقابلة للتشغيل، وتعمل على قائمة عادية.

الترتيب الفقاعي — تبادل الجارين

امشِ على القائمة مقارنًا الجارين ومبدّلًا الزوج غير المرتب. مع كل جولة “يطفو” أكبر عنصر غير مرتب إلى مكانه النهائي، فالجولة التالية أقصر بخطوة. وإذا مرّت جولة كاملة دون تبديل، فالقائمة مرتبة أصلًا ويتوقف الخوارزم مبكرًا — فضيلته الوحيدة المنجية، التي تمنح O(n)‎ للمدخلات المرتبة أصلًا.

def bubble_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

الترتيب الانتقائي — اختر الأصغر وكرر

اقسم القائمة إلى مقدمة مرتبة وبقية غير مرتبة. وفي كل خطوة امسح البقية كلها بحثًا عن أصغرها وبدّله إلى مكانه. يجري دائمًا العدد نفسه من المقارنات — نحو n²/2 — مهما كانت المدخلات مرتبة سلفًا؛ لذلك فأفضل الحالات ومتوسطها وأسوأها كلها O(n²)‎. وفضيلته أنه يجري n تبديلًا على الأكثر، وكان ذلك مفيدًا حين كان التبديل مكلفًا.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

الترتيب الإدخالي — طريقة لاعب الورق

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

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

الترتيب الدمجي — قسّم وقهّر وادمج

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

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

الترتيب السريع — التجزئة حول محور

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

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < p:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)
    return a

الترتيب الكومي — رتل أولويات متنكر

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

def heap_sort(a):
    def sift(lo, n, i):
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and a[lo + l] > a[lo + m]:
                m = l
            if r < n and a[lo + r] > a[lo + m]:
                m = r
            if m == i:
                return
            a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
            i = m
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift(0, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end, 0)
    return a

قراءة الجدول

تصف Big-O النمو لا المؤقت: تُتجاهل الثوابت والعتاد عمدًا لتظهر هيئة التوسع. والجدول أدناه هو المرجع المعياري (كورمن وآخرون، Introduction to Algorithms؛ وقاموس الخوارزميات وهياكل البيانات في NIST). و“مستقر” تعني أن العناصر المتساوية تحافظ على ترتيبها الأصلي.

الخوارزميةالأفضلالمتوسطالأسوأذاكرة إضافيةمستقر
Bubble SortO(n)O(n²)O(n²)O(1)نعم
Selection SortO(n²)O(n²)O(n²)O(1)لا
Insertion SortO(n)O(n²)O(n²)O(1)نعم
Merge SortO(n log n)O(n log n)O(n log n)O(n)نعم
Quick SortO(n log n)O(n log n)O(n²)O(log n)لا
Heap SortO(n log n)O(n log n)O(n log n)O(1)لا

جرّب في المحاكاة: سابق الست بقائمة معكوسة ثم شبه مرتبة. ينقلب ترتيب الوصول — يقفز الترتيب الإدخالي من مؤخرة السباق إلى مقدمته — ولا صيغة تعلّم ذلك مثل مشاهدته يحدث.

ثلاثة أخطاء شائعة

«Quick Sort هو الأسرع دائمًا.» هو في المتوسط من الأسرع، لكن Quick Sort البسيط له حالة أسوأ هي O(n²)، مثلًا حين يقع العنصر المحوري دائمًا عند أحد طرفي القائمة. أما Merge Sort و Heap Sort فيبقيان عند O(n log n) مهما كانت المدخلات.

«الطرق التربيعية البسيطة لا فائدة منها.» يُستخدم Insertion Sort كثيرًا مع القوائم الصغيرة، وأداؤه جيد جدًّا مع القوائم شبه المرتبة. وبرامج الترتيب المستخدمة عمليًّا تكون في الغالب هجينة وتتحول إلى Insertion Sort عند الأجزاء الصغيرة.

«الترتيب المستقر هو الذي لا يفشل أبدًا.» للاستقرار معنى محدد: العناصر المتساوية في المفتاح تحتفظ بالترتيب الذي كانت عليه قبل الترتيب. Merge Sort و Insertion Sort مستقران، أما Quick Sort و Heap Sort فليسا كذلك في صورتيهما المعتادتين.

أسئلة الزوار

ما هي خوارزمية الترتيب التي يجب استخدامها في الكود الحقيقي؟

دائمًا تقريبًا الترتيب المدمج في اللغة: sorted()‎ في بايثون، وArray.sort()‎ في جافاسكربت، أو Arrays.sort()‎ في جافا للكائنات. كلها هجينة هندسية (بايثون وجافا تستخدمان Timsort) بزمن O(n log n)، مستقرة، ومجرّبة من ملايين المستخدمين. الخوارزميات الست في هذه الصفحة تعلّم الأفكار وراء هذه الأدوات، ولا تستبدلها.

إذا كان الترتيب الفقاعي بطيئًا، فلماذا ما زال يُدرَّس؟

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

ماذا يعني أن يكون الترتيب مستقرًا؟

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

لماذا ليس الترتيب السريع هو الأسرع دائمًا رغم أنه O(n log n)‎ في المتوسط؟

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

هل تُشغّل المحاكاة الخوارزميات فعلًا أم أنها مجرد رسوم متحركة؟

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

ما الذي تعدّه ترميز Big-O فعلًا؟

كيف ينمو عدد الخطوات الأساسية مع المدخلات، متجاهلًا العوامل الثابتة. O(n²)‎ تعني أن مضاعفة المدخلات تضاعف العمل أربع مرات تقريبًا؛ وO(n log n)‎ تعني أن المضاعفة لا تزيد العمل إلا قليلًا عن الضعف. عند n = 1,000,000‎ يكون الفرق بين نحو تريليون عملية وعشرين مليونًا — دقائق أو حتى ساعات مقابل جزء من الثانية.

المصادر وقراءات إضافية

استشهد بهذه المعروضة

Eurekarium. (2026). مختبر الترتيب. https://eurekarium.com/ar/computing/sorting-lab/

آخر تحديث: