BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.2. ORDENAMIENTO POR INSERCIÓN. (INSERTION SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.2. ORDENAMIENTO POR INSERCIÓN. (INSERTION SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.2. ORDENAMIENTO POR INSERCIÓN. (INSERTION SORT)

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Ordenamiento por insercción.

La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada. Para explicarlo mejor nos basaremos en el siguiente enunciado:

“Para cada elemento de la lista después del primero, comparar los elementos con los anteriores desplazando una posición a la derecha a todos los elementos anteriores que cumplan con la comparación y luego colocar el elemento en la posición del último elemento anterior desplazado.”

Ahora veamos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:

7, 3, 10, 1, 9

La lista tiene 5 elementos, con lo cual tendremos que recorrer la lista 4 veces. Ya que la comparación se hará desde el segundo elemento de la lista, es decir recorremos la lista después del primer elemento hasta el último.


1er. recorrido: Se toma 3 para comparar con los elementos anteriores. Los elementos anteriores son: 7


3

7

10

1

9


La comparación 3<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.


3

7

10

1

9


Al no haber más elementos a comparar colocamos el 3 en la posición del último elemento desplazado.


3

7

10

1

9


2do. recorrido: Se toma 10 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7


10

3

7

1

9


La comparación 10<7, es falsa, entonces no desplazamos nada y se termina este recorrido.


3

7

10

1

9


3er. recorrido: Se toma 1 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7, 10


1

3

7

10

9


La comparación 1<10, es verdadera, entonces desplazamos el 10 una posición a la derecha.


1

3

7

10

9


La comparación 1<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.


1

3

7

10

9


La comparación 1<3, es verdadera, entonces desplazamos el 3 una posición a la derecha.


1

3

7

10

9


Al no haber más elementos a comparar colocamos el 1 en la posición del último elemento desplazado.


1

3

7

10

9


4to. recorrido: Se toma 9 para comparar con los elementos anteriores. Los elementos anteriores son: 1, 3, 7, 10


9

1

3

7

10


La comparación 9<10 es verdadera, entonces desplazamos el 10 una posición a la derecha.


9

1

3

7

10


La comparación 9<7 es falsa, entonces no desplazamos nada y se termina este recorrido, colocando el 9 en la posición del último elemento desplazado.


1

3

7

9

10


Con este último recorrido la lista ya esta ordenada. Tal como se puede observar, cada recorrido termina cuando se encuentra una posición en donde colocar el elemento tomado o cuando ya no haya elementos con que comparar. Bien ahora el siguiente procedimiento sería la primera implementación del algoritmo:


Descargar
Procedure Ordenar(A:LNaturales);         
  Var i,j:longint;
      aux:qword;	     
 Begin         
   for i:=low(A)+1 to High(A) do
    Begin
      aux:=A[i];  //aux almacena el elemento a comparar con los anteriores
      j:=i-1;
      While (j>=0) and (aux<A[j]) do
      //Mientras no sea el fin de la lista y aux sea menor con uno de los
      //elementos anteriores, ir desplazando  
        Begin
          A[j+1]:=A[j];
          j-=1;          
        End;	   	  
      //Colocar aux en la posición del último elemento desplazado.   
      A[j+1]:=aux;      	    
    End;
 End;
Código fuente 1: Primer algortimo Insertion Sort.
Descargar

Este algoritmo es el que hemos usado en capítulos anteriores, pero se tiene que observar que este algoritmo hace uso de la evaluación booleana en cortocircuito. Si observa la condición (j>=0) and (aux<A[j]) del bucle while, puede suceder que cada vez que se disminuye j en 1 este puede llegar a ser negativo, y el algoritmo comparará un valor fuera del rango, algo parecido a esto aux<A[-1], pero esa comparación no sucederá porque se usa la evaluación booleana en cortocircuito, lo que significa que sólo se evaluara el resultado de la primera condición (j>=0), y dependiendo de ella se evaluará la siguiente. Es decir si (j>=0) es falso, entonces no se evalúa la condición (aux<A[j]), ya que basta con que una de las condiciones sea falsa para que el operador and de como resultado un valor falso.

En caso se presente una situación en la que no debemos usar la evaluación booleana en cortocircuito, entonces es necesario usar el tipo de dato longword para la variable j. Esto nos obliga a modificar el algoritmo anterior haciendo uso para ello de una variable de tipo boolean que nos permite controlar el bucle while, y nos indique que j llego al inicio de la lista cuando este obtenga el valor 0. Ejemplo:


Descargar
Procedure Ordenar(A:LNaturales);         
Var i,j:longword;
    aux:qword;      
    IniLista:boolean;
 Begin
     for i:=low(A)+1 to high(A) do
       Begin 
           aux:=A[i];
           j:=i-1; IniLista:=false;       
           While (not IniLista) and (aux<A[j]) do
             Begin                 
                A[j+1]:=A[j];                                            
                if j>0 then j-=1 else IniLista:=true
             End;
           if IniLista then A[j]:=aux   
                       else A[j+1]:=aux
     End;
 End;
Código fuente 2: Segundo algoritmo Insertion Sort, sin el uso de evaluación booleana en cortocircuito.
Descargar

El algoritmo usa la variable IniLista para terminar el bucle while, esta variable será verdadera cuando j llegue a valer 0 y sólo disminuirá el valor de j en 1 cuando j sea mayor que 0, es decir j nunca llegará a valer -1. Esto nos lleva a colocar una condición después del bucle while que verifica como se salió del bucle, y de esa manera evitar incrementar j en 1 cuando este tenga el valor 0. Esta serie de adiciones harán que el algoritmo sea un poco más lento, pero nos permite evitar una comparación fuera del rango de la lista (aux<A [-1]).

Los algoritmos anteriores se pueden mejorar enormemente con el uso de la función move, que se puede usar en vez de ir desplazando los elementos anteriores uno por uno, move nos permite copiar el contenido de una variable por bloques. En ambos algoritmos la variable j nos indica en qué posición se colocará o insertará el elemento a ordenar, de esa manera podemos usar move para indicarle que mueve un bloque desde j a j+1, según sea el caso, veamos cómo debe ser el primer algoritmo usando move:


Descargar
Procedure Ordenar(A:LNaturales);         
  Var i,j:longint;
      aux:qword;	     
 Begin         
   for i:=low(A)+1 to High(A) do
    Begin
      aux:=A[i];      
      j:=i-1;
      While (j>=0) and (aux<A[j]) do j-=1;
      j:=j+1;
      if j<i then Begin
                    Move(A[j],A[j+1],(i-j)*8);  
                    A[j]:=aux;      	          
                  End;
    End;
 End;
Código fuente 3: Algoritmo Insertion Sort con el uso de move.
Descargar

Como se puede observar el bucle while sólo disminuye la variable j hasta encontrar la posición de inserción. Una vez encontrado la posición de inserción entonces se hace uso de move. Se copia desde A[j], en la posición A[j+1], la cantidad de elementos indicada por i-j, se multiplica por 8 porque LNaturales usa qword que tiene un tamaño de 8 bytes y la cantidad de elementos a mover debe ser siempre en bytes; pero en el caso se quiera ordenar un arreglo dinámico que tiene elementos de tipo word, entonces se debe multiplicar por 2 y así respectivamente. Además se puede observar que hay una condición en la que j debe ser menor que i, esta condición es importante para evitar que cuando ambas variables sean iguales no se intente mover 0 bytes.

Para el segundo algoritmo se debe tener en cuenta el hecho de que la variable j no dará un resultado negativo con lo que la rutina move será diferente según cada caso:


Descargar
Procedure Ordenar(A:LNaturales);         
Var i,j:longword;
    aux:qword;      
    IniLista:boolean;
 Begin
     for i:=low(A)+1 to high(A) do
       Begin 
           aux:=A[i];
           j:=i-1;    IniLista:=false;       
           While   (not IniLista) and (aux<A[j]) do
             Begin                                 
                if j>0 then j-=1
                       else IniLista:=true               
             End;
       if j<i then Begin             
          if IniLista then Begin
                          Move(A[j],A[j+1],i*8);  
                          A[j]:=aux ;                                  
                        End    
                    else Begin                              
                           Move(A[j],A[j+1],(i-j)*8);  
                           A[j+1]:=aux ;   
                         End;   
           End;                
     End;
 End;
Código fuente 4: Algoritmo Insertion Sort con el uso de move y sin evaluación booleana en cortocircuito.
Descargar

En caso j sea cero (se llego al inicio de la lista) no es necesario restar i de j, y en caso sea distinto de cero se resta i de j, para obtener la cantidad de elementos a copiar con move.

Los algoritmos mencionados anteriormente ordenan la listas de menor a mayor (ascendente), en caso quisiéramos hacerlo de mayor a menor (Descendente), sólo basta con cambiar la condición, aux<A[j] por aux>A[j].

Si se quiere ordenar listas que usen los tipos de datos como ansistring o unicodestring, entonces lo recomendado es usar uno de los algoritmos que no use move, ya que será difícil determinar la longitud en bytes a desplazar por esta función.

El siguiente archivo comprimido: OrdenacionInsercion.zip ,tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales y LPalabras de la unidad listas.




SIGUIENTE
SIGUIENTE
SIGUIENTE



 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.


Comments System WIDGET PACK






PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.