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

#define VAL 1000

typedef struct lista Le;

struct lista{
    int x;
    Le *prox;
};

Le *insere(Le* elemento,int dado){
    Le* novo=(Le*)malloc(sizeof(Le));
    novo->x=dado;
    novo->prox=elemento;
    return novo;
}

void imprime(Le* lista){
    Le* p;
    for(p=lista;p!=NULL;p=p->prox){
        printf("Valor = %d\n",p->x);
    }
}

Le* bolha(int n,int *lista){
    int i,fim;
    Le* anterior=NULL;
    Le* atual=lista;
    Le* proximo=atual->prox;

    for(fim=n-1;fim>0;fim--){
        anterior=NULL;
        atual=lista;
        proximo=atual->prox;
        for(i=0;i<fim;i++){
            if(atual->x > proximo->x){
                if (anterior==NULL) lista=proximo;
                atual->prox = proximo->prox;
                proximo->prox = atual;
                if (anterior!=NULL) anterior->prox = proximo;

                anterior = proximo;
                proximo = atual->prox;

            }
            else {
                anterior = atual;
                atual=atual->prox;
                proximo=atual->prox;
            }
        }
    }
    return lista;
}

main(){
    int i;
    Le* elemento;
    elemento=NULL;
    srand(time(NULL));

    for(i=0;i<VAL;i++){
        elemento=insere(elemento,rand()%VAL);
//        elemento=insere(elemento,i);
    }
    imprime(elemento);
    elemento = bolha(VAL,elemento);
    printf("\n\n\n\n\n\n\n\n\n\n\n\nELEMENTOS ORDENADOS:\n\n\n\n\n\n\n\n\n\n\n\n");
    imprime(elemento);
}
