Infor

APUNTES

Estructura de Datos y Algoritmos


Curso 2003-2004


www.utomde.com






Pablo Perales Diaz
Algoritmos de clasificación en memoria principal

Estabilidad: decimos que un algoritmo es estable cuando la posición relativa de los elementos de igual valor no varían en el transcurso del algoritmo

Naturalidad: Se dice que el comportamiento de un algoritmo es natural sisu mejor caso (en el que hacemos menos comparaciones y movimientos es cuando el array esta inicialmente ordenado

2.1 Inserción

La idea de este método de clasificación es la de insertar el elemento no ordenado en la posición que le corresponde dentro del conjunto de elementos ya ordenados.

2.1.1 Inserción directa

Se basa en coger el primer elemento de la parte desordenada y buscar laposición que le corresponda dentro de la parte ordenada.

Paso1: Partimos de un Array aleatoriamente ordenado y marcamos su primer elemento como parte ordenada. El resto será la parte desordenada.

Paso2: Cogemos el primer elemento de la parte no ordenada y lo almacenamos en una variable centinela (a[0])

Paso3: Comparamos empezando por el final de la parte ordenada hasta que encontramos unelemento menor.

Paso4: Movemos una posición a la Dcha todos los elementos que han resultado mayores que el que queremos insertar e instalamos el centinela en la posición encontrada.









CÓDIGO

TYPE tarray:Array[0..n] OF INTEGER

PROCEDURE Inserción_Directa(Var a:tarray)
Var i,j
FOR i:= 2 TO n DO
a[0]:= a[i];
j:=I;
WHILE a[0]a[j+1] THEN
Aux:= a[j+1]A[j+1]:=a[j]
A[j]:= aux
K:=j
END
END
R:=k-1
FOR j:=R TO L BY -1 DO
IF a[j]>a[j+1] THEN
Aux:= a[j+1]
A[j+1]:=a[j]
A[j]:= aux
K:=j
END
END
L:=k+1
UNTIL L>R
END Vibración

CONCLUSIONES

* De todos los métodos presentados el de selección directa será el mas recomendable a elegir cuando el array está aleatoriamente ordenado.

* Elmétodo de inserción binaria será el más rápido cuando el desorden se encuentre el las primeras posiciones del array

* El método de vibración será el mas eficiente cuando el array esta inicialmente ordenado.



METODOS AVANZADOS

Algoritmo de Shell o incrementos decrecientes

Se trata de ir realizando la inserción directa con todos los elementos que difieren en [pic] posiciones dentro delarray. Posteriormente haremos la inserción directa con elementos que difieran [pic] posiciones y así sucesivamente hasta obtener la ordenación total

[pic]

Nota: Para que este algoritmo realice una clasificación satisfactoria el ultimo nº de elementos del conjunto de incrementos decrecientes debe ser igual a 1, caso en el que se realizara la inserción directa normal.

Paso 1: Cogemos elprimer elemento del conjunto de incrmentos decrecientes y vamos haciendo grupo con los elementos que difieren en tantas posiciones como nos indique dicho número.

Nota: Siempre nos quedaran tantos grupos como el elemento [pic]

[4,2,1]

|6 |1 |8 |7 |2 |4 |3 |10 |0 |22 |


Grp1 Grp2 Grp3Grp4 grp1 Grp2 Grp3 Grp4 grp1 Grp2

Paso 2: Realizamos la inserción directa con cada uno de los grupos. Para la implementación lo que haremos pasar el elemento que queremos insertar al centinela y compararlo con el ultimo de la parte ordenada [pic] posiciones anteriores. El momento en el que encontremos un elemento menor o el principio del array pararemos y movemos todos loselementos del mismo grupo [pic] posiciones hacia la derecha.


|0 |1 |3 |7 |2 |4 |8 |10 |6 |22 |


Grp1 Grp2 Grp3 Grp4 grp1 Grp2 Grp3 Grp4 grp1 Grp2


Paso 3: Una vez hecha la inserción directa sobre los [pic] grupos, cogemos el siguiente elemento del conjunto de incrementos...