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

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2016)
ترتيب بالإدراج لمجموعة اعداد, الخط الافقي هو المؤشر

الترتيب بالإدراج هو الترتيب الأفضل بالنسبة للقوائم الصغيرة ولكنه ليس الأمثل للاستخدام في القوائم الكبيرة.

المبدأ بسيط: هذا الترتيب يتم استعماله من أي شخص يريد مثلا ترتيب ملفاته أو أوراقه، يتم وضع ملف في مكانه ضمن الملفات التي سبق ترتيبها، ثم نمر إلى الملف الموالي.

خصائص[عدل]

  • عدد المفارنات اللازمة من الرتبة .
  • معدل التبديلات من الرتبة .
  • تعقيد الخوارزم:

مثال[عدل]

مثال بسيط لترتيب بالإدراج في 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;
}
خوارزميات الترتيب

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