Linked list – sorting by selection

Question:

I'm reproducing a sorting by selection algorithm using linked list.

I'm using two loops using a min cell, i and j, with respect to cell j, ok, but when it's time to change the min pointers and i is not working, when I change the two, i starts the loop in the position that would previously be min, but when I have to make i point again to the previous position and start the loop in what would be the i->prox position, I'm not succeeding without getting lost in the pointers. I've tried auxiliary cells, auxiliary variables, Boolean variables and there was no evolution.

Detail: I can't create auxiliary cell vectors or linked lists.

Code below:

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

struct cel {
    int cont;
    struct cel *prox;
};

typedef struct cel celula;

void insere (int x, celula *p) {

   celula *nova;
   nova = NULL;
   nova = (celula *)malloc (sizeof (celula));
   nova->cont = x;
   nova->prox = p->prox;
   p->prox = nova;
}

void selectsort(celula *p) {
    celula *ai, *i, *aj, *j, *min, *amin, *pmin;
    ai = p;
    i = p->prox;

        while (i != NULL) {
        aj = i;
        j = i->prox;
        min = i;

            while(j != NULL) {

                if (j->cont < min->cont) {
                    amin = aj; min = j, pmin = j->prox;
                }
                aj = j;
                j = j->prox;
            }

        if (i->cont > min->cont) {

            min->prox = i->prox;
            ai->prox = min;
            i->prox = pmin;
            amin->prox = i;

        }
        ai = i;
        i = i->prox;
    }
}

void imprima (celula *p) {
   celula *v;
   for (v = p->prox; v != NULL; v = v->prox)
      printf ("%d ", v->cont);
      printf("\n");
}

int main () {

    celula *l = malloc (sizeof (celula));
    l->prox = NULL;

    insere(7, l);
    insere(11, l);
    insere(8, l);
    insere(4, l);
    insere(12, l);
    insere(9, l);
    insere(1, l);
    imprima(l);
    selectsort(l);
    printf("\n");
    imprima(l);

return 0;

}

Answer:

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

struct cel {
     int cont;
     struct cel *prox;
};

typedef struct cel celula;

celula* insere (int x, celula *p) {

        celula *nova = (celula *)malloc (sizeof (celula));
        nova->cont = x;
        nova->prox = p;
        // necessário retorna o novo endereço do nova cabeça da lista ou da celula nova para a variável 'l'
        return nova;
 }

void selectsort(celula *p) {
     celula *i, *j, *aux;
     aux = (celula *)malloc (sizeof (celula));
     i = p;
     while( i != NULL) {
            j = i->prox;
            while (j != NULL) {
                   if (i->cont > j->cont){
                         //  swap dos ponteiros
                         *aux = *i ; // copia valor de i em aux.
                         *i =  *j; // copia valor de j em i.
                         i->prox = aux->prox; // altera ponterio do próximo de i para que ele continue sendo o mesmo que era antes da copia
                         aux->prox = j->prox; // copia o valor do ponteiro do proximo j
                         *j = *aux; // copia valor de aux em j.
                          j->prox = aux->prox; // altera ponterio do próximo de i para que ele continue sendo o mesmo que era antes da copia
                   }
                   j = j->prox;
            }
      i = i->prox;
    }
}

void imprima (celula *p) {
     celula *v;
     for (v = p; v != NULL; v = v->prox)
         printf ("%d ", v->cont);
         printf("\n");
}      

int main () {
    // lista vazia aponta para um endereço NULO !
    celula *l = NULL;

    // É necessário atualizar o ponteiro 'l' para a nova celula  ou  a cabeça da sua lista !  por isso do 'l = insere( numero, lista);'
    l = insere(7, l);
    l = insere(11, l);
    l = insere(8, l);
    l = insere(4, l);
    l = insere(12, l);
    l = insere(9, l);
    l = insere(1, l);
    imprima(l);
    selectsort(l);
    printf("\n");
    imprima(l);

   return 0;

}

The code is commented out on the errors that occurred.

Scroll to Top