ordenamiento - cime.cl · tipos de ordenamiento universidad técnica federico santa maría -...

Universidad Técnica Federico Santa María - Departamento de Informática

Ordenamiento

Mauricio SolarLorna Figueroa

2008


Ordenamiento

• Importancia de mantener orden de datos: Fácil y rápido acceso de los datos.

• Criterio para el análisis de un algoritmo:• factores con respecto a qué se desea optimizar:

• Espacio de memoria• Tiempo de ejecución


Ordenamiento

• Al momento de tomar esta decisión se debe investigar:• Con qué equipo de trabajo se cuenta (donde se ejecuta

el programa), • Necesidades del cliente (si debe ser rápido porque se

atiende a diario muchas personas), • etc.


• Es la operación de arreglar los registros de una tabla en algún orden de acuerdo a algún criterio.

• El propósito principal de un ordenamiento es el de facilitar la búsqueda.

• Ejemplos : Guía telefónica, tablas de contenido, bibliotecas y diccionarios, etc.

¿Qué es ordenamiento?


• Formalmente: Dado un conjunto de n elementos a1, a2,..., an y una relación de orden total (≤) sobre ellos, el problema del ordenamiento consiste en encontrar una permutación de esos elementos ordenada de forma creciente/decreciente.

• El tipo y tamaño de los elementos, así como el dispositivo en donde se encuentran almacenados pueden influir en el método utilizado para ordenarlos.



• Distintos criterios para clasificar los algoritmos, una posibilidad es respecto a su eficiencia:

• Θ(n2): Burbuja, Inserción, Selección.• Θ(nlogn): Mezcla, Montículos, Quicksort.• Otros:

• Incrementos Θ(n1.25), • Cubetas Θ(n), • Residuos Θ(n).



• Interno : datos a ordenar están localizados en la memoria principal del computador.

se asume que el tiempo que se requiere para acceder cualquier elemento es el mismo.

• Externo : datos a ordenar están localizados en algún dispositivo externo (disco, cinta, cilindro magnético, etc),

se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada.

Tipos de Ordenamiento


• Ordenamiento por intercambio

1.- Burbuja. 2.- Transposición par e impar. 3.- Shaker sort (vibración). 4.- Quick sort (rápido).

• Ordenamiento por selección

1.- Selección directa. 2.- Heap sort.

Taxonomía de los algoritmos - internos


• Ordenamiento por inserción1.- Inserción directa. 2.- Inserción binaria. 3.- Shell.

• Ordenamiento por distribución1.- Base radix. 2.- Conteo.



• Ordenamiento por intercalación1.- Concatenación directa. 2.- Concatenación merge.

• Ordenamiento por calculo de direcciones

1.- Ordenamiento de llaves por calculo de direcciones.



• Straight merging.• Natural merging. • Balanced multiway merging.• Polyphase sort. • Distribution of initial runs.

Taxonomía de los algoritmos - externos


• Los elementos se toman de dos en dos, se comparan y se intercambian si no están en el orden adecuado.

• Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.

• Burbuja. • Transposición par e impar. • Shaker sort (vibración). • Quick sort (rápido).

Algoritmos de intercambio


• Se selecciona o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada.

• Este proceso se repite para el resto de los elementos hasta que todos son analizados.

• Selección directa• Heap sort

Algoritmos de selección


• Los elementos que van a ser ordenados son considerados uno a la vez.

• Cada elemento es insertado en la posición apropiada con respecto al resto de los elementos ya ordenados.

• Inserción directa,• Shell,• Inserción binaria, • Hashing

Algoritmos de inserción


• Cada elemento es comparado con los demás. • En la comparación se cuenta cuántos elementos son más

pequeños que el elemento que se está analizando, generando asíuna enumeración.

• El número generado para cada elemento indicará su posición.

Algoritmos de enumeración


• Los métodos simples son: • Inserción (o por inserción directa), selección, burbuja y

shell, en dónde el último es una extensión al método de inserción, siendo más rápido.

• Los métodos más complejos son:• quick-sort (ordenación rápida) y el heap sort.

Taxonomía de los algoritmos


• Pasa por un archivo en forma secuencial varias veces. • Cada paso consiste en comparar un elemento del archivo con su

sucesor (x[j] con x[j+i]), e intercambiar los dos elementos si no están en el orden apropiado.

• Este algoritmo es de fácil comprensión y programación pero es de los menos eficientes

• n-1 pasos y n-i comprobaciones en cada paso.

Algoritmos de Intercambio: Burbuja


• Recorre el arreglo intercambiando los elementos adyacentes que estén desordenados.

• Se recorre el arreglo hasta que ya no haya cambios. • toma el elemento mayor y lo va recorriendo de posición en

posición hasta ponerlo en su lugar.


paso 1: [ Inicializar i al final de arreglo ] for(i = n; i ≥ 1; i--)paso 2: [ Inicializar j desde la segunda posición ] for(j = 2; j ≥ i; j++)paso 3: [ Si a[j-1] es mayor que el que le sigue ] if a[j-1]< a[j]paso 5: [ Los intercambia ] swap(a,j-1,j);paso 6: [ Fin ]


