ترتيب بالإدراج

ترتيب بالإدراج بيانات عامّة الصنف خوارزمية ترتيب بنية البيانات مصفوفة الأداء أسوء حالة О(n2) مقارنات وتبديلات الحالة المُثلى O(n) مقارنات و O(1) تبديلات الأداء الوسطي О(n2) مقارنات وتبديلات

ترتيب بالإدراج لمجموعة أعداد, الخط الأفقي هو المؤشر

الترتيب بالإدراج (بالإنجليزية: Insertion Sort) هي خوارزمية ترتيب بسيطة مبدأها مشابه لما يستعملهُ أغلب الناس عند ترتيب أوراقهم أو ملفاتهم. وتعمل الخوارزمية بالمرور على البيانات وإدراج كل مدخل في مكانه أولا بأول، ولا تعدّ هذه الطريقة الأفضل بالنسبة للقوائم الكبيرة حيث من يُفضل استخدام خوارزميات متطورة أكثر مثل الترتيب السريع أو الترتيب الدمجي، ولكن للترتيب بالإدراج عدة نقاط إيجابية:

• خوارزمية بسيطة: قام عالم الحاسوب جون بنتلي بتطبيق الخوارزمية في ثلاثة سطور بلغة سي ونسخة محسنة في 5 سطور.
• أكثر كفاءة للمصفوفات الصغيرة جداً كغيرها من الخوارزمات الرباعية.
• كفاءة أعلى عند التطبيق من أغلب خوارزمات الترتيب التربيعية البسيطة مثل الترتيب بالاختيار أو الترتيب بالفقاعات.
• متأقلمة الأداء: إذ تتحسن كفاءتها كلما كانت المصفوفة مرتبة أكثر، وينخفض التعقيد الزمني للترتيب إلى O(nk) في مصفوفة لا يبعد أي مدخل أكثر من k خانة عن مكانها المرتب.
• الثبات: لا يغير الترتيب النسبي للمدخلات ذات مفاتيح متساوية.
• في المكان: يحتاج فقط إلى O(1) ذاكرة اضافية.
• فورية: أي أنها تستطيع ترتيب المعلومات أثناء تلقيها بدل الانتظار حتى تلقي المصفوفة الكاملة.

وبرمجياً، تتطلب الخوارزمية عدد مقارنات من الرتبة $\frac{n^2}{4}$، ومعدل تبديلات من الرتبة $\frac{n^2}{2}$، وتعقيد زمني برتبة $\mathcal{O}(n^2)$.

مثال

مثال بسيط لترتيب قائمة متصلة بالإدراج بلغة C

struct LIST * SortList1(struct LIST * pList) {
    // zero or one element in list
    if(pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while(pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if(head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while(p != NULL) {
                if(p->pNext == NULL || // last element of the sorted list
                   current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if(!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL)
  {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) /* does head belong here? */
      {
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}