CODEWITHSUNDEEP
cpointersstruct
Digihash
Digihash

Reputation: 375

How does this sorting method work?

I'm learning C from "The C Book". I think it's a good book and I understand most of it, like pointers. But I can't get my head around 1 example of sorting with linked list structures.

If I draw it on paper, I keep getting that the pointers of the second object aren't adjusted to the first if they are switched. Maybe I'm thinking in a wrong way about these pointers in the structures. Can somebody explain this exchange very short, maybe by example like I made in the code with 5, 99 and 1. I'd like to understand this kind of sorting with linked list because it seems pretty useful for later.

This is the code: #include #include 

struct list_ele{
    int data;
    struct list_ele *pointer;
}ar[3];

struct list_ele *
sortfun( struct list_ele *list );

int
main(){
    struct list_ele *lp;

    ar[0].data = 5;
    ar[0].pointer = &ar[1];
    ar[1].data = 99;
    ar[1].pointer = &ar[2];
    ar[2].data = 1;
    ar[2].pointer = 0;/* mark end of list */

    /* sort list */
    lp = sortfun(ar);
    /* follow pointers */
    while(lp){
        printf("contents %d\n", lp->data);
        lp = lp->pointer;
    }
    exit(EXIT_SUCCESS);
}

struct list_ele *
sortfun( struct list_ele *list )
{
    int exchange;
    struct list_ele *nextp, *thisp, dummy;

    /*
     * Algorithm is this:
     * Repeatedly scan list.
     * If two list items are out of order,
     * link them in the other way round.
     * Stop if a full pass is made and no
     * exchanges are required.
     * The whole business is confused by
     * working one element behind the
     * first one of interest.
     * This is because of the simple mechanics of
     * linking and unlinking elements.
     */

    dummy.pointer = list;
    do{
        exchange = 0;
        thisp = &dummy;     
            while( (nextp = thisp->pointer) && nextp->pointer) {
                if(nextp->data > nextp->pointer->data){
                    /* exchange */
                    exchange = 1;
                    thisp->pointer = nextp->pointer;
                    nextp->pointer = this->pointer->pointer;
                    thisp->pointer = nextp;
                }
            thisp = thisp->pointer;
        }
    }while(exchange);

    return(dummy.pointer);
}

Upvotes: 0

Views: 79

Answers (1)

Felice Pollano
Felice Pollano

Reputation: 33262

This is bubble sort. It works by exchanging items out of order, repeating until there is no more items out of order. It is helpful if there is not so much items, otherwise some other methods are required. The tricki part is probably this:

                thisp->pointer = nextp->pointer;
                nextp->pointer = this->pointer->pointer;
                thisp->pointer = nextp;

that is meant to swap the order of two element in the linked list.

Upvotes: 1

Related Questions