void Burbuja ( vector a; int prim, ult) {int i, j;for ( i = prim; i <= ult-1; i++ ) {

for ( j = ult; j <= i+1; j-- ) {if ( a[j-1]>a[j] )

swap ( a, j-1, j );}

}}

}

Burbuja - implementación


• En el peor de los casos, el número máximo de revisiones es n-1 y el número de intercambios o comparaciones está dado por (n-1) * (n-1) = n2 - 2n + 1

• En el mejor de los casos, el número de revisiones es mínimo 1 y el ciclo de comparaciones es n-1

• El algoritmo es O(n) en el mejor de los casos y O(n2) en el peor de los casos.

• Ventaja: requiere poco espacio adicional• una posición de memoria para el valor para intercambio

• Desventaja: utilizar excesivo tiempo de ordenamiento por el número de comparaciones que realiza.



• Es de complejidad cuadrática.• Es el peor entre los algoritmos de O(n2): Selección, Inserción y

Burbuja, no sólo en cuanto al tiempo de ejecución, sino también respecto al número de comparaciones y de intercambios que realiza.

• Una posible mejora que puede admitir este algoritmo es el control de la existencia de una pasada sin intercambios; en ese momento el vector estará ordenado.

• Mejora: Utilizar una bandera booleana que cambia cuando se realiza algún intercambio,

• Permanece sin cambio cuando no cambia ningún valor,• puede truncar el ciclo y terminar el proceso de

ordenamiento.



