Ascending Order in a chained list in c

Question

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

typedef struct LISTA{

int dado;
struct LISTA *prox; 




}lista;

lista *insere(lista *p, int valor){

lista *novo;
novo=(lista*)malloc(sizeof(lista));
novo->dado = valor;
novo->prox = p;
return novo;

 }


void imprime(lista *p){
lista *novo;
for(novo = p; novo!= NULL; novo=novo->prox){
    printf("%d",novo->dado);

}


 }
 lista *ordemCrescente(lista *p){
lista *aux = NULL;
lista *novo = p;


int *recebe;
int x=0;
int menor=0;
while(novo != NULL){
    if(novo->dado < menor){
        aux = novo->prox;
         novo = novo->dado;
         novo->dado = aux; 
    return p;               
    }       

    novo= novo->prox;
}

     }






     main(){

  lista *l,i;
  lista *primeiro, *ultimo;
l = NULL;
l = insere(l, 20);
l = insere(l, 30);
l = insere(l, 40);
l = insere(l, 50);
l = insere(l, 60);


imprime(l);
printf("\n");
l = ordemCrescente(l);
imprime(teste);
  }

Answer 1

First I’ll start with the simplest problems.

• Missed a spot after the %d in function imprime.

• Avoid using l or O as a variable name, because it is very easy to confuse this with the numbers 1 and 0.

• Learn to properly identify your code. Makes your life much easier.

Now let’s go for the hard one. Watch this:

        aux = novo->prox;
        novo = novo->dado;
        novo->dado = aux; 

novo is a pointer. When doing novo->dado, you will pick up an integer and assign it to a pointer (your compiler must be giving you a Warning because of this). With that, novo will become an invalid pointer. When doing novo->dado = aux;, the result is that you will try to access the invalid address and put something there. The result will be a segmentation failure.

The correct way to exchange novo and novo->prox would be so:

        int aux = novo->dado;
        novo->dado = novo->prox->dado;
        novo->prox->dado = aux;

Despite this, the organizational procedure as a whole is totally wrong. The return within it would cause something to be returned in the first "uninversion" of items to be made, and not after all have been made. Even if there was no return, the while traverse each element of the list only once (O(n)), and therefore it is impossible that an approach like this serves to sort the list since the minimum possible complexity is O(n log n). To make matters worse, any approach based on sweeping the list and exchanging neighboring elements will necessarily have minimal performance O(n²).

So there’s nothing in your job ordemCrescente be usable for a good solution. It would have to be redone from scratch.

I suggest studying the existing sorting algorithms to understand how they work and then choosing one of them to implement. Among the ones you can try to implement with linked lists (use two whiles one inside the other to do this), are the Bubble Sort, the Selection Sort and the Insertion Sort. They will all have complexity O(n²) and all of them have as a strategy to exchange neighboring elements several times until the list is ordered.

If you want to go further and look for more efficient sorting algorithms that probably don’t have a way to be implemented with linked lists (at least not efficiently), you can look at the Shell Sort and the Quick Sort, who are still O(n²) in the worst case, are O(n log n) in the average case. Or else look at the Heapsort and the Merge Sort that have complexity O(n log n) in all cases.

As a bonus, there is also the Bogosort which is one of the most inefficient algorithms ever invented. I talk about it here.