المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2016)
ترتيب بالإدراج
Insertion-sort-example-300px.gif
بيانات عامّة
الصنف خوارزمية ترتيب
بنية المعطيات مصفوفة
التعقيد الزمني الأسوأ О(n2) مقارنات وتبديلات
التعقيد الزمني الوسطي О(n2) مقارنات وتبديلات
التعقيد الزمني المثالي O(n) مقارنات و O(1) تبديلات
ترتيب بالإدراج لمجموعة أعداد, الخط الأفقي هو المؤشر

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

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

وبرمجيا، تتطلب الخوارزمية عدد مقارنات من الرتبة ، ومعدل تبديلات من الرتبة ، وتعقيد زمني برتبة .

مثال[عدل]

مثال بسيط لترتيب قائمة متصلة بالإدراج بلغة 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;
}

مراجع[عدل]

  1. ^ Bentley، Jon (2000). Programming Pearls. ACM Press/Addison–Wesley. 


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

بالفقاعات · بالإختيار · بالإدراج · سريع · انتقائي · دمجي