Insertion Sort in double-linked circular list

Asked

Viewed 1,369 times

4

I’m having problems with Insertion Sort, it’s probably in the stopping condition, the problem I’m already days with this problem and so far I haven’t been able to leave the place. Could someone give a light? I thank you in advance!

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;
        }
    }
}
c

1 answer

2

Well, you made a mess with pointers and the algorithm, I modified your code and it’s working normally here.

Your if(n) should be a while, since the Insertion Sort performs several exchanges for each element, in this case it is only performing the first exchange.

Also inside the if(n) code is not working. Try not to use ptr->Prox->ant, this confuses a lot, create a new variable that makes the code easier to understand.

I added additional functions to help test the code.

#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;
}

Still missing to put the function listVazia and missing to do functions that clean the memory and call free for all malloc.

Remembering better a free on the main than two flying malloc!

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.