هذه ثلاث فرز مقارنة بسيطة O(n²). إنها بطيئة على المدخلات الكبيرة لكن سهلة الفهم ومفيدة لتعليم آليات الفرز.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| الفرز | الأفضل | الأسوأ | مستقر | في المكان |
|---|---|---|---|---|
| الفقاعة | O(n) | O(n²) | نعم | نعم |
| الاختيار | O(n²) | O(n²) | لا | نعم |
| الإدراج | O(n) | O(n²) | نعم | نعم |
فرز الإدراج سريع حقًا للمصفوفات الصغيرة أو المرتبة جزئيًا ويُستخدم داخل الفرز الهجين. تجنب جميع الأنواع الثلاثة على البيانات الكبيرة غير المرتبة — استخدم فرز O(n log n) بدلاً من ذلك.
تبني هذه الفرز الحدس حول الثوابت والتبديلات والاستقرار قبل أن تتعامل مع الخوارزميات المتقدمة.
فرز الإدراج بشكل خاص يظهر داخل فرز الإنتاج (مثل Timsort) للمصفوفات الصغيرة جدًا.
معرفة السبب في أنها O(n²) تجعل الانتقال إلى فرز O(n log n) ذا معنى.
مكتبة من أسئلة مقابلات تقنية المعلومات مع إجابات مفصّلة — من المبتدئ إلى المتقدم.
تبرع