فرز بالإدراج

// zero or one element in list

if(!pList || !pList->pNext)

} else {

struct LIST * p = head;

من جهة ثانية، // insert current element into proper position in non-empty sorted 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 */

مثال

• مثال بسيط لترتيب قائمة متصلة بالإدراج بلغة C
• struct LIST * SortList1(struct LIST * pList) {
• // zero or one element in list

while(p != NULL) {

current->iValue < p->pNext->iValue) // middle of the list

pList = pList->pNext;

• // insert into the head of the sorted list
• // or as the first element into an empty sorted list
• current->pNext = head;
• head = current;

{

• // 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)

return pList;

/* build up the sorted array from the empty list */

pList = pList->pNext;

/* splice head into sorted list at proper place */

return pList;

• // head is the first element of resulting sorted list
• struct LIST * head = NULL;
• while(pList != NULL) {
• struct LIST * current = pList;

{

• /* no - continue down the list */
• ppTrail = &(*ppTrail)->pNext;
• }
• pHead->pNext = *ppTrail;
• *ppTrail = pHead;
• }
• return pSorted;
• }