Como ya tenemos las rutinas de manejo de las listas enlazadas con sus elementos ordenados, la voy a usar como algoritmo de ordenación general, simplemente tomo los algoritmos de lista enlazada y los simplifico al máximo, creo la lista con tamaño exacto para los elementos a ordenar, la relleno, y luego la recorro modificando el arreglo original, y al final resultando un algoritmo muy sencillo, aunque para ordenar una lista necesita otras dos adicionales, por lo que gasta bastante más memoria.
ALGORITMO Insercion_lista (arreglo, primero, ultimo)
raiz ← null
tamaño ← ultimo - primero + 1
CREAR_ARREGLO Datos(tamaño)
CREAR_ARREGLO Enlaces(tamaño)
BUCLE i DESDE primero HASTA ultimo
LISTA_ORDENADA_INSERTAR(arreglo(i), Datos, Enlaces, raiz)
FIN BUCLE
pos ← raiz
BUCLE i DESDE primero HASTA ultimo
arreglo(nro) ← Datos(pos)
pos ← Enlaces(pos)
FIN BUCLE
ALGORITMO LISTA_ORDENADA_INSERTAR (valor, ListaDatos, ListaNodos, NodoRaiz)
// Busco un nodo libre
nro ← BUSCAR_ELEMENTO_LIBRE
SI nro = NULL ENTONCES
ERROR No hay espacio libre
SALIR DEL ALGORITMO
FIN SI
// Ubico el elemento
ListaDatos(nro) = Valor
// Si es el primer nodo lo ubico en la raiz
SI (NodoRaiz ES NULO) ENTONCES
ListaNodos(nro) ← NULL
NodoRaiz ← nro
FIN SI
// Si no es el primero buscamos su posición
SI (NodoRaiz NOES NULO) ENTONCES
pos ← NodoRaiz // Nodo por el que vamos
ant ← NULL // Nodo anterior al que vamos
REPETIR
encontrado ← Falso
// Si he encontrado un elemento mayor o igual, debo ubicarlo antes
SI (ListaDatos(pos) ≥ Valor) ENTONCES
// Si es el primer elemento, hay que ubicarlo en la raiz
SI (ant ES NULO) ENTONCES
ListaNodos(nro) ← NodoRaiz
NodoRaiz ← nro
encontrado ← Cierto
FIN SI
// Si no es el primer elemento, hay que ubicarlo tras el anterior
SI (ant NOES NULO) ENTONCES
ListaNodos(nro) ← ListaNodos(ant)
ListaNodos(ant) ← nro
encontrado ← Cierto
FIN SI
FIN SI
// Si se ha llegado al final se pone el último
SI (ListaNodos(pos) ES NULO) ENTONCES
ListaNodos(pos) ← nro
ListaNodos(nro) ← NULL
encontrado ← Cierto
END IF
//No encontrado seguimos iterando
SI (NO encontrado) ENTONCES
ant ← pos
pos ← ListaNodos(pos)
FIN SI
HASTA QUE (encontrado)
FIN SI
Aquí el programa completo en SuperBASIC correspondiente, son las rutinas desarrolladas en el manejo de listas pero simplificadas al máximo dejando solo lo necesario. Para gastar un poco menos de memoria y optimizar algo las velocidades (aunque en SuperBASIC la velocidad no se nota por su forma de trabajar), habría que hacer que la lista de punteros sea de enteros en lugar de reales. De momento no lo voy a hacer así.
20000 REMark --------------------------------------------- 20010 REMark -- ALGORITMOS DE ORDENACION -- 20020 REMark -- Modulo....: Insercion con lista -- 20030 REMark -- Objetivo..: Ordena un arreglo usando -- 20040 REMark -- enlazada -- 20050 REMark -- Autor.....: javu61, 12/2016 -- 20060 REMark -- Parametros: -- 20070 REMark -- arreglo -- Arreglo a ordenar -- 20080 REMark -- sentido -- FALSO = Ascendente -- 20090 REMark -- primero -- primer elemento -- 20100 REMark -- ultimo -- ultimo elemento -- 20110 REMark -- Si ultimo=0 -- Todos -- 20120 REMark --------------------------------------------- 20130 DEFine PROCedure Insercion_Lista (arreglo,sentido,primero,ultimo) 20140 LOCal pos,nro 20150 : 20160 IF ultimo = 0 THEN ultimo=DIMN(arreglo) 20170 : 20180 REMark Crear los elementos de la lista 20190 LET L_NULO = -1 : REMark Puntero nulo 20200 LET L_RAIZ = L_NULO : REMark Puntero al nodo raiz 20210 DIM ArrPuntero(ultimo-primero) : REMark Puntero siguiente elemento 20220 DIM ArrLista(ultimo-primero) : REMark Elementos de la lista 20230 : 20240 REMark Rellenar la lista 20250 FOR pos = primero TO ultimo : LISTA_ADD pos,arreglo(pos),sentido 20260 : 20270 REMark A partir de la lista montar el arreglo ordenado 20290 FOR nro=primero TO ultimo 20300 MUEVE ArrLista(L_RAIZ), arreglo(nro) 20310 L_RAIZ= ArrPuntero(L_RAIZ) 20320 END FOR nro 20330 END DEFine 20340 : 20350 REMark ------------------------------------------------------------- 20360 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista -- 20370 REMark ------------------------------------------------------------- 20380 DEFine PROCedure LISTA_ADD(nro,dato,sentido) 20390 LOCal repetir,pos,ant 20400 : 20410 REMark Ubico el elemento 20420 ArrLista(nro) = dato 20430 : 20440 REMark Si es el primer nodo, lo ubico en la raiz 20450 IF L_RAIZ = L_NULO THEN 20460 ArrPuntero(nro) = L_NULO 20470 L_RAIZ = nro 20480 ELSE 20490 REMark Si no es el primero, buscamos su posición recorriendo 20500 pos = L_RAIZ 20510 ant = L_NULO 20520 REPeat repetir 20530 REMark Si he econtrado su posición 20540 IF COMPARA(ArrLista(pos), dato, sentido) >= 0 THEN 20550 REMark Segun sea ahora el primer elemento o no 20560 IF ant = L_NULO THEN 20570 ArrPuntero(nro) = L_RAIZ 20580 L_RAIZ = nro 20590 ELSE 20600 ArrPuntero(nro) = ArrPuntero(ant) 20610 ArrPuntero(ant) = nro 20620 END IF 20630 EXIT repetir 20640 END IF 20650 REMark Si he llegado al final, lo añado como utimo elemento 20660 IF ArrPuntero(pos)=L_NULO THEN 20670 ArrPuntero(pos) = nro 20680 ArrPuntero(nro) = L_NULO 20690 EXIT repetir 20700 END IF 20710 ant = pos 20720 pos = ArrPuntero(pos) 20730 END REPeat repetir 20740 END IF 20750 END DEFine 20760 : 20770 :
Las pruebas de las rutinas de ordenación por inserción desarrolladas hasta el momento dan el siguiente resultado con 50 elementos, vemos que Shell es el mas rápido en el caso medio y es bastante bueno para listas ordenadas o en orden inverso, además no requiere mucha memoria. La inserción pura y la inserción con lista enlazada tardan mas o menos lo mismo en el caso medio, ya que son muy similares en cuanto a la cantidad de elementos a recorrer para insertar uno en su lugar, pero por su forma de trabajar la inserción pura es la mas rápida para listas ordenadas mientras la de lista enlazada es la peor, y para listas en orden inverso se cambian las tornas.
He dividido los programas en dos grupos, aquí todo lo desarrollado sobre estructuras de datos y sus pruebas hasta el momento, y aquí todo lo desarrollado sobre ordenación hasta el momento.
No hay comentarios:
Publicar un comentario