Sorting an unordered list does not work

Question

The code works until the part I have ordered a list already created using a new list, only I can not identify the error. That’s when I created the functions Ordain and Addordenado that started to go wrong.

OBS:I asked to print the new list on itself Ordain to be able to test, then I would move on to the main, only that not even this is working.

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

typedef struct Elemento{
  int valor;
  struct Elemento*prox;
}Elemento;

typedef struct Lista{
  Elemento*Inicio;
  Elemento*Fim;
}Lista;

Lista*CriandoLista(){
  Lista*lista=(Lista*)malloc(sizeof(Lista));
  lista->Inicio=NULL;
  lista->Fim=NULL;
  return lista;
}

Elemento*CriandoElemento(int n){
  Elemento*novo=(Elemento*)malloc(sizeof(Elemento));
  novo->prox=NULL;
  novo->valor=n;
  return novo;
}

void AddLista(Lista*lista,Elemento*novo){
  if(lista->Inicio==NULL){
      lista->Inicio=novo;
      lista->Fim=lista->Inicio;
  }else{
      lista->Fim->prox=novo;
      lista->Fim=novo;
  }
}

void Imprimir(Lista*lista){
  Elemento*aux=lista->Inicio;
  while(aux!=NULL){
      printf(" %d ",aux->valor);
      aux=aux->prox;
  }
}

void AddOrdenado(Lista*lista,Lista*nvlista){
  Lista*aux=lista;
  Lista*aux2=nvlista;
  if(nvlista->Inicio==NULL){
      nvlista->Inicio=lista->Inicio;
      nvlista->Fim=lista->Inicio;
      lista->Inicio=lista->Inicio->prox;
      nvlista->Inicio->prox=NULL;

  }else{
      if((nvlista->Inicio->valor)<(lista->Inicio->valor)){
          nvlista->Inicio=lista->Inicio;
          lista->Inicio=lista->Inicio->prox;
          nvlista->Inicio->prox=aux2->Inicio;
      }else if((nvlista->Fim->valor)>(lista->Inicio->valor)){
          aux2->Fim->prox=lista->Inicio;
          nvlista->Fim=aux2->Fim;
          lista->Inicio=lista->Inicio->prox;
          nvlista->Fim->prox=NULL;
      }else{
          while(aux2!=NULL){
              if((lista->Inicio->valor)>(aux2->Inicio->prox->valor)){
                  lista->Inicio->prox=aux2->Inicio->prox;
                  aux2->Inicio->prox=lista->Inicio;
                  lista->Inicio=aux->Inicio->prox;
              }
              aux2->Inicio=aux2->Inicio->prox;
          }
      }
  }
}
void Ordenar(Lista*lista){
  Lista*nvlista=CriandoLista();
  while(lista->Inicio!=NULL){
      AddOrdenado(lista,nvlista);
  }
  Imprimir(nvlista);
}

int main(){
  Lista*lista=CriandoLista();
  int n[]={5,10,9};
  for(int i=0;i!=sizeof(n)/sizeof(int);i++){
    AddLista(lista,CriandoElemento(n[i]));
  }
  Imprimir(lista);
  Ordenar(lista);
}

Answer 1

There’s a lot of things you need to get right for the addition to work.

• Its function Ordenar doesn’t even advance through us:

  Lista*nvlista=CriandoLista();
  while(lista->Inicio!=NULL){
      AddOrdenado(lista,nvlista);
  }
  

  Notice that there is none x = x->prox;, so this is for all intents and purposes a while infinite, which is actually the problem you see directly on the console, because it does not end.

  But even in this function has another problem that is more subtle and more complicated to solve. This is the change of ->prox elements from the old list. If you are adding elements from the old list to the new one and exchange the ->prox the old list no longer works because there are no longer the connections that should. You can easily solve this problem by adding a copy of the node you are going to so as not to invalidate the old list. That said, you can rewrite your function as follows:

  void Ordenar(Lista *lista) {
      Lista *nvlista=CriandoLista();
      Elemento *no_atual = lista->Inicio; //elemento para navegar na lista
      while(no_atual != NULL) {
          Elemento *novo = CriandoElemento(no_atual->valor); //adicionar uma cópia
          AddOrdenado(nvlista, novo);
          no_atual = no_atual->prox; //avançar para o proximo, que faltava
      }
      Imprimir(nvlista);
  }
  

• In the AddOrdenado has a much more complex logic than necessary and does not even cover all the particular cases that exist. I suggest another approach to navigate the knots while they are smaller than the knot to insert, and stop at the first major knot. The insertion should then be done at the node prior to what stopped. Naturally you have to consider particular cases of empty list, or node larger/smaller than all.

  Following this logic could do so:

  void AddOrdenado(Lista *nvlista, Elemento *elemento) {
      if (nvlista->Inicio == NULL){ //se lista vazia
          nvlista->Inicio = nvlista->Fim = elemento;
          return;
      }
  
      Elemento *atual = nvlista->Inicio;
      Elemento *anterior = NULL; 
      while (atual != NULL && atual->valor < elemento->valor){ //navegar enquanto menor
          anterior = atual;
          atual = atual->prox;
      }
  
      if (atual == NULL){ //novo maior que todos
          nvlista->Fim->prox = elemento;
          nvlista->Fim = elemento;
      }
      else {
          if (anterior == NULL){ //novo menor que todos
              elemento->prox = nvlista->Inicio;
              nvlista->Inicio = elemento;
          }
          else {
              elemento->prox = anterior->prox;
              anterior->prox = elemento;
          }
      }
  }
  

See the program with these changes working correctly

Just a small note regarding writing, avoid writing something like Lista*nvlista all together because it gets harder to read, and it might even give you the idea that it’s a multiplication. Choose to separate with space as is default by writing for example Lista *nvlista.