quick sort

je voulais savoir comment utiliser quick sort pour trier une liste chainee pouvez vous me donner le code en c ?

Je crois que le quicksort à besoin d'un accès indexé aux éléments. Dans ce cas, c'est pas du tout adapté aux listes chainées.

_____________________________________
Un éditeur de ressources gratuit pour Windows

salut,

le pire c'est ce que je croyait jusqu'à ce que je tombe sur un article qui parlait des listes chainées dans la glib...et en fait on peut faire du quicksort sur une liste chainéé...niveau perf ca doit pas forcément être nickel...mais bon : voici un code que j'ai fait pendant un cours de C...

note : ce code reproduit à peut près les list_head doublement chainées du noyau linux...très astucieux dans le principe : un inclu dans la liste dans les données et non les données dans la liste...

désolé pour la longueur que ca va donner :
dans main.c :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "list_head.h"

struct test {
    int az;
    double er;
    char m;

    LIST_ENTRY(l);
};
LIST_HEAD(test);

int compare(struct list_entry * e1,struct list_entry * e2)
{
    struct test *t1 = LIST_GET(e1,test,l);
    struct test *t2 = LIST_GET(e2,test,l);

    return (t1->m > t2->m ? 1 : -1);
}

int main()
{
    struct list_entry *p;
    struct list_entry *p2;
    struct test *t;
    int i;

    LIST_INIT(b);

    for (i = 0;i < 15;i++)
    {
        int j = rand() % 15;
        t = (struct test *)malloc(1 * sizeof(struct test));
        t->az = j;
        t->er = j;
        t->m = 'a'+j;
        LIST_INSERT_FIRST(b,t,test,l);
    }

    LIST_REMOVE_FIRST(b);

    p = b.first;
    while (p)
    {
        struct test *tp = LIST_GET(p,test,l);
        printf("%d %lf %c\n",tp->az,tp->er,tp->m);
        p2 = p;
        p=p->next;
    }

    printf("---\n");

    b.first = list_head_sort(b.first,compare);

    p = b.first;
    while (p)
    {
        struct test *tp = LIST_GET(p,test,l);
        printf("%d %lf %c\n",tp->az,tp->er,tp->m);
        p2 = p;
        p=p->next;
    }

    printf("---\n");

    while (p2)
    {
        struct test *tp = LIST_GET(p2,test,l);
        printf("%d %lf %c\n",tp->az,tp->er,tp->m);
        p2=p2->prev;
    }
    system("pause");
}

dans list_head.h :
#ifndef _LIST_HEAD_H_
#define _LIST_HEAD_H_

//store the needed element to be a double-linked list
struct list_entry {
    struct list_entry *next;
    struct list_entry *prev;
};

//get the offset of the member m in the struct t
#define OFFSET(t,m) (int)&(((struct t *)0)->m)
//get the offset of the member m in the struct pointed by p
#define OFFSET2(p,m) (int)((int)&((p)->m)-(int)(p))
//get the pointer to the beginning of the struct t given a pointer p to the member m
#define BASE_OF(p,t,m) (struct t *)((unsigned char *)p - OFFSET(t,m))

//declare a member m to make a struct a linked list with list_head
#define LIST_ENTRY(m) \
    struct list_entry m

//insert at the beginning of h, the element pointed by p of type t* which contains a member m of type struct list_entry
#define LIST_INSERT_FIRST(h,p,t,m) \
    (p)->m.prev = 0; \
    (p)->m.next = h.first; \
    (h).first = (struct list_entry *)((unsigned char*)(p)+OFFSET(t,m)); \
    if ((p)->m.next) \
        ((p)->m.next)->prev = h.first;

//insert element pointed by p after element pointed by p2 given the member m is the list_entry struct
#define LIST_INSERT_AFTER(p,p2,m) \
    (p)->m.prev = &((p2)->m); \
    (p)->m.next = (p2)->m.next; \
    (p2)->m.next = &((p)->m); \
    if ((p)->next) \
        (p)->next->prev = &((p)->m)

//insert element pointed by p before element pointed by p2 given the member m is the list_entry struct
#define LIST_INSERT_BEFORE(p,p2,m) \
    (p)->m.prev = (p2)->m.prev; \
    (p)->m.next = &((p2)->m); \
    (p2)->m.prev = &((p)->m); \
    if ((p)->prev) \
        (p)->prev->next = &((p)->m)

//remove element p given the member m is the list_entry struct
#define LIST_REMOVE(p,m) \
    if ((p)->m.prev) \
        (p)->m.prev->next = (p)->m.next; \
    if ((p)->m.next) \
        (p)->m.next->prev = (p)->m.prev; \

//remove the first element of h given the member m is the list_entry struct
#define LIST_REMOVE_FIRST(h) \
    if (h.first->next) \
        h.first->next->prev = 0; \
    h.first = h.first->next

//declare the list head struct whose first points to the first element of the list
#define LIST_HEAD() \
    struct list_head { \
        struct list_entry *first; \
    }

//init a variable b to be a list_head
#define LIST_INIT(b) \
    struct list_head b; b.first = 0

//get the pointer to the beginning of the struct t (data) given a pointer p to the member m
#define LIST_GET(p,t,m) \
    BASE_OF(p,t,m)

/*
* sort the list list with help of compare function
* list : list to sort
* compare : compare function to compare to element of list
* return a pointer to the first element in sorted list (so to the sorted list)
*/
struct list_entry *list_head_sort(struct list_entry *list,int(*compare)(struct list_entry *,struct list_entry *));

#endif

dans un list_head.c :
#include "list_head.h"

/*
* take two lists l1 and l2 and sort/merge them with the compare function compare
* l1, l2 : list to sort/merge
* compare : compare function to compare to elements
*/
static struct list_entry *list_head_sort_merge(struct list_entry *l1,struct list_entry *l2,int(*compare)(struct list_entry *,struct list_entry *))
{
    //l is used to insert elements at the end of the result list
    //ret is the beginning of the return list
    struct list_entry *l = 0,*ret = 0;
    //e is the element to insert to the result list
    struct list_entry *e = 0;

    //if no list to merge : return an empty list
    if (!l1 && !l2)
        return 0;

    //as long as we have an element in one of the lists
    while (l1 && l2)
    {
        //compare the current element of each list
        if (compare(l1,l2) > 0)
        {
            //element in l1 is greater than element in l2
            //so process l2
            e = l2;
            //pass to the next element of l2 since we will remove the current
            l2 = l2->next;
        }
        else
        {
            //element in l2 is greater than element in l1
            //so process l1
            e = l1;
            //pass to the next element of l1 since we will remove the current
            l1 = l1->next;
        }

        //if the result list is currently not empty
        if (l)
            //add the selected element at the end
            l->next = e;
        //else, e is the first element of the result list, so save it in the return value
        else
            ret = e;
       
        //the previous element of the new last is the current end of the result list
        e->prev = l;
        //the next element of the new last does not exist
        e->next = 0;
        //the new current end element of result list is the last selected element
        l = e;
    }

    //if there is elements yet in l1
    if (l1)
    {
        //append it to the end of the result list

        //if the result list is currently not empty
        if (l)
            //add l1 at the end
            l->next = l1;
        //else, l1 is the result list, so save it in the return value
        else
            ret = l1;
       
        //link the rest list to the end of result list
        l1->prev = l;
    }
    //if there is elements yet in l2
    else
    {
        //append it to the end of the result list

        //if the result list is currently not empty
        if (l)
            //add l2 at the end
            l->next = l2;
        //else, l2 is the result list, so save it in the return value
        else
            ret = l2;
       
        //link the rest list to the end of result list
        l2->prev = l;
    }

    return ret;
}

/*
* sort the list list with help of compare function
* list : list to sort
* compare : compare function to compare to element of list
* return a pointer to the first element in sorted list (so to the sorted list)
*/
struct list_entry *list_head_sort(struct list_entry *list,int(*compare)(struct list_entry *,struct list_entry *))
{
    //if we have a list to sort
    if (list)
    {
        //l1 : points to the middle of the list (skip one element at a time)
        //l2 : points to the end of the list (skip two elements at a time)
        struct list_entry *l1 = list,*l2 = l1->next;

        //as long as we are not at list end
        while (l2)
        {
            //l1 skip one element
            l1 = l1->next;
            //l2 skip two elements
            l2 = l2->next;
            l2 = (l2 ? l2->next : 0);
        }

        //split the two parts of the list (middle is pointed by l1)
        if (l1->prev)
            l1->prev->next = 0;
        l1->prev = 0;

        //if we have not only one element in list
        if (l1 != list)
            //process recursively the both part of list to sort locally
            return list_head_sort_merge(list_head_sort(list,compare),list_head_sort(l1,compare),compare);
        else
            //else return the one cell list
            return list;
    }
    else
        return 0;
}

bonne prog

ShareVB

Evidemment on peut le faire (quitte à transormer la liste en tableau, trier le tableau et transormer le tableau en liste, c'est sans doute encore plus rapide comme ça). Mais le tri n'est plus très 'quick' avec les listes chainées

_____________________________________
Un éditeur de ressources gratuit pour Windows

salut,

non, non le code ci dessus fait du quick sort sans passer par un tableau...et je pense qui s'ils font cela dans la glib alors ca doit quand même être relativement efficace...

ShareVB