[SOLUCIONADO] como podria ordenar sin destruir y crear

[eke_ps]

esto es en C
como podria sin destruir o crear nuevos nodos

ordenar una lista enlazada simple?

yo lo e echo guardando valores en una variable comun
pero me dijeron que existe otra manera!!

[gonzo13]

Hola,

Existen una serie de algoritmos que permiten ordenar los elementos de un conjunto, ya sea una tabla o una lista. Los algoritmos básicos son:

• Selección
• Intercambio (método de la burbuja)
• Ordenación
• Quicksort

Puedes encontrar más sobre estos métodos en Internet o en libros de programación, aunque no sea un libro de C/C++, ya que son fácilmente implementables. Te recomiendo que estudies cómo funcionan y los apliques a una tabla primero. Una vez entendido, la implementación en una lista no es complicada.

Un saludo,
gonzo

[vosk]

Puede que el Intercambio (método de la burbuja) sea el mas asequible, consiste en repetir varias ordenaciones donde en cada iteracion comparas un nodo con el siguiente (y los ordenas segun quieras), de forma que en cada pase el ultimo elemento comparado queda ordenado y en el pase siguiente lo omites.

No te pongo el codigo, pero enseguida veras como funciona, supongamos que tienes la lista 37514 y quieres ordenarla de forma creciente:

Código C:

pase 1:
        3 ? 7, 3<7, no hace falta ordenar
        7 ? 5, 7>5, intercambias estos dos, ahora la lista es 35714
        7 ? 1, 7>1, intercambias estos dos, ahora la lista es 35174
        7 ? 4, 7>4, intercambias estos dos, ahora la lista es 35147
final del pase 1, obtienes la lista 35147
final del pase 1, la posicion (tamaño lista - 1) está ordenada correctamente
 
pase 2:
        3 ? 5, 3<5, no hace falta ordenar
        5 ? 1, 5>1, intercambias estos dos, ahora la lista es 31547
        5 ? 4, 5>4, intercambias estos dos, ahora la lista es 31457
final del pase 2, obtienes la lista 31457
final del pase 2, omites la comparacion entre (tamaño lista - 2) y (tamaño lista -1)
final del pase 2, la posicion (tamaño lista - 2) está ordenada correctamente
 
etc...
 

Es decir, en cada pase comparas todos los elementos con el siguiente excepto contra el elemento que quedo ordenado al final del pase anterior, de esta forma si tienes una lista de 5 elementos en el primer pase comparas 5, en el segundo comparas 4, en el tercero 3, etc...

Solo una anotacion: en cualquier caso cuando mueves punteros tienes que controlar los casos de perdida de memoria (o memory leak): se produce cuando pierdes la referencia a una posicion de memoria:

Código C:

int *nodo1 = malloc(sizeof(int));
int *nodo2 = malloc(sizeof(int));
nodo1 = nodo2;//memory leak
 

En este ejemplo estoy perdiendo la referencia a nodo1, de forma que pierdo la capacidad de trabajar con esa direccion de memoria (y el tamaño que ocupa) mientras tenga abierta la aplicacion (los s.o. actuales y no tan actuales liberan la memoria bloqueada por la aplicacion al finalizar la misma aplicacion); en el caso de sizeof(int) bytes perdidos no hay problema, pero imagina que pierdes elementos mas grandes y/o mas numerosos. Cuando hay memoria suficiente la perdida de memoria tal vez sea un problema minimo, pero en caso de listas la perdida de memoria se traduce a la perdida de un elemento por mucha memoria libre que tengas. Para evitarlo copias la direccion del elemento a sobreescribir a un puntero temporal y haces las operaciones:

Código C:

int *nodot = 0;
int *nodo1 = malloc(sizeof(int));
int *nodo2 = malloc(sizeof(int));
 
nodot = nodo1;
nodo1 = nodo2;//no pierdo la referencia a nodo1 porque la tengo en nodot
nodo2 = nodot;//he intercambiado los punteros
 

Saludos
vosk