Ordenamiento MS

Arreglos

METODOS DE
ORDENAMIENTO

METODOS DE
ORDENAMIENTO

Se clasifican en
Directos (IN SITU)

SELECCIÓN
INSERCION
INTERCAMBIO

Avanzados

INSERCION DIRECTA
• Los ítems están divididosconceptualmente
en un arreglo destino {A[1] .. A[i-1]} y un
arreglo origen {A[i] .. A[n]}. En cada paso,
empezando con i=2 e incrementando i de
uno en uno, se toma el elemento i de la
secuencia origen y setransfiere a la
secuencia destino insertándolo en el lugar
adecuado

INSERCION DIRECTA
• Como sabemos cual es el sitio apropiado?
– Como el arreglo destino esta ordenado
podemos “dejar caer” elelemento mientras este
sea menor que cada uno de los elemento del
arreglo destino
– Cuando insertemos un elemento en el arreglo
ordenado los elementos que queden por encima
de este deberán correrse unaposición

INSERCION DIRECTA
... Algoritmo
Para i:= 2 a N hacer
x:= A[i];
j:=i-1;
Mientras(x < A[j]) ^ (j > 0) hacer
A[j+1]:= A[j]
j:= j -1
Fin Mientras
A[j+1]:=x
Fin para

INSERCION DIRECTA
•OBSERVACIONES
– Debemos controlar que j > 0 para no exceder el
limite inferior del arreglo, cuando el elemento a
insertar en el arreglo ordenado es menor a todos
ellos.
– Siempre se supone q el primer elementoesta
ordenado, para no tener q perder tiempo
comparándolo consigo mismo

SELECCIÓN DIRECTA
• El método se basa en encontrar en cada
pasada del arreglo el elemento con clave
mínima y ubicarlo en laposicion
correspondiente a la pasada, intercambiando
los elementos
• Es decir se selecciona el elemento menor
del arreglo no ordenado y se lo ubica en el
arreglo ordenado

SELECCIÓN DIRECTA
...Algoritmo
Para i:=1 : (N-1) hacer
x:=A[i]
MIN:=i;
Para j:=(i+1) : N hacer
Si A[j] < x entonces
MIN:=j;
x:=A[j]
Fin si
Fin para
A[MIN]:=A[i]
A[i]:=x
Fin para

SELECCIÓN DIRECTA
• OBSERVACIONES
– Este métodoasí como el de inserción suponen
el peor caso, es decir que el arreglo este muy
desordenado
– En el caso que se los elementos queden
ordenados prematuramente el método seguirá
trabajando hasta llegar...