#include <stdio.h>
#include <stdlib.h>

typedef struct element
{
int contenu;
struct element *suivant;
} element;

int main()
{
    printf("\n Seconde solution du tri d'une liste chainee \n");
    printf("   en cas de bug, emailez moi to slarabi@usthb.dz or larabi_s@yahoo.fr \n");
    printf("\n------------ Auteur: S. Larabi --------------------------------------\n");

    element *debut, *nad;
    element *ad;
    debut= (element *) malloc (sizeof(element));
    ad=debut;

    int i, n, val;
    printf("Donnez le nombre d'elements de la liste = ");
    scanf("%d",&n);

    if(n!=0)
    {

    for(i=0; i<n-1; i++)
    {
       printf("Donnez la valeur du prochain element = ");
       scanf("%d",&val);
       ad->contenu=val;
       nad=(element *) malloc (sizeof(element));
       ad->suivant=nad;
       ad=nad;
    }
    printf("Donnez la valeur du dernier element = ");
    scanf("%d",&val);
    ad->contenu=val;
    ad->suivant=NULL;
    }
// Affichage des éléments de la liste

    printf("\n Affichage des elements de la liste \n");
    printf(" ================================== \n");

    ad=debut;
    while(ad->suivant!=NULL)
    {
        printf("Element = %d \n", ad->contenu);
        ad=ad->suivant;
    }
    // affichage du dernier element
    printf("Element = %d \n", ad->contenu);

    // adc pointe l'élément courant, dans lequel on mettra la valeur maximale
    // admax pointe l'élément dont la valeur est maximale, en tenant compte des éléments allant
    // de adc jusqu'à la fin de la liste

    element *adc, *admax, *pad, *padc, *padmax;
    adc=padc=padmax=debut;
    pad=adc;

    while (adc->suivant!=NULL)
    {
        //Mettre le max dans l'adresse adc: adresse courante
        admax=adc;

        // sauvegarde de pad pour la mise à jour de padmax

        ad=adc;
        pad=adc;

        printf("padc= %d \n", padc->contenu);
        printf("adc= %d \n", adc->contenu);

        while (ad!=NULL)
        {
            if (admax->contenu < ad->contenu)
            {
                padmax=pad;
                admax=ad;
            }
            pad=ad;
            ad=ad->suivant;
        }
        // réorganiser le chainage entre adc et admax
        // l'élément adc est précédé par padc et admax par padmax
        if(adc!=admax)
        {
            //mise à jour des chainage: l'élément admax pointera l'élément courant,
            // et l'élément qui précède   admax pointera le suivant de admax

            padmax->suivant=admax->suivant;
            padmax=padc;

            if(adc!=debut)
                {padc->suivant=admax;}
            else
                {debut=admax; padc=debut;}
            admax->suivant=adc;
            adc=admax;
        }
        // Passer à l'élément suivant de la liste

        //Mise à jour de pad et passage au suivant

        padc=adc;
        adc=adc->suivant;

    }
    printf("\n Affichage des elements de la liste apres tri \n");
    printf(" ============================================================================== \n");

    ad=debut;
    if(ad!=NULL)
    {
        while(ad->suivant!=NULL)
            {
            printf("Element = %d \n", ad->contenu);
            ad=ad->suivant;
            }
            // affichage du dernier element
            printf("Element = %d \n", ad->contenu);
    }
    else
    {
        printf("Liste vide \n");
        printf("========== \n");
        printf("+++++++++++++++++   Merci pour votre assiduite  +++++++++++++++++++ \n");
        printf("Source ecrit par S. Larabi \n");


    }

    return 0;
}