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

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

int main()
{
    printf("\n Premiere 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;
    adc=debut;

    while (adc->suivant!=NULL)
    {
        //Mettre le max dans l'adresse adc: adresse courante
        admax=adc;
        ad=adc;
        while (ad!=NULL)
        {
            if (admax->contenu < ad->contenu)
            {
                admax=ad;
            }
            ad=ad->suivant;
        }
        // permuter entre adc et admax
        int temp;
        if(adc!=admax)
        {
            printf(" permtation entre %d   et    %d  \n", adc->contenu, admax->contenu);
            temp=admax->contenu;
            admax->contenu=adc->contenu;
            adc->contenu=temp;
        }
        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;
}