[ Foro de Pascal ]

Algoritmo sobre ordenamiento de listas enlazadas simples.

06-Oct-2012 02:51
Luis Torres (+12)
5 Respuestas

Un gran saludo a todos. Estoy aquí porque necesito el algoritmo de ordenamiento por burbuja (iterativo) para ordenar una lista enlazada simple de enteros. Si alguien aquí me lo puede facilitar estaría muy agradecido, lo necesito para poder hacer unos ejercicios.


07-Oct-2012 09:47
Nacho Cabanes (+31)

Lo puedes encontrar en muchos sitios, por ejemplo en la propia Wikipedia, ya sea en castellano:

http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

o, más detallado, en inglés:

http://en.wikipedia.org/wiki/Bubble_sort

Pero recuerda, que una ordenación de burbuja es razonable para un array, pero en una lista enlazada es menos costoso ordenar a medida que se introducen los datos.


08-Oct-2012 03:05
Luis Torres (+12)

Gracias por su respuesta pronta. Yo conozco el método de ordenamiento por burbuja, pero no sabría llevarlo a cabo en una lista enlazada. Entiendo eso de que sería mejor haber insertado cada elemento en orden, pero, ¿qué hay si la lista ya está conformada y está desordenada?, ¿cómo haría para ordenarla con este método?. Un gran saludos, profesor.


12-Oct-2012 17:28
Nacho Cabanes (+31)

A ver... es que no es aplicable directamente: en una lista enlazada no existe un contador de cantidad de elementos (al menos no "por definición", aunque lo puedas crear como ampliación), de modo que el típico "for" que se usa para recorrer al ordenador por burbuja dea de perder sentido.

Además, debes mirar el valor del siguiente elemento e intercambiar con él, y eso es algo que tampoco tiene mucho sentido en una lista, porque no puedes mirar hacia atrás, sólo hacia delante (salvo que sea una lista doble), además de que no deberías intercambiar todos los datos, sino sólo los enlaces...

El concepto se parece, pero sólo se parece. Son cosas distintas, que deberás atacar de forma distinta. Es como si me dices "como entre dos motos tienen cuatro ruedas, quiero guardar todas estas bolsas en su  maletero..."  El que tengan 2+2 ruedas no las convierte en coche, no existe maletero y podrías llegar a imitar uno, pero sería innecesariamente trabajoso.  De forma similar, en el caso de este ejercicio, aunque una lista guarde datos, y se pueda acceder a ellos, el método de burbuja no es la forma "natural" de ordenar para datos a los que no puedas acceder mediante posición. Lo podrías llegar a conseguir, pero complicando innecesariamente el problema. Es mucho más simple y más natural generar una nueva lista en la que ordenes a medida que vas insertando los datos.


13-Oct-2012 03:13
Luis Torres (+12)

O sea que si tengo una lista enlazada simple desordenada, ¿sería descabellado que me pidieran que la ordenara?.
Saludos y, muchas gracias por su respuesta.


14-Oct-2012 01:06
Nacho Cabanes (+31)

Desde mi punto de vista como profesor, sería poco razonable (casi diría que "antipedagógico") que te pidieran ordenarla mediante burbuja (o quicksort, o selección directa, o inserción directa, o cualquier otro modo de ordenación que esté diseñado para arrays).

Es razonable que te pidan ordenarla, pero usando métodos adecuados para estructuras dinámicas (habitualmente, volcando a una nueva lista que sí esté ordenada).






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)