void burbuja() {int aux; Boolean b = true; byte i = 1, j;while ( (i <= n-1) && (b) ) {

b = false;while ((j< n-1) && (b)) {

b = false;for (j = 1; j <= n-1; j++) {

if (x[j] > [j+1]) {b = true;aux = x[j];x[j] = x[j+1];x[j+1] = aux;

}}i++;

}}

Burbuja - implementación


Burbuja - ejemplo

1 [20] 10 102 [10] 20 203 [40] 40 304 [30] 30 40n = 4 ( n-1 = 3 )b = t, f, t, t, fi = 1, 2, 3j = 1, 2, 3x = 2, 3aux = 20, 40


Algoritmos de Intercambio: Par_impar

void par_impar( ) { int r, i, j, aux; r = (n+1)/2; for ( j = 1; j <= r; ) {

i = 1; while (i<n) {

if ( x[i] > x[i+1] ) { aux = x[i];x[i] = x[i+1];x[i+1] = aux;i = i+2;

} else

i = i+2; }

i = 2; while ( i < n ) {

if ( x[i] > x[i+1] ) { aux = x[i];x[i] = x[i+1];x[i+1] = aux;i = i+2;

}else

i = i+2; }

}}


Algoritmos de Intercambio: Par_impar

1 [40] 30 30 30 10 10 10 102 [30] 40 10 10 30 30 30 203 [10] 10 40 40 40 20 20 304 [60] 60 60 20 20 40 40 405 [20] 20 20 60 60 60 50 506 [50] 50 50 50 50 50 50 60

n = 6r = 3j = 1,2,3.i =1,3,5,7,2,4,6,1,3,5,7,2,4,6,1,3,5,7,2,4,6aux = 40,40,60,30,40,60,30


Algoritmos de Intercambio: shaker

• La idea básica de este algoritmo consiste en mezclar las dos formas en que se puede realizar el método de la burbuja.

• En este algoritmo cada pasada tiene dos etapas. 1. En la primera etapa "de derecha a izquierda“:

• Se trasladan los elementos más pequeños hacia la parte izquierda del arreglo, almacenando en una variable la posición del último elemento intercambiado.

• Las sucesivas pasadas trabajan con los componentes del arreglo comprendidos entre las posiciones almacenadas en las variables.

• El tamaño de la variable que almacena el extremo izquierdo del arreglo es mayor que el contenido de la variable que almacena el extremo derecho.



void shakersort ( ) { int aux,k,i,r,j; i = 2; r = n; k = n;do

for ( j = r; j >= i; j--) { if (x[j-1] > x[j]) {

aux = x[j-1];x[j-1] = x[j];x[j] = aux; k =j;

}} i = k+1;

for ( j = i; j <= r; ) { if ( x[j-1] > x[j] ) {

aux = x[j-1]; x[j-1] = x[j];x[j] = aux;k = j;

}} r = k-1;

while ( i > r );}



1 [38] 38 12 122 [12] 12 38 233 [56] 23 23 384 [23] 56 56 56

i = 2,3r = 4,2k = 4,2,3j = 4,3,2,3,4aux = 56,38,38


Algoritmos de Intercambio: Quick Sort

void quick_sort (int a[ ],int p, int q) {int r;int contador = 1;if (p < q) {

contador ++;r = particion(a,p,q);quick_sort(a,p,r);quick_sort(a,r+1,q);

}}


int particion(int a[ ],int p, int temp q) {int temp, x = a[p], i = p-1, j = q+1, cont = 3;while(1) {

j = j-1; cont+=5;while( a[j] > x ) {

cont += 2;j--;

}i++;while ( a[i] < x ) {

cont+=2;i++;

}if( i < j ) {

cont += 3;temp = a[i];a[i] = a[j];a[j] = temp;

}else

return j;}

}


Algoritmos de Selección: Selección directa

• Se divide el vector en dos zonas, una ordenada y otra sin ordenar. Inicialmente la zona ordenada está vacía y coincide con la posición 1.

• En cada iteración se toma el elemento mínimo de la zona sin ordenar y lo coloca en la zona ordenada, intercambiándolo con el elemento siguiente al último de la zona ordenada.

• A continuación aumenta la zona ordenada en un elemento para incluir el que se acaba de añadir y vuelve a comenzar otra iteración.

• Para ordenar todo el vector, se debe realizar una iteración por cada elemento nuevo a colocar en la zona ordenada y en cada iteración recorrer toda la zona no ordenada del vector para encontrar el mínimo y ponerlo en la zona ordenada.



• Encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición.

• Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo el arreglo.

paso 1: [ Para cada posición del arreglo ] for (i=1;i<= n;)paso 2: [ Inicializar la posición del menor ] { min = i;paso 3: [ Recorrer todo el arreglo ] for( j = i+1; j <= n;)paso 4: [ Si a[ j ] es menor ] if a[j] < a[min]paso 5: [ Reasigna el menor ] min = j;paso 6: [ Intercambia los datos ] swap(a,min,j)paso 7: [ Fin ] }



• El arreglo a ordenar es a = [ 'a','s','o','r','t','i','n','g','e','x','a','m','p','l','e' ]• Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este

caso el menor elemento es la primera 'a'. No ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el dato que está en la segunda posición, la 's', quedando así el arreglo después de dos recorridos: a = [ 'a','a','o','r','t','i','n','g','e','x','s','m','p','l','e' ].

• El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve de la siguiente manera:

• a = [ 'a','a','e','e','t','i','n','g','o','x','s','m','p','l','r' ].• De esta manera se va buscando el elemento que debe ir en la siguiente posición

hasta ordenar todo el arreglo.


Selección directa - implementación

void Seleccion(vector a; int prim, ult) {int i;for ( i=prim; i <= ult-1; i++ ) {

Intercambia(a ,i, PosMinimo (a, i, ult) )}

}

int PosMinimo(vector a; int i, j ) {// devuelve la posicion del minimo elemento de a[i..j]

int pmin, k;pmin = i;for ( k = i+1; k <= j; k++) {

if ( a[k] < a[pmin] ) pmin = k;

}return pmin;

}


• El arreglo a ordenar es:a = [ 'a', 's', 'o', 'r', 't', 'i', 'n', 'g', 'e', 'x', 'a', 'm', 'p', 'l', 'e' ]

• Se empieza por recorrer el arreglo hasta encontrar el menor elemento.

• En este caso el menor elemento es la primera 'a'• No ocurre ningún cambio.

• Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'

• Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo después de dos recorridos:

a = [ 'a', 'a', 'o', 'r', 't', 'i', 'n', 'g', 'e', 'x', 's', 'm', 'p', 'l', 'e' ]

Selección directa - ejemplo


• El siguiente elemento, el tercero en orden de menor mayor es la primera 'e'

• se intercambia con lo que está en la tercera posición, la 'o'• Le sigue la segunda 's',

• la cual es intercambiada con la 'r'. • El arreglo ahora se ve de la siguiente manera:

a = [ 'a', 'a', 'e', 'e', 't', 'i', 'n', 'g', 'o', 'x', 's', 'm', 'p', 'l', 'r' ]

• De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.

Selección directa - ejemplo


• En el primer paso del ordenamiento se efectúan n-1comparaciones, en el segundo n-2 comparaciones, y asísucesivamente.

• El total de comparaciones aproximadas, está dado por: n(n-1)/2.• La relación de ordenamiento es O(n)2 para cualquier estado inicial

de los elementos del arreglo. • El costo del problema, tanto en el caso peor como en el caso

mejor es: O(n) = n2

• Este método se le conoce por el nombre de "EMPUJE HACIA ABAJO", y es recomendable para un número pequeño de elementos.

Selección directa


• Es de complejidad cuadrática.• Dado el número de operaciones de comparación e intercambio

que realiza, es el más adecuado para ordenar pocos registros de gran tamaño.

• Si el tipo base del vector a ordenar no es entero, sino un tipo más complejo (guías telefónicas, índices de libros, historiales hospitalarios, etc.) se debe dar mayor importancia al intercambio de valores que a la comparación entre ellos en la valoración del algoritmo por el costo que suponen.

• Analizando el número de intercambios que realiza, es de orden O(n), frente al orden O(n2) de intercambios que presentan los métodos de Inserción o Burbuja.

Selección directa


• Es un método de ordenamiento por selección.• Heap: es un árbol binario de altura mínima, en que los nodos del

nivel más bajo están lo más a la izquierda posible. • La información es almacenada de manera que al recorrer un

camino desde la raíz hacia las hojas, los datos se encuentran en orden descendente.

• Si se presenta este arreglo resultante como un árbol se observa que cada elemento es el padre de los elementos z[i], z[i+1] puesto que es una estructura con un grupo en el cual j ≤ i/2.

• En la segunda parte del procedimiento se realiza el proceso de ordenamiento en el cual se recorre el árbol de tal forma que el resultado es una lista ordenada de elementos.

Algoritmos de Selección: Heapsort


• El vector debe tener estructura de montículo, es decir, un árbol en el que los hijos de cada nodo son siempre menores que el padre.

• De esta forma, no se tiene que recorrer toda la zona desordenadapara encontrar el elemento máximo, ya que en este caso la ordenación se realiza en sentido inverso.

• La estructura en montículo facilita esta búsqueda y la hace del orden de log(n).

• Por lo tanto el costo final será log(n) para cada elemento que se quiera colocar en la zona ordenada, es decir:

O(n) = n log(n)



• Aplicar HeapSort( ) para ordenar el conjunto de datos, S = { 25, 15, 20, 3, 5, 10 }

construir el árbol, y numerar los nodos :

Heapsort - ejemplo

25

15 20

3 5 10

1

2 3

4 5 6

6543211053201525


Verificar la condición de heapk = 6 ; (k = nº de nodos)Intercambiar nodo 1 con nodo 6 :

Heapsort - ejemplo

25

15 20

3 5 10

1

2 3

4 5 6

10

15 20

3 5 25

1

2 3

4 5 6

Resultado :

6543212553201510


Revisar y recuperar condición de heap, si no se cumple, entre los nodos 1 y 5:

Heapsort - ejemplo

Resultado:

10

15 20

3 5 25

1

2 3

4 5 6

20

15 10

3 5 25

1

2 3

4 5 6

15

10 20

3 5 25

1

2 3

4 5 6

6543212553101520


k = 5; intercambiar los nodos 1 y 5 :

Heapsort - ejemplo

Resultado: 5

15 10

3 20 25

1

2 3

4 5 6

20

15 10

3 5 25

1

2 3

4 5 6

6543212520310155


Revisar y recuperar condición de heap, si no se cumple, entre los nodos 1 y 4:

Heapsort - ejemplo

Resultado :5

15 10

3 20 25

1

2 3

4 5 6

15

5 10

3 20 25

1

2 3

4 5 6

6543212520310515



Heapsort - ejemplo

Resultado: 3

5 10

15 20 25

1

2 3

4 5 6

15

5 10

3 5 25

1

2 3

4 5 6

6543212520151053


Revisar y recuperar condición de heap, si no se cumple, entre los nodos 1 y 3 :

Heapsort - ejemplo

Resultado :

3

5 10

15 20 25

1

2 3

4 5 6

5

3 10

15 20 25

1

2 3

4 5 6

10

3 5

15 20 25

1

2 3

4 5 6 6543212520155310



Heapsort - ejemplo

Resultado: 5

3 10

15 20 25

1

2 3

4 5 6

10

3 5

15 20 25

1

2 3

4 5 6

6543212520151035


Heapsort - ejemplo

5

3 10

15 20 25

1

2 3

4 5 6

Revisar y recuperar condición de heap, si no se cumple, entre los nodos 1 y 2.

6543212520151035


Heapsort - ejemplo


5

3 10

15 20 25

1

2 3

4 5 6

3

5 10

15 20 25

1

2 3

4 5 6

Resultado :

6543212520151053


Heapsort - ejemplo

3

5 10

15 20 25

1

2 3

4 5 6

El algoritmo finaliza, y los datos están ordenados ascendentemente, siguiendo la numeración de los nodos :

6543212520151053


Heapsort - implementación

void heap_sort(int n; int x[ ] ) {int i, j, k, y;for ( k = 2; k <= n; k++ ) {

i = k;y = x[k];j = i/2;while ( j > 0 ) {

if ( y <= x[j] ) {x[i] = yx[i] = x[j];i = j;j = i/2;

}}

}


Heapsort - implementaciónfor (k= n; k>= 2; k--) {

y = x[k];x[k] = x[1];i = 1;j = 2;if ( ( x[3] > x[2] ) && ( k-1 > =3 ) ) {

j =3;while (j < =k-1) {

if ( x[j] < =y ) {x[i] = y;x[i] = x[j];i = j;j = 2*i;if ( x[j-1] > x[j] )

j++;}

}}


Heapsort – implementación ver.01

HeapSort( ) {BuildHeap( ); // construir el heapfor ( k = n ; k > 1 ; k = k – 1 ) {

Intercambiar( A[ 1 ], A[ k ] ;Heapify(1, k - 1) ;

}}

BuildHeap( ) {for ( j = n ; j >= 1 ; j -- )

Heapify( j, n)}

Heapify(j, k) {// hace que A[j : k] cumpla con la condición de heap, suponiendo que A[j+1, k] // la cumple

if ( (A[ j ] tiene algún hijo ) && ( algún hijo( no es hoja ) de A[ j ] es mayor que él ) ) {Sea A[ s ] el mayor de los hijos de A[ j ] ;Intercambiar (A[ j ], A[ s ] ) ;Heapify(s, k) ;

}}


• Ordena un conjunto de datos, en tiempo O(n lg n) en el peor caso.

• Heapify(j, k) toma tiempo O(lg(k-j)• Equivalentemente, hacer heapify partiendo de un elemento de

altura h, toma tiempo O(h).• En BuildHeap hay a lo más n / 2i elementos de altura i. • Si el heap tiene altura total h, el tiempo total ocupado por

buildheap es :

• En HeapSort( ), el tiempo total, para el peor caso, es:


( )nOnoioi

ii

hii

n =⎟⎠

⎞⎜⎝

⎛=⎟

⎠

⎞⎜⎝

⎛ ∑∑≥≤≤ 0

20

2

( ) ( )nnOjOnOnj

lglg2

=⎟⎟⎠

⎞⎜⎜⎝

⎛+ ∑

≤≤


• Toma cada elemento del arreglo y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo.

• Si el elemento con el que se está comparando es mayor que el elemento a ordenar,

• se recorre hacia la siguiente posición superior. • Si no,

• se detiene el proceso de comparación • el elemento ya está ordenado • y se coloca en su posición

• es la siguiente a la del último número con el que se comparó.

Algoritmos de Inserción: Inserción directa


paso 1: [Para cada posición del arreglo] for(i = 2; i<= n;i++)paso 2: [ Inicializar v y j ] { v = a[i]; j = i;paso 3: [ Compara v con los anteriores ] while(a[j-1]>v) && (j>1)paso 4: [ Recorre los datos mayores ] { a[j] = a[j-1];paso 5: [ Decrementa j ] j = j-1; }paso 5: [ Inserta v en su posición ] a[j] = v;

Algoritmos de Inserción: Inserción directa

• Toma el arreglo de datos a ordenar a[] y modifica las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor.

• n representa el número de elementos que contiene a[ ].


• El arreglo a ordenar es:a = [ 'a', 's', 'o', 'r', 't', 'i', 'n', 'g', 'e', 'x', 'a', 'm', 'p', 'l', 'e' ]

• El algoritmo recorre el arreglo de izquierda a derecha.• Primero toma el segundo dato, 's' y lo asigna a v; • i toma el valor de la posición actual de v.• Luego compara 's' con lo que hay en la posición j-1, ie, con 'a'. • Debido a que 's' no es menor que 'a' no sucede nada y avanza i.• Ahora v toma el valor 'o' y lo compara con 's',

• como es menor, lleva 's' a la posición de la 'o'; • decrementa j, la cual ahora tiene la posición en dónde estaba 's';

Inserción directa – Ejemplo


• compara a 'o' con a[j-1] , es decir, con 'a'• Como no es menor que 'a' sale del for y pone la 'o' en la posición

a[j]• El resultado hasta este punto es el arreglo siguiente:

a = [ 'a', 'o', 's', 'r', .... ]

• Así se continúa y el resultado final es el arreglo ordenado :

a = [ 'a', 'a', 'e', 'e', 'g', 'i', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'x' ]

Inserción directa – Ejemplo


• Si el arreglo inicial está ordenado se hace una comparación en cada paso, O(n).

• Si los elementos están ordenados en sentido inverso la relación es O(n)2.

• Número de comparaciones:• arreglo ordenado: n-1• arreglo desordenado: (n-1)*(n/2)

• Método muy adecuado para aquellas situaciones en donde se necesita ordenar un vector que está casi ordenado, como suele suceder en aquellas aplicaciones de inserción de elementos en bancos de datos previamente ordenados cuya ordenación total se realiza periódicamente.

Inserción directa


void Insercion (vector a; int prim, ul) {int i, j, x;for ( i = prim+1; i <= ult; i++ ) {

x = a[i]; j = i-1;while ( ( j >= prim ) && (x < a[j] ) ) {

a[j+1] = a[j]; j--;

}a[j+1] = x;

}}

Inserción directa - implementación


Inserción_binaria( int x[] ) {int a, i, j,m, s, r;for ( i = 2; i <= n; ) {

a = x[i];s = 1;r = i;while (s < r) {

m =(s+r) div 2;if(x[m] < a)

s = m+1;else

r = m; }

Inserción binaria - implementación

for( j = i; j > r+1 ; j-- ) x[j] = x[j-1];

}x[r] = a;

} }


• Similar a la inserción directa, realiza el mismo número de pasos, toma la misma variable auxiliar ´a´ e inicializa 2 variables.

• El ordenamiento se lleva a cabo de la siguiente manera: Saca mitad de s y r, compara el contenido de la mitad con el valor de“a" si es más grande, hace más grande el límite superior de lo contrario, hace más grande el límite inferior.

• Este proceso se realiza mientras el límite inferior sea menor que el superior, después se realiza un ciclo decrementado donde los números mayores se van bajando, y por ultimo se asignan el valor de “a", al contenido del rango “r".

Inserción binaria


• También llamado Ordenamiento de disminución incremental.• Ordena subgrupos de elementos separados k unidades (respecto

de su posición en el arreglo) del arreglo original. • El valor k es llamado incremento. • Después de que los primeros k subgrupos han sido ordenados

(generalmente utilizando insercion directa), se escoge un nuevo valor de k más pequeño, y el arreglo es de nuevo dividido entre el nuevo conjunto de subgrupos.

• Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de k.

• Eventualmente el valor de k llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.

• Al principio del proceso se escoge la secuencia de decrecimientode incrementos; el último valor debe ser 1.

Algoritmos de Inserción: Shell


• Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos.

• Cuando el incremento toma un valor 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.

• El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

• Su complejidad es difícil de calcular y depende mucho de la secuencia de incrementos que utilice.

• En general este método es el escogido para muchas aplicaciones reales por ser muy simple teniendo un tiempo de ejecución aceptable incluso para grandes valores de n.

Algoritmos de Inserción: Shell


void Shell( int n; int x[ ] ) {int aux, salto = n/2, i, j, k;while (salto > 0) {

for ( i = salto +1; i <= n; i++ ) {j = i - salto;while ( j > 0 ) {

n = j + salto;if ( x[j] <= x[k] ) j = 0;else {

aux = x[j]; x[j] = x[k];x[k] = aux;

}j = j - salto;

}}salto = salto /2;

}}

Shell - implementación


• Para el arreglo a = [ 6, 1, 5, 2, 3, 4, 0 ], se tiene el siguiente recorrido:

Shell - ejemplo

Ninguno0, 1, 2, 3, 4, 5, 615(4,2), (4,3)0, 1, 2, 3, 4, 5, 614

Ninguno0, 1, 4, 2, 3, 5, 633(2,0)0, 1, 4, 2, 3, 5, 632

(6,2), (5,4), (6,0)2, 1, 4, 0, 3, 5, 631IntercambioLista OrdenadaSaltoRecorrido


void conteo(int n, int x[ ] ) {int s[n], p, i, j;for ( i = 1; i <= n; i++ ) {

p =1;for( j = 1; j <= n; j++)if (x[i] > x[j])

p++;s[p]=x[i];

}}

1 [20] [1]2 [15] [8]3 [8] [15]4 [1] [20]i = 1, 2, 3, 4p = 1, 2, 3, 4 |1,2,3,4| |1,2,3 | |1, 2 | |1 |j = 1, 2, 3, 4 |1,2,3,4| |1,2,3,4| |1,2,3,4|

Algoritmos por distribución: Método de conteo


• Utiliza la técnica de Divide y Vencerás.• Su estrategia consiste en dividir el vector en dos subvectores,

ordenarlos mediante llamadas recursivas, y finalmente combinar los dos subvectores ya ordenados.

Algoritmos de Intercalación: Mergesort


void Mezcla( vector a,b; int prim,ult ) {// utiliza el vector b como auxiliar para realizar la mezcla int mitad;if ( prim < ult ) {

mitad = ( prim + ult ) / 2;Mezcla ( a, b, prim, mitad );Mezcla ( a, b, mitad+1, ult );Combinar ( a, b, prim, mitad, mitad+1 ,ult );

}}

Mergesort - implementación


void Combinar(vector a, b; int p1,u1,p2,u2) {// mezcla ordenadamente los subvectores a[p1..u1] y a[p2..u2] suponiendo que están ya// ordenados y que son consecutivos (p2 = u1+1), utilizando el vector auxiliar b.int i1, i2, k;if ( ( p1 > u1) || ( p2 > u2 ) ) exit (1);for ( k = p1; k <= u2; k++ ) {

b[k] = a[k];} // volcamos a en bi1 = p1;i2 = p2; // cada indice se encarga de un subvectorfor ( k = p1; k <= u2; k++ ) {

if ( b[i1] <= b[i2] ) {a[k] = b[i1];if ( i1 < u1 ) i1++;else b[i1] = max_int;

}

Mergesort - implementación

else {a[k] = b[i2];if ( i2 < u2 ) i2++;

else b[i2] = max_int;}

} }


void Merge( int an,ab,cn ) {int apa =1, apb =1, apc =1;if ( ( an + bn ) > cn )

printf("ERROR");else {

while( (apa <= an) && (apb <= bn) ) {if a[apa] < b[apb]) {

c[apc] = a[apa];apa++;

}else {

c[apc] = b[apb];apb++;

}apc++;

}

Algoritmos por intercalación: merge

while( apa <= an ) {c[apc] = a[apa];apa ++;apc ++;

}while (apb <= bn) {

c[apc] =b[apb];apb++;apc++;

}}

}


• Ordena n elementos en tiempo Θ(nlogn) en cualquiera de los casos (peor, mejor o medio).

• Sin embargo tiene una complejidad espacial, en cuanto a memoria, mayor que los demás (del orden de n).

• Otras versiones de este algoritmo no utilizan el vector auxiliar b, sino que trabajan sobre el propio vector a ordenar, combinando sobre él los subvectores obtenidos de las etapas anteriores.

• Consigue ahorrar espacio (un vector auxiliar), pero complica el código del algoritmo resultante.



• Se adapta muy bien a distintas circunstancias, por lo que es comúnmente utilizado no sólo para la ordenación de vectores.

• Por ejemplo, el método puede ser también implementado de forma que el acceso a los datos se realice de forma secuencial, por lo que hay diversas estructuras (como las listas enlazadas) para las que es especialmente apropiado.

• También se utiliza para realizar ordenación externa, en donde el vector a ordenar reside en dispositivos externos de acceso secuencial (i.e. archivos).



• Se supone que los datos a ordenar son números naturales, todos distintos y comprendidos en el intervalo [1,n].

• Es decir, el problema es ordenar un vector con los n primeros números naturales.

• Bajo esas circunstancias es posible implementar un algoritmo de complejidad temporal O(n): ordenación por Cubetas,

• en cada iteración se sitúa un elemento en su posición definitiva.

Ordenación por Cubetas (Binsort)


void Cubetas ( vector a ) {int i;for ( i = 1; i <= n; i++ ) {

while ( a[i] != i ) {swap ( a, i, a[i] );

}}

}

Ordenación por Cubetas (Binsort)


• Puede utilizarse cuando los valores a ordenar están compuestos por secuencias de letras o dígitos que admiten un orden lexicográfico.

• El método consiste en definir k colas (numeradas de 0 a k–1) siendo k los posibles valores que puede tomar cada uno de los dígitos que componen la secuencia.

• Una vez tengamos las colas habría que repetir, para i a partir de 0 y hasta llegar al número máximo de dígitos o letras de nuestras cadenas:1. Distribuir los elementos en las colas en función del dígito i.2. Extraer ordenada y consecutivamente los elementos de las

colas, introduciéndolos de nuevo en el vector.

Ordenación por Residuos (Radix)


• Sea el vector: [0, 1, 81, 64, 23, 27, 4, 25, 36, 16, 9, 49].• En este caso se trata de números naturales en base 10, que son

secuencias de dígitos. • Se necesitan 10 colas.

• Cada uno de los dígitos puede tomar 10 valores (del 0 al 9)

• En la primera pasada se introducen los elementos en las colas deacuerdo a su dígito menos significativo:



• Extraer ordenada y sucesivamente los valores, obteniendo el vector: [0, 81, 1, 23, 4, 64, 25, 16, 36, 27, 49, 9].

• Volver a realizar otra pasada, esta vez tomando el segundo dígito menos significativo:


• Volviendo a extraer ordenada y sucesivamente los valores se obtiene el vector: [0, 1, 4, 9, 16, 23, 25, 27, 36, 49, 64, 81].

• Como el máximo de dígitos de los números a ordenar era dos, con dos pasadas es suficiente.


typedef struct colaitem {vector elems;int cont

}void Residuos(vector a; int B, prim, ult) {

int i, j, k, h, digito iter;boolean sigo;colaitem colas[MAXB-1];iter = 1; // iter va acumulando B1,B2,B3,... do // para cada uno de los digitos

for ( i = 0; i <= B-1; i++ ) // inicializar las colascolas[i].cont = 1; // primera posicion libre

// clasificacion de los elementos en las colas sigo = false; // indica si quedan numeros con mas digitosfor ( i = prim; i <= ult; i++ ) {

sigo = ( ( a[i] / iter ) >= int( B ) ) || sigo;



digito = ( a[i] / iter ) % int(B); // num cola colas[digito].elems[colas[digito].cont] = a[i];colas[digito].cont++; // inserta a[i] en su cola

}iter = iter*int(B);j = prim; // ahora volcamos las colas sobre el vectorfor ( i = 0; i<= B-1; i++ ) {

h = colas[i].cont-1; // num de elementos en esa colafor ( k = 1; k <= h; k++ ) {

a[j] = colas[i].elems[k]; j++;

}}

while ( ! Sigo );}



Búsqueda

Mauricio SolarLorna Figueroa

2008


Búsqueda

• La recuperación de información es una de las más importantes aplicaciones de los computadores.

• Dado un nombre entregar un número telefónico asociado. • Dado un número o nombre se deben encontrar los registros

personales de dicho nombre o clave. • En estos ejemplos se está dando una parte de la información, la

llave (o clave) y se está preguntando para encontrar un registro que contiene más información asociada con la llave.

• La búsqueda de llaves para encontrar registros es a veces la acción que requiere más tiempo en un programa.


Clasificación de Técnicas de Búsqueda

• Búsqueda interna. • Los registros se mantienen dentro de la memoria del

computador.

• Búsqueda externa. • Hay muchos registros y cada uno muy grande o extenso y es

necesario almacenarlos en archivos o en medios externos.


• Búsqueda por comparación de llaves. • Se tiene la búsqueda secuencial, que es una técnica de

búsqueda que mejora la eficiencia de un archivo ordenado pero requiere mayor espacio.

• Búsqueda por transformación de llaves. • El valor de la llave se transforma en un índice de una tabla

para obtener una dirección.

Clasificación de Técnicas de Búsqueda


Algoritmos de Búsqueda

• Búsqueda por comparación de llaves• Secuencial • Secuencial encadenada• Secuencial indexada• Secuencial binaria• Árbol binario de búsqueda• ….

• Búsqueda por transformación de llaves• Funciones hash

• Método de la división• Método del cuadrado• Método de pliegue• …..


1. Búsqueda secuencial.

Búsqueda por comparación de llaves

int A_SECUENCIAL( int llave; int k [ ] ) {int i = 1, n;boolean f = false;while( ( i<=n ) && ( ! ( f ) )

if ( llave == k[i] ) {posic = i; f = true;

}else

i++;if ( ! f )

posic = 0;return posic;

}


2. Búsqueda secuencial encadenada.

• Almacena una tabla o archivo como lista encadenada.• Ventaja: el tamaño de la tabla puede ser aumentada

únicamente de acuerdo a los requerimientos. • Asume que la tabla está organizada como una lista

encadenada lineal.



2.- ALGORITMO DE BUSQUEDA BINARIA. • Este método es el más eficiente en un tabla o archivo secuencial. • El argumento de búsqueda es comparado con la llave del

elemento central de la tabla, si estos son iguales entonces termina la búsqueda, si no, continua la búsqueda con la parte superior o inferior de la tabla siguiendo los mismos pasos.

• Válido exclusivamente para vectores ordenados.• Termina si se encuentra el valor buscado o si el tamaño del

intervalo de búsqueda queda anulado.• En los casos en que existan repeticiones en el vector, del valor

buscado, obtendrá uno de ellos aleatoriamente según los lugares que ocupen, los cuales necesariamente son consecutivos.



#include <stdio.h>void main (void){ int vector [100], x, enc, i, centro, izqda, dcha;

for (i = 0; i <= 99; i++)// ingreso de datos al arreglo

vector[i] = i * 2;x = i / 2;

// Escritura en pantalla del vector ordenadoprintf ("\n\nVector:\n");for (i = 0; i < 100; i++)

printf ("%d\t", vector[i]);



printf ("\nValor a buscar: %d", x);// Búsqueda binaria en vector ordenadoenc = 0;izqda = 0;dcha = 99;while (! enc && izqda <= dcha) {

centro = (izqda + dcha) / 2;if (x < vector[centro])dcha = centro - 1;

else if (x > vector[centro])izqda = centro + 1;

elseenc = 1;

}



// Escritura en pantalla del vector ordenadoif (enc)printf("\n%d encontrado en índice %d ", x, centro);

elseprintf ("\n\nNo existe el valor %d en el vector.", x);

getch ();}



// Implementación recursiva del algoritmo de Búsqueda Binaria#define FALSE 0#define TRUE 1

int búsqueda( int vec[ ], int elem, int limiteInf, int limiteSup ) {int medio;

if ( limiteInf > limiteSup )return FALSE;

else if(vec[ medio = (limiteInf + limiteSup +1 ) / 2 ] == elem )return TRUE;

else if ( elem < vec[ medio ] )return búsqueda( vec, elem, limiteInf, medio-1 );

elsereturn búsqueda( vec, elem, medio+1, limiteSup );

}



ALGORITMO FIBONACCI:

• Algoritmo de búsqueda es para un arreglo ordenado que utiliza la secuencia numérica de Fibonacci como parte del proceso.

• Se utiliza un arreglo que contiene los números Fibonacci. • La secuencia Fibonacci consiste en que cada elemento es la suma

de los dos elementos anteriores.0, 1, 1, 2, 3, 5, 8, 13,.............



int FIBONACCI( int llave,n, K[ ], FIB[ ] ) {int T, J = 1, mitad = 1/n;boolean fin;while((FIB[J] != K[mitad] ) && ( ! fin) )

if ((mitad <= 0) || (llave> K[mitad]))if ( F1 = = 1 ) fin = trueelse {

mitad = mitad + F2;F1 = F1 - F2; F2 = F2 - F1;

}else {if (F2 == 0 ) fin = true;else {

mitad = mitad - F2;T = F1 - F2;

F2 = T;}if ( fin ) return 0;else return mitad;

}


Referencias

• Apuntes y notas personales• ¿Qué es ordenamiento?; Raiger Murillo Moreno.• Aho, J.E. Hopcroft y J. D. Ullman, Data structures and

algorithms. • T. Cormen, C. Leiserson y R. Rivest, Introduction to Algorithms.• H. R. Lewis y L. Denenderg, Data Structures and Their

Algortihms.• D. E. Knuth, The Art of Computer Programing, Vol. 1,

Fundamental Algorithm, y Vol. 3, Sorting and Searching. • R. Sedgewick, Algorithms. • G. H. Gonnet y R. Baeza-Yates, Handbook of Algorithms and

Data Structure.

ordenamiento - cime.cl · tipos de ordenamiento universidad técnica federico santa maría -...

Documents