4

Estou com problemas no insertion sort, provavelmente é na condição de parada, o problema que já estou a dias com este problema e até agora não consegui sair do lugar. Alguém poderia dar uma luz? Desde já agradeço!

void ordena(Lista *p_l){ //insertion sort

int n;
No_lista *cur, *ptr, *tmp;
if(listaVazia(p_l)) return;
cur = *p_l;
cur = cur->prox;
while(cur!=*p_l){
    n=0;
    ptr=cur;
    tmp=cur->ant;
    cur=cur->prox;
    while (tmp!=*p_l && tmp->info > ptr->info){
        n++;
        tmp=tmp->ant;
    }
    if (n){
        ptr->ant->prox=ptr->prox;
        if (ptr->prox!=*p_l)
            ptr->prox->ant=ptr->ant;
        if (tmp==*p_l){
            tmp=*p_l;
            ptr->ant=*p_l;
            ptr->prox=tmp;
            ptr->prox->ant=ptr;
            *p_l=ptr;
        }
        else{
            tmp=tmp->prox;
            tmp->ant->prox=ptr;
            ptr->ant=tmp->ant;
            tmp->ant=ptr;
            ptr->prox=tmp;
        }
    }
}

1 Resposta 1

2

Bom, você fez uma confusão com ponteiros e com o algoritmo, modifiquei o seu código e está funcionando normalmente aqui.

O seu if(n) deveria ser um while, já que o insertion sort realiza várias trocas para cada elemento, neste caso só está realizando a primeira troca.

Além disso dentro do if(n) o código não está fucionando. Tente não usar ptr->prox->ant, isso confunde muito, crie uma nova variável que assim o código fica mais fácil de entender.

Coloquei funções adicionais para ajudar a testar o código.

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

typedef struct No_lista{
    struct No_lista *ant;
    struct No_lista *prox;
    int info;
} No_lista;

typedef No_lista* Lista;

void adicionar(int parametro, Lista *inicial){
    if(*inicial == 0 ){
        (*inicial) = malloc(sizeof(No_lista));
        (*inicial)->ant = *inicial;
        (*inicial)->prox = *inicial;
        (*inicial)->info = parametro;
    }else{
        No_lista *aux, *ultimo;
        aux = *inicial;
        while(aux->prox != *inicial)
            aux = aux->prox;
        aux->prox = malloc(sizeof(No_lista));
        ultimo = aux->prox;
        ultimo->ant = aux;
        ultimo->prox = *inicial;
        ultimo->info = parametro;
        (*inicial)->ant = ultimo;
    }
}

void printLista(Lista *inicial){
    No_lista *aux;
    aux = *inicial;
    printf("Imprimindo lista:\n");
    do{
        printf("%d ", aux->info);
        aux = aux->prox;
    }while(aux != *inicial);
    printf("\n");
}

void ordena(Lista *p_l){ //insertion sort
    No_lista *cur, *ptr, *tmp, *aux, *aux_ant, *aux_prox;
//  if(listaVazia(p_l))
//      return;

    cur = *p_l;
    cur = cur->prox;

    // Tratando para o caso da lista com 2 elementos
    if( cur->prox == *p_l){
        if( (*p_l)->info > cur->info)
            (*p_l) = (*p_l)->prox;
        return;
    }

    while(cur!=*p_l){
        ptr=cur;
        tmp=cur->ant;
        cur=cur->prox;

        while (tmp->prox != *p_l && tmp->info > ptr->info){
            aux_ant = tmp->ant;
            aux_prox = ptr->prox;

            aux_ant->prox = ptr;
            ptr->prox = tmp;
            tmp->prox = aux_prox;
            aux_prox->ant = tmp;
            tmp->ant = ptr;
            ptr->ant = aux_ant;

            tmp = ptr;
            ptr = tmp->prox;

            if(ptr==*p_l)
                *p_l = tmp;

            tmp=tmp->ant;
            ptr = ptr->ant;
        }
    }
}

int main()
{
    Lista *li, p = NULL;
    li = &p;

    adicionar(4, li);
    adicionar(1, li);
    adicionar(7, li);
    adicionar(5, li);
    adicionar(2, li);

    printLista(li);
    ordena(li);
    printLista(li);

   // scanf("%*c");
    return 0;
}    

Ainda falta colocar a função listaVazia e falta fazer funções que limpem a memória e chamem free para todos os malloc.

Lembrando mais vale um free na main do que dois malloc voando!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .