[ Foro de Pascal ]

Codigo de "Ordenación ShellSort", ¿visualizarlo paso a paso?

04-Apr-2007 19:13
Homer A. Ramos
3 Respuestas

Hola chicos, estoy aprendiendo a "ordenar" con diferentes métodos. Por ejemplo, ahora estoy viendo el método [b]ShellSort[/b], el cual, divide la lista (en la que tengo los valores a ordenar) en grupos de dos.... El caso es que he encontrado un ejemplo de este método por la red y lo que me gustaría saber es: ¿cómo puedo hacer, que tengo que añadir en el código para poder ir viendo paso a paso los cambios que va realizando en la lista? Por ejemplo, tengo la lista: 1 8 4 3 7. Me gustaría ver paso a paso como va ordenandose. Me ayudáis????? es que no me sale correctamente. Gracias a todos!!!! Os paso el código que funciona correctamente: __________________ program ShellSort; {modelo de odenacion de "x" enteros aleatorios} uses crt; const numumElem = 5; type rango = 1..numumElem; Tlista = array [rango] of integer; var lista : Tlista; (*_________________________________*) procedure lista_aleatoria(var list : Tlista; elementos : integer); var i : integer; begin randomize; for i := 1 to elementos do list[i] := Random(1000); end; (*_________________________________*) procedure visualizar_lista(var list : Tlista; elementos : integer); var i : integer; begin for i := 1 to elementos do write(list[i]:6, ' '); writeln(); end; (*_________________________________*) procedure intercambiar(var x, y : integer); var aux : integer; begin aux := x; x := y; y := aux; end; (*_________________________________*) procedure ShellSort(var list : Tlista; num : integer); var lista_dividida, i, j, k : integer; begin lista_dividida := num div 2; while (lista_dividida > 0) do begin for i := (lista_dividida + 1) to num do begin j := i - lista_dividida; while (j > 0) do begin k := j + lista_dividida; if (list[j] 0} end; {for} lista_dividida := lista_dividida div 2; end; {while (lista_dividida > 0)} end; (*_________________________________*) begin {programa principal} clrscr; writeln(); write(' Generar numeros aleatorios: '); lista_aleatoria(lista, numumElem); visualizar_lista(lista, numumElem); writeln(); write(' Ordenacion por ShellSort: '); ShellSort(lista, numumElem); visualizar_lista(lista, numumElem); writeln(); writeln(); end.
05-Apr-2007 21:53
Nacho Cabanes (+32)

Buff... no hay quien lo lea... X-D Elige el estilo "preformateado" cuando copies y pegues, para que no se descoloque (o enciérralo entre <pre> y </pre> si no usas el editor de vista previa, sino el HTML).

En cualquier caso, hay algo extraño aquí: if (list[j] 0}

No cierras paréntesis, sino llave, no hay nada entre el elemento y el cero... ni compila, vamos...

Pero si lo que quieres es que te muestre el progreso, deberías llamar "Visualizar_lista" no desde el cuerpo del programa, después de "ShellSort", sino dentro de "ShellSort, al final de cada pasada del "for", por ejemplo.

08-Apr-2007 12:13
Homer A. Ramos

Puff no había visto como quedó el código... que desastre!! jejeje. Asi es imposible leerlo y, como tu dices, hay un error muy raro con el if.... BUeno, ahí va el código, espero que esta vez salga "bien". Para el caso de visualizar, yo ya lo había intentado pero claro, lo que sucede es que al mostrar, hay algunas veces en las que no se observa cambio alguno, sino que se muestra el vector anterior, "se repite", y lo que me gustaría es que solo se muestre una vez, cuando se ordena y nada más. Por ejemplo, compilo y me sale:
 Generar numeros aleatorios: 75 151 24 153 564

 24 151 75 153 564
 24 151 75 153 564
 24 151 75 153 564
 24 151 75 153 564
 24 75 151 153 564
 24 75 151 153 564
 24 75 151 153 564
 Ordenacion por ShellSort: 24 75 151 153 56
Entendéis a lo que me refiero? Que puedo hacer? Gracias!!
program ShellSort;

{modelo de odenacion de "x" enteros aleatorios}
uses
 crt;

const
 numumElem = 5;

type
 rango = 1..numumElem;

 Tlista = array [rango] of integer;

var
 lista : Tlista;

(*_________________________________*)

procedure lista_aleatoria(var list : Tlista; elementos : integer);
var
 i : integer;
begin
 randomize;
 for i := 1 to elementos do
 list[i] := Random(1000);
end;

(*_________________________________*)

procedure visualizar_lista(var list : Tlista; elementos : integer);
var
 i : integer;
begin
 for i := 1 to elementos do
 write(list[i]:6, ' ');
 writeln();
end;

(*_________________________________*)

procedure intercambiar(var x, y : integer);
var
 aux : integer;
begin
 aux := x;
 x := y;
 y := aux;
end;

(*_________________________________*)

procedure ShellSort(var list : Tlista; num : integer);
var
 lista_dividida, i, j, k : integer;
begin
 lista_dividida := num div 2;
 while (lista_dividida > 0) do
 begin
 for i := (lista_dividida + 1) to num do
 begin
 j := i - lista_dividida;
 while (j > 0) do
 begin
 k := j + lista_dividida;
 if (list[j] 0}
 visualizar_lista(lista, numumElem);
 end; {for}
 lista_dividida := lista_dividida div 2;
 end; {while (lista_dividida > 0)}
end;

(*_________________________________*)

begin
 {programa principal}
 clrscr;
 writeln();
 write(' Generar numeros aleatorios: ');
 lista_aleatoria(lista, numumElem);
 visualizar_lista(lista, numumElem);
 writeln();

 ShellSort(lista, numumElem);
 write(' Ordenacion por ShellSort: ');
 visualizar_lista(lista, numumElem);
 writeln();
 writeln();
end.


10-Apr-2007 10:59
Nacho Cabanes (+32)

Es "normal" que en un paso de ordenación no haya nada que ordenar, especialmente si comparas sólo por pares de elementos.

Yo creo que lo razonable es que, si muestras los pasos intermedios, muestres todos ellos, aunque no en alguno no cambie nada, para que se vea que ese algoritmo no es tan eficiente como podría ser. Si muestras 3 pasos, pero has dado 10, estás "falseando" los resultados del algoritmo, haciendo que parezca más rápido de lo que realmente es, cuando tu algoritmo es de coste constante.

Si aun así quieres, "por estética", que no muestre pasos repetidos, tendrías que hacerlo memorizando el estado anterior en otro array, y haciendo que "visualizar_lista" compare (antes de escribir) el array actual con su estado anterior, y entonces escriba en pantalla únicamente cuando hay cambios.






(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.)