Publicado el 5 de Julio del 2020
861 visualizaciones desde el 5 de Julio del 2020
179,8 KB
39 paginas
Creado hace 10a (13/06/2014)
11-Ordenar
11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort
11: Ordenar
2
Definiciones
Se desea ordenar un set de estructuras, que
contienen información, de acuerdo al valor de un
campo de la estructura denominado clave.
Ordenamiento interno, es aquel que ordena un arreglo
de estructuras; y externo es aquel que ordena un
archivo de estructuras.
Ordenamiento in situ, es aquel que no requiere espacio
adicional (se ordena en el mismo arreglo o archivo).
11: Ordenar
3
Definiciones II
Suelen tenerse dos medidas de eficiencia: C(n) el
número de comparaciones de claves, y M(n) el número
de movimientos de datos, necesarios para lograr el
ordenamiento.
Los métodos mas simples de ordenamiento suelen ser
de complejidad O(n2).
Suelen ser el punto de partida de los métodos más
elaborados que suelen ser O(n*log2(n)).
11: Ordenar
4
Definiciones III
En los diversos algoritmos de ordenamiento es
importante considerar su complejidad en el peor caso
y en promedio.
Si se requiere un ordenamiento ascendente, cada vez
que en el arreglo se tenga: i < j con a[i] > a[j] se tiene
una inversión.
Los algoritmos de ordenamiento eliminan todas las
inversiones.
11: Ordenar
5
11-Ordenar
11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort
11: Ordenar
6
Selección
Algoritmo Selection sort:
Repetir hasta que quede un arreglo de un elemento:
Seleccionar el elemento de la última posición del
arreglo. Sea j su cursor.
Buscar el elemento con la mayor clave en el resto del
arreglo.
Intercambiar el elemento de la última posición del
arreglo con el de mayor clave.
Disminuir el rango del arreglo en uno.
11: Ordenar
7
Selección: tipos
Los siguientes tipos que serán usados en las funciones:
typedef int Tipo; /* tipo de item del arreglo */
typedef int Indice; /* tipo del índice */
Ordenaremos ascendentemente: desde Inf hasta Sup.
11: Ordenar
8
Selección: código
void selectsort(Tipo a[], Indice Inf, Indice Sup)
{ Indice i, j, max; Tipo temp;
for (j=Sup; j>Inf; j--) {
max=j;
temp=a[j];
for(i=j-1; i>=Inf; i--) {
if (a[i]>temp) {
max=i;
temp=a[i];
// Selecciona el ultimo: a[j]
// Busca el mayor entre los
// otros elementos
}
}
a[max]=a[j];
a[j]=temp;
}
}
// Intercambia el mayor con a[j]
11: Ordenar
9
Selección: ejemplos
Ejemplos: aleatorio y peor caso de datos de entrada
11: Ordenar
10
Selección: complejidad
El for interno se realiza: (n-1)+(n-2) +…+ 1 veces. Ya que la primera
vez hay que buscar el mayor en un subarreglo de (n-1)
componentes; la segunda vez se busca el mayor en un subarreglo de
(n-2) componentes; y así sucesivamente.
Suma que tiene por resultado: n*(n-1)/2.
A esto se debe agregar la selección, que es O(1), y el intercambio
(que también es O(1)); acciones que se repiten (n-1) veces.
La complejidad es T(n) = n*(n-1)/2 +(n-1) y entonces O(n2).
Otra forma de calcular la complejidad es la observación de que el
algoritmo se rige por la relación de recurrencia: T(n) = T(n-1) + (n-1)
con T(0) = 0, ya que cada vez se reduce el tamaño del arreglo en
uno, pero con un costo para reducirlo de (n-1) operaciones O(1).
Se logra igual resultado que el anterior: O(n2).
11: Ordenar
11
11-Ordenar
11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort
11: Ordenar
12
Intercambio
Se comparan e intercambian pares adyacentes de ítems, hasta
que todos estén ordenados.
Los mas conocidos son bubble y shakesort. Son algoritmos muy
poco eficientes, estan aqui solo para ilustrar.
Algoritmo Bubblesort:
Comenzar con i=0;
Repetir hasta que quede arreglo de tamaño uno:
Efectúa una pasada hacia arriba, hasta la última posición:
if (a[i] > a[i+1])
swap (a[i], a[i+1]); // intercambiar el mayor hacia arriba
i++;
Disminuir en uno el tamaño del arreglo partiendo por arriba.
11: Ordenar
13
Bubblesort: código
#define SWAP(a, b) { t=a; a=b; b=t; }
#define compGT(a, b) (a > b)
/* Ordena ascendente. Desde indice Inf hasta Sup */
void bubbleSort( Tipo a[], Indice Inf, Indice Sup ) {
Indice i, j; Tipo t; //temporal
for(i=Inf ; i<= Sup; i++) {
// Recorre el arreglo con i
for(j=Inf+1; j<=(Sup-(i-Inf)); j++) { // Recorre con j, compara
y
if( compGT( a[j-1], a[j] ) )
intercambio
// ordena por
SWAP(a[j-1], a[j]);
// el mayor queda arriba.
}
}
}
11: Ordenar
El for interno se realiza: (n-1)+(n-2) +…1. Entonces es O(n2).
14
Bubblesort: complejidad
Algoritmo shakesort o bubblesort de dos pasadas (ambos son O(n2)):
Comenzar con i=0;
Repetir hasta que quede arreglo de tamaño uno:
Efectúa una pasada hacia arriba, hasta la última posición:
if (a[i] > a[i+1])
swap (a[i], a[i+1]);
i++; (más pesado en última posición)
Disminuye en uno el tamaño del arreglo (por arriba)
Efectúa una pasada hacia abajo, hasta el inicio del arreglo:
if (a[i-1] > a[i])
swap (a[i], a[i-1]);
i--; (más liviano en primera posición)
Acorta en uno el tamaño del arreglo (por abajo).
11: Ordenar
15
11-Ordenar
11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort
11: Ordenar
16
Inserción
Algoritmos Inserción:
En la etapa i-ésima se inserta a[i] en su lugar correcto entre:
a[0], a[1],…, a[i-1] que están previamente ordenados.
Hay que desplazar los elementos previamente ordenados, uno a
uno, hasta encontrar la posición donde será insertado a[i].
En el peor caso: si a[0] es mayor que a[i] hay que efectuar i
copias.
En el mejor caso si a[i-1] es menor que a[i], no hay
desplazamientos.
Si existen claves repetidas, éstas conservan el orden original, se
dice que el algoritmo de ordenamiento es estable.
11: Ordenar
17
Inserción: código
typedef int Tipo; /* tipo de item del arreglo */
typedef int Indice; /* tipo del índice */
#define compGT(a, b) (a > b)
void InsertSort(Tipo *a, Indice inf, Indice sup) {
Tipo t; Indice i, j; /*Ordena ascendentemente */
for (i = inf + 1; i <= sup; i++) {
t = a[i]; //se marca el elemento que será insertado.
/* Desplaza elementos hasta encontrar punto de inserción */
for (j = i-1; j >= inf && compGT(a[j], t); j--)
a[j+1] = a[j];
a[j+1] = t; /* lo inserta */
}
}
11: Ordenar
18
Inserción: ejemplos
Ejemplos: aleatorio y peor caso de datos de entrada
11: Ordenar
19
Inserción: complejidad
En el peor caso, el for interno se efectúa: 1 + 2 + 3 +…+(n-1).
Esto en caso que el arreglo esté previamente ordenado en forma
descendente. En el primer recorrido del for interno hay que mover
un elemento; en la segunda pasada, hay que mover dos elementos; y
así sucesivamente, hasta mover (n-1) para dejar espacio en la
primera posición, para insertar el último.
Esto tiene complejidad T(n) = n*(n-1)/2 + (n-1) = O(n2). Se agregan
(n-1) movimientos por el almacenamiento del elemento que será
insertado, más la escritura para la inserción; ambas son O(1).
En el mejor de los casos con un arreglo previamente ordenado en
forma ascendente, el for interno no se realiza nunca; ya que no son
necesarios los desplazamientos que éste efectúa; el lazo externo
debe efectuarse (n-1) vez. Este caso es de complejidad: T(n) =
O(n). Mientras más ordenado parcialmente esté el arreglo, mejor
será el comportamiento del algoritmo de inserción.
11: Ordenar
20
Inserción Binaria
Una posible mejora del algoritmo es la consideración de que el
subarreglo en el cual se insertará el elemento está previamente
ordenado.
En este caso, en lugar de efectuar una búsqueda secuencial de la
posición de inserción, se puede realizar una búsqueda binaria. Sin
embargo esto disminuye el número de comparaciones y no el de
movimiento de los datos (que suele ser de mayor costo).
11: Ordenar
21
Inserción Binaria: código
int BinaryInsertSort(Tipo *a, Indice inf, Indice sup)
{ int op=0;
Tipo t;
Indice i, j, right, left, m;
for (i = inf + 1; i <= sup; i++) {
t = a[i];
left=inf ;
right=i-1;
while (left<=right) {
m=(left+right)/2;
if ( t <a[m]) right=m-1;
else left=m+1;
}
// Desplazar elementos
for (j = i-1; j >= left ; j--)
{
a[j+1] = a[j];
op++;
}
/* inserte */
a[left] = t;
op++;
}
return(op);
}
11: Ordenar
22
11-Ordenar
11.1 Definiciones
11.2 Selección
11.3 Intercambio
11.4 Inserción
11.5 Shellsort
11.6 Quicksort
11.7 Mergesort
11: Ordenar
23
Shellsort
Es uno de los algoritmos más rápidos para ordenar
arreglos de algunas decenas de componentes. Es una
generalizacion del Insertion sort.
Es un método adaptivo que funciona mejor si los
arreglos están casi ordenados. El análisis de su
complejidad es difícil.
Algoritmo Shellsort:
Se ordenan elementos que están a una distancia h entre ellos en
pasadas consecutivas.
Al inicio h es un valor elevado y disminuye con cada pasada.
Sea hk cuando la distancia de comparación es k. La pasada se
denomina fase hk. El algoritmo termina con h1.
11: Ordenar
24
Shellsort II
Después de la fase hk los elementos que están a distancia hk entre
ellos están ordenados: a[i] < a[i + hk] < a[i + 2hk ] < a[i + 3hk] < … para
todo i.
El ordenamiento burbuja ordena en fase h1. Necesariamente
shellsort tiene que llegar a ordenar la fase h1, pero su ventaja es
que el número de intercambios en la fase h1 es menor que los
intercambios necesarios en inserción o por burbuja.
La razón de esto es que si a una lista ordenada de fase hk se la
somete a un ordenamiento de fase hk-1 sigue hk ordenada.
11: Ordenar
25
Shellsort: código
// El algoritmo original hace que hk sea el anterior dividido por dos.
void shellsortShell(Tipo a[], Indice n)
{ Indice
Comentarios de: 11-Ordenar (0)
No hay comentarios