code

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

#define TAM 10

int vet[TAM];

typedef struct elemento { //Estrutura da lista duplamente encadeada
  int valor;
  int refer;
  struct elemento *prox;
  struct elemento *ant;
}Elem;



Elem* cria()                            // Funcao criar alocação/ inicializa a lista
{
    Elem *e;
    e=(Elem*)malloc(sizeof(Elem));      // Espaço é alocado do tamanho de Elem
    e->ant = NULL;
    e->prox = NULL;
    e->refer = 0;
    return e;
}

void inserir(Elem *lista, int valor, int refer)     //Função para inserção de um novo nó com seus devidos parâmetros na lista
{
    Elem *e, *aux;
    e=(Elem*)malloc(sizeof(Elem));
    e->valor = valor;
    e->refer = refer;
    if(lista->prox == NULL)                         // Se a lista não existir, o primeiro elemento criado assumirá as seguintes características:
    {
        e->prox = NULL;
        e->ant = NULL;
        lista->prox = e;
    }
    else                                            // Caso a lista exista, ocorrerá a definição dos parâmetros do novo nó dessa foma:
    {
        aux= lista->prox;
        for(;aux->prox!=NULL; aux=aux->prox);       // Condição executada para poder chegar no último nó da lista.
        e->ant= aux;
        aux->prox = e;
        e->prox= NULL;

    }
}

void impressao(Elem *lista)                         //Função para impressão da lista duplamente encadeada
{
    Elem *p;
    p=lista->prox;
    printf(" Lista \t Posicao\n");
    for(; p!=NULL ; p = p->prox)
        printf("\n %d \t %d ", p->valor, p->refer);
}

void impressaoReverse(Elem *lista)                  //Função para imprimir a lista de trás pra frente
{
    printf("\n\n");
    Elem *p;
    p=lista->prox;
    for(; p->prox!=NULL ; p = p->prox);             // Acha o último nó da lista

    for(; p!= NULL ; p = p->ant)                    // Imprime a partir do último nó em direção ao início
    {
         printf("\n %d", p->valor);
    }

}

void BubbleSort(Elem *lista)                       //Método de ordenação Bubble Sort
{
    Elem *p;
    int j;
    for(j=0;j<TAM;j++)
    {
        p=lista->prox;
         for(; p->prox != NULL;p= p->prox)
        {
            if((p->valor) > (p->prox->valor))
            {
                int a;
                a = p->valor;
                p->valor = p->prox->valor;
                p->prox->valor = a;
            }
        }
    }
}

void InsertionSort(Elem *lista)                           //Método de ordenação Insertion Sort - Em vetor
{
    Elem *p, *pn , *pb;                             // Declaração de ponteiros
    int a_val, a_val2;                              // Parametros para o armazenamento dos valores dos respetivos nós

    p=lista->prox;
    for(; p != NULL ; p=p->prox)                    // Looping com condiçao de parada quando o elemento da lista for nulo
    {
        pn = p;                                     // PN armazena o valor de p no inicio da iteraçao

        if(pn->ant != NULL)                         // Só começarão a ocorrer as trocas se P nao for o primeiro e unico elemento da lista
        {
            pb = p->ant;                            // "pb" recebe o endereço do nó anterior a "p".
            if(pb->valor > pn->valor)               // Se o valor do nó anterior a "p" for maior do que o de "p"
            {
                do                                  // Acontecerá a permutação dos valores
                {
                    a_val = pn->valor;              // a_val recebe o valor do nó de "p"
                    a_val2 = pb->valor;             // a_val2 recebe o valor do nó anterior a "p"
                    pn->valor = a_val2;             // o valor de "pn" é atualizado para o valor maior que estava contido em "pb"
                    pb->valor = a_val;              // o valor de "pb" é atualizado para o valor menor que estava contido em "pn"
                    if(pn->ant !=NULL)              // Garante a execução do metodo varrendo a lista em direção ao inicio para a verificação dos valores
                        pn = pb;
                    if(pb->ant != NULL)
                        pb = pb->ant;

                }while((pb->valor) > (pn->valor));

            }
        }
    }
}

void SelectionSort(Elem *lista)                         //Método de ordenação Selection Sort
{
    int menor=99999;
    Elem *p, *pos, *q;

    q=lista->prox;                                      // "q" recebe o endereço do primeiro elemento da lista
    for(;q!= NULL;q=q->prox)                            // Enquanto q for diferente de NULL, o vetor será percorrido até que chegue no fim ao encontrar NULL.
    {

        for (p=q;p != NULL;p=p->prox)                   // Atribui-se o endereço de "q" a "p", as condições são as mesmas do looping acima
        {
            if (p->valor < menor)                       // Se o valor do nó atual da iteração for menor que o valor atribuído a menor,
            {                                           // a variavel "menor" recebe esse valor
                menor = p->valor;
                pos = p;                                // o endereço do respectivo nó é armazenado na variável "pos"
            }
        }
        pos->valor = q->valor;                          // os valores são trocados, de modo que os menores valores fiquem localizados à partir do inicio da
        q->valor = menor;                               // lista em ordem crescente.
        pos = NULL;                                     // as variaveis sao resetadas para a proxima iteração do método
        menor=99999;
    }

}


void QuickSort(int v[], int inicio , int fim)           //Método de ordenação Quick Sort    que sera escolhido pelo aluno       ESCOLHER (ENTRE SHELLSORT, MERGESORT, QUICKSORT) --->>> QuickSort
{
    int i, j, pivo, aux;
    i= inicio;
    j= fim;
    pivo = v[(inicio + fim)/2];
    while (i <= j)
    {
        while ( v[i] < pivo)
            i= i+1;
        while ( v[j] > pivo)
            j= j-1;
        if( i <= j )
        {
            aux= v[i];//printf("\n\tchegaaaaaquiiiii");
            v[i]=v[j];
            v[j]= aux;
            i= i+1;
            j= j-1;
        }
    }

    if( j > inicio)
        QuickSort(v, inicio, j);
    if( i < fim )
        QuickSort(v, i, fim);

    //////

    int k;

    for(k=0;k<TAM;k++)
        vet[k] = v[k];
}




int main() {

	int i, valor, refer;

    Elem *lista;

    char op;

    lista=cria();                                                 // lista recebe o endereço do espaço alocado pela função cria()

 do {
    //system("cls");
    printf("\n\nEscolha uma opcao\n\n\n");
    printf("1  - Gerar e Inserir na lista Duplamente Encadeada \n");
    printf("2  - Metodo Bolha\n");
    printf("3  - Metodo Selecao\n");
    printf("4  - Metodo Insercao\n");
    printf("5  - Metodo QuickSort\n");
    printf("6  - Sair\n\n\n");
    printf("Opcao: ");
    op = getchar();
    fflush(stdin);
    switch (op) {

    case '1' :  printf("\nSorteando e inserindo numeros...\n\n");
                srand(time(NULL));                               //Inicializa o randomize
                if(lista->prox != NULL)                         // Caso a lista já exista, será apagada e outra vai ser criada.
                {
                    Elem *e, *aux;
                    e=lista->prox;
                    for(;e!= NULL;)
                    {
                       aux=e;
                       e= e->prox;
                       free(aux);
                    }

                }

                for(i = 0; i < TAM; i++)             // Looping usado para atribuir cada valor à lista/vetor.
                {
                    refer = i + 1;
                    valor = (rand()%800)+1;
                    inserir(lista,valor,refer);
                    vet[i]= valor;
                }

                impressao(lista);                      //Função para impressão da lista após ser gerada.

                getch();
                break;

    case '2' :  printf("\nOrdencao Metodo BubbleSort \n\n");

                BubbleSort(lista);                    //Chama metodo de ordenação BOLHA
                impressao(lista);
                getch();
                break;

    case '3' :  printf("\nOrdenacao Metodo SelectionSort \n\n");
                SelectionSort(lista);                  //Chama metodo de ordenação Seleção
                impressao(lista);
                getch();
                break;

    case '4' :  printf("\nOrdenacao Metodo InsertionSort\n\n");

                InsertionSort(lista);                       //Chama metodo de ordenação Inserção no vetor
                impressao(lista);
                getch();
                break;

    case '5' :  printf("\nOrdenacao Metodo QuickSort\n\n");

                QuickSort(vet, 0, TAM-1);               //Chama metodo de ordenação QuickSort no vetor

                int k;
                for(k=0;k<TAM;k++)
                    printf("\n %d", vet[k]);

                getch();
                break;

    case '6' :  break;

    default  :  printf("\nOpcao invalida!\n\n");
                getch();
                    }
  } while (op != '6');

    return 0;
}