خوارزميةمجاني
الترتيب بالإدراج
رتّب المصفوفة بتوسيع جزء مرتّب في بدايتها، عنصراً بعد عنصر.
- الزمن
- O(n²)
- الذاكرة
- O(1)
تتبّعها خطوة بخطوة
الخطوة 1 من 15
1function insertionSort(nums) {2 for (let i = 1; i < nums.length; i++) {3 const key = nums[i];4 let j = i - 1;5 while (j >= 0 && nums[j] > key) {6 nums[j + 1] = nums[j];7 j--;8 }9 nums[j + 1] = key;10 }11 return nums;12}- key
- = 2
- 4
- 2i
- 5
- 1
- 3
نأخذ key = 2. كل ما على يساره مرتّب مسبقاً.
كيف تعمل
خذ العنصر التالي مفتاحاً. أزِح كل عنصر أكبر منه في الجزء المرتّب خانة واحدة إلى اليمين، ثم ضع المفتاح في الفراغ. زمنه تربيعي في أسوأ الحالات، لكنه سريع جداً مع المصفوفات القصيرة أو شبه المرتّبة، ولهذا تستخدمه خوارزميات الترتيب الحقيقية للأجزاء الصغيرة.