selection sorting of a linked list in c

Question

i am experimenting with different sorting techniques for singly linked lists in C. However i am stuck with a pointer rearrangement approach for a selection sort. This is my code so far

typedef struct node { 
    int data; 
    struct node *next;
} Node;



   void llselectionsort(Node *head) { 
   Node *marker, *cur = NULL, *min;

   for(marker = head; marker != NULL; marker = marker->next){
         min = marker;
         for(cur = marker->next; cur != NULL; cur = cur->next){
            if(cur->data < min->data) {
               min = cur;
            }
     }
     Node *tmp = marker;
     marker = min;
     tmp->next = marker->next;
     min->next = tmp;

}

}

I think i may be using one less pointer than necessary but i am still unsure. Any help would be appreciated thank you.

(note: i know selection sort is considered inefficient, however i would like to understand how to implement it regardless for smaller list sorting)

Answer 1

This is easier to implement if you use double pointers:

NODE * SortList(NODE * pList)
{
NODE **ppNew = &pList;                          /* used to traverse sorted list */
NODE **ppSml;                                   /* ptr to ptr to smallest node */
NODE **ppCur;                                   /* head or previous node */
NODE *pCur;                                     /* current node */
NODE *pTmp;

    if(pList == NULL)                           /* check for NULL list */
        return(pList);
    while((*ppNew)->next != NULL){              /* while not at end list */
        ppSml = ppNew;                          /*   find smallest node */
        ppCur = &((*ppNew)->next);
        while(NULL != (pCur = *ppCur)){
            if(pCur->data < (*ppSml)->data)
                ppSml = ppCur;
            ppCur = &((*ppCur)->next);
        }
/*  for adjacent nodes, 3 pointers are rotated and the order of swaps matters */
        if(*ppNew != *ppSml){                   /* if not the same node */
            pTmp = *ppNew;                      /*     swap node ptrs */
            *ppNew = *ppSml;
            *ppSml = pTmp;
            pTmp = (*ppNew)->next;              /*     swap next ptrs */
            (*ppNew)->next = (*ppSml)->next;
            (*ppSml)->next = pTmp;
        }
        ppNew = &((*ppNew)->next);              /*   advance ppNew */
    }    
    return(pList);
}