فرز الفقاعات وفرز الإدراج
برمج خوارزميتي الفرز التربيعيتين، وافهم سبب كونهما O(n²)، وتعرّف إلى الحالة الوحيدة التي يتفوق فيها فرز الإدراج على فرز الدمج
فرز الفقاعات وفرز الإدراج درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
لماذا ندرس خوارزميات الفرز ذات O(n²)؟
يعمل فرز الفقاعات وفرز الإدراج في O(n²) في أسوأ الحالات، مما يجعلهما غير عمليين للمدخلات الكبيرة. ومع ذلك، تتوقع منك كل مقابلة جادة في الخوارزميات تنفيذَهما وتحليلهما. فهما يعلّمان مفاهيم أساسية، مثل المقارنة والتبديل والفرز المستقر وسلوك أفضل حالة، وهي مفاهيم تنطبق على خوارزميات أكثر تقدمًا. ويستخدمهما القائمون بالمقابلات لاختبار قدرتك على الاستدلال بشأن ثوابت الحلقات والترميز التقاربي انطلاقًا من المبادئ الأولى.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')فرز الفقاعات: رفع القيمة العظمى
يمسح فرز الفقاعات المصفوفة مرارًا ويبدّل العناصر المتجاورة الخارجة عن الترتيب. بعد كل مرور كامل، «تطفو» أكبر قيمة غير مرتبة إلى موضعها النهائي في النهاية. وبعد n-1 مرورًا، تصبح المصفوفة كاملة مرتبة. جاءت التسمية من الطريقة التي تطفو بها العناصر الأكبر إلى الأعلى مثل الفقاعات. وهو أبسط خوارزمية فرز من حيث الوصف، لكنه نادرًا ما يُستخدم عمليًا.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]فرز الفقاعات مع الإنهاء المبكر
يستخدم فرز الفقاعات المحسّن راية swapped؛ فإذا لم ينتج عن مرور داخلي كامل أي تبديل، فهذا يعني أن المصفوفة مرتبة بالفعل، فننهي التنفيذ مبكرًا. يمنح ذلك أفضل حالة بتعقيد O(n) للمدخلات المرتبة مسبقًا، وهي ميزة فرز الفقاعات الحقيقية الوحيدة. ومن دون هذه الراية، ينفّذ دائمًا مقارنات بتعقيد O(n²). وتحسين الإنهاء المبكر هو ما يتحقق منه القائمون بالمقابلات عند السؤال عن تحسينات فرز الفقاعات.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passتحليل تعقيد فرز الفقاعات
تتكرر الحلقة الخارجية لفرز الفقاعات n-1 مرة. وتتكرر الحلقة الداخلية n-1-i مرة في كل مرور: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 من المقارنات. وهذا يعطي O(n²) في المتوسط وفي أسوأ الحالات. ومع راية الإنهاء المبكر، تنخفض أفضل حالة إلى O(n) للمدخلات المرتبة. ويبلغ تعقيد المساحة O(1)، إذ لا يتطلب الأمر سوى متغير مؤقت أثناء التبديل. وفرز الفقاعات مستقر؛ فالعناصر المتساوية تحافظ على ترتيبها النسبي لأننا لا نبدّل إلا العناصر الأكبر تمامًا.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5فرز الإدراج: بناء مجموعة بطاقات مرتبة
يحاكي فرز الإدراج ترتيب أوراق اللعب في اليد: تلتقط البطاقة التالية، أي العنصر، وتدرجها في الموضع الصحيح بين البطاقات المرتبة الموجودة إلى اليسار. والثابت هو أن arr[0:i] تكون مرتبة دائمًا. ولكل عنصر جديد، أزِح العناصر الأكبر نحو اليمين لإفساح المجال. هذه الخوارزمية تعمل في مكانها ومستقرة، ولها تعقيد O(n²) في أسوأ الحالات، لكنها تحقق O(n) في أفضل الحالات للبيانات شبه المرتبة.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]فرز الإدراج خطوة بخطوة
تتبّع فرز الإدراج على [3, 1, 4, 2]: i=1، وkey=1، أزِح 3 إلى اليمين ← [1, 3, 4, 2]. i=2، وkey=4، لا توجد إزاحات ← تبقى المصفوفة دون تغيير. i=3، وkey=2، أزِح 4 ثم 3 إلى اليمين ← [1, 2, 3, 4]. تتم مقارنة كل عنصر بالعناصر الموجودة إلى يساره حتى نعثر على موضعه الصحيح. تنفّذ حلقة while الداخلية الإزاحات باستخدام عمليات إسناد، وهي أسرع من التبديل لأن كل إزاحة تتطلب عملية إسناد واحدة مقابل ثلاث عمليات للتبديل.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]فرز الإدراج على البيانات شبه المرتبة
الميزة الأهم في فرز الإدراج هي تعقيده O(n + inversions). والانعكاس هو زوج (i,j) حيث i < j لكن arr[i] > arr[j]. في المصفوفات شبه المرتبة التي تحتوي على عدد قليل من الانعكاسات، يكون فرز الإدراج سريعًا جدًا، وقد يتفوق أحيانًا عمليًا على فرز الدمج بفضل بساطته ونمط وصوله الملائم لذاكرة التخزين المؤقت. ويستخدم Timsort فرز الإدراج للمصفوفات الفرعية الصغيرة لهذا السبب تحديدًا.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)الاستقرار في الفرز
تكون خوارزمية الفرز مستقرة إذا حافظت العناصر المتساوية على ترتيبها النسبي الأصلي بعد الفرز. كل من فرز الفقاعات وفرز الإدراج مستقر؛ فهما لا يبدّلان العناصر المتساوية أبدًا. يهم الاستقرار عند الفرز باستخدام مفاتيح متعددة بالتتابع: افرز أولًا حسب المفتاح الثانوي، مع الحفاظ على الاستقرار، ثم افرز حسب المفتاح الأساسي، مع الحفاظ على الاستقرار، للحفاظ على ترتيب المفتاح الثانوي بين العناصر المتساوية. وفرز الدمج مستقر أيضًا، أما فرز الكومة وفرز quick sort فعادةً فغير مستقرين.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableفرز الإدراج باستخدام البحث الثنائي
تبحث الحلقة الداخلية لفرز الإدراج عن الموضع الصحيح وتزيح العناصر في الوقت نفسه. يمكنك استخدام البحث الثنائي للعثور على الموضع في O(log i) من المقارنات، لكن الإزاحات لا تزال تستغرق O(i) من الوقت، لذلك يبقى التعقيد الإجمالي O(n²). يقلل هذا التحسين عدد المقارنات، وهو مفيد عند استخدام دوال مقارنة مكلفة، لكنه لا يقلل العدد الإجمالي للعمليات. يظهر «فرز الإدراج الثنائي» هذا في Timsort عند التعامل مع أحجام المقاطع الصغيرة.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]فرز الفقاعات مقابل فرز الإدراج: متى تستخدم كلًّا منهما
في المقابلات، اذكر هذه المقارنة بثقة: فرز الإدراج أفضل من فرز الفقاعات بلا استثناء؛ فكلاهما يعمل في O(n²) في أسوأ الحالات وبمساحة O(1)، لكن فرز الإدراج ينفّذ عمليات كتابة أقل، بمقدار O(n+k) حيث k عدد الانعكاسات، مقابل O(n²) لفرز الفقاعات، كما أنه أكثر ملاءمة لذاكرة التخزين المؤقت، وهو الخيار العملي عندما تكون n صغيرة، إذ يستخدمه Timsort. والميزة الحقيقية الوحيدة لفرز الفقاعات هي بساطته التعليمية. وفي بيئات الإنتاج، استخدم دائمًا خوارزمية الفرز المضمّنة في اللغة.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]عدد الانعكاسات كمقياس
يساوي عدد الانعكاسات في المصفوفة عدد الأزواج (i,j) حيث i < j لكن arr[i] > arr[j]. وينفّذ فرز الإدراج عددًا من الإزاحات يساوي تمامًا عدد الانعكاسات، وهي ملاحظة مفيدة. ويتطلب حساب الانعكاسات بكفاءة، في O(n log n)، استخدام نسخة معدّلة من فرز الدمج. ويسأل القائمون بالمقابلات أحيانًا: «إلى أي مدى تراعي خوارزميتك الانعكاسات؟» متابعةً لنقاشات الفرز.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedتحقّق سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep من هذا الدرس.
مراجعة الدرس
تعلّمت في هذا الدرس أن: فرز الفقاعات ينفّذ n-1 مرورًا، يرفع كل منها القيمة العظمى الحالية إلى موضعها النهائي، وله تعقيد O(n²) في أسوأ الحالات، لكنه يحقق O(n) في أفضل الحالات باستخدام راية الإنهاء المبكر، وأن فرز الإدراج يزيح العناصر نحو اليمين لإدراج المفتاح الحالي في الموضع المرتب الصحيح، ويعمل في O(n + inversions)، مما يجعله مثاليًا للبيانات شبه المرتبة، وأن كلتا الخوارزميتين مستقرتان، وتستخدمان O(1) من المساحة، ولهما تعقيد O(n²) في أسوأ الحالات، لكن فرز الإدراج مفضّل بوضوح على فرز الفقاعات في جميع السيناريوهات العملية. بعد ذلك سننفّذ فرز الدمج من الصفر.
الأسئلة الشائعة
هل درس «فرز الفقاعات وفرز الإدراج» مجاني؟
نعم — نص درس «فرز الفقاعات وفرز الإدراج» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «فرز الفقاعات وفرز الإدراج»؟
برمج خوارزميتي الفرز التربيعيتين، وافهم سبب كونهما O(n²)، وتعرّف إلى الحالة الوحيدة التي يتفوق فيها فرز الإدراج على فرز الدمج تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «فرز الفقاعات وفرز الإدراج»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- فرز الفقاعات وفرز الإدراج
- فرز الدمج: قسّم وفرز وادمج
- الفرز السريع واختيار المحور
- فرز بلا مقارنة ودالة sort() في Python