|
Categorias
|
Algoritmos de Ordenamiento
Algoritmos de Ordenamiento ¿Qué es ordenamiento? Es la operación de arreglar los registros de una tabla enalgún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algúncampo en un registro. El propósito principal de un ordenamiento es el de facilitarlas búsquedas de los miembros del conjunto ordenado. Ej. de ordenamientos: Dir. telefónico, tablas de contenido, bibliotecas ydiccionarios, etc. El ordenar un grupo de datos significa mover los datos o susreferencias para que queden en una secuencia tal que represente un orden, elcual puede ser numérico, alfabético o incluso alfanumérico, ascendente odescendente. ¿Cuándo conviene usar un método de ordenamiento? Cuando se requiere hacer una cantidad considerable de búsquedasy es importante el factor tiempo.
Tipos de ordenamientos: Los 2 tipos de ordenamientos que se pueden realizar son: losinternos y los externos. Los internos: Son aquellos en los que los valores a ordenar están enmemoria principal, por lo que se asume que el tiempo que se requiere paraacceder cualquier elemento sea el mismo (a[1], a[500], etc). Los externos: Son aquellos en los que los valores a ordenar están enmemoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asumeque el tiempo que se requiere para acceder a cualquier elemento depende de la últimaposición accesada (posición 1, posición 500, etc).
Eficiencia en tiempo de ejecución: Una medida de eficiencia es: Contar el # de comparaciones (C) Contar el # de movimientos de items (M) Estos están en función de el #(n) de items a ser ordenados. Un "buen algoritmo" de ordenamiento requiere de unorden nlogn comparaciones.
La eficiencia de los algoritmos se mide por el número decomparaciones e intercambios que tienen que hacer, es decir, se toma n como el númerode elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmorealiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2 Algoritmos de ordenamiento: Internos:
Externos:
Clasificación de los algoritmos de ordenamiento de información: El hecho de que la información está ordenada, nos sirvepara poder encontrarla y accesarla de manera más eficiente ya que de locontrario se tendría que hacer de manera secuencial. A continuación se describirán 4 grupos de algoritmos paraordenar información: Algoritmos de inserción: En este tipo de algoritmo los elementos que van a serordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posiciónapropiada con respecto al resto de los elementos ya ordenados. Entre estos algoritmos se encuentran el de INSERCION DIRECTA,SHELL SORT, INSERCION BINARIA y HASHING. Algoritmos de intercambio: En este tipo de algoritmos se toman los elementos de dos endos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Esteproceso se repite hasta que se ha analizado todo el conjunto de elementos y yano hay intercambios. Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT. Algoritmos de selección: En este tipo de algoritmos se SELECCIONA o se busca elelemento más pequeño (o más grande) de todo el conjunto de elementos y secoloca en su posición adecuada. Este proceso se repite para el resto de loselementos hasta que todos son analizados. Algoritmos de enumeración: En este tipo de algoritmos cada elemento es comparado contralos demás. En la comparación se cuenta cuántos elementos son más pequeñosque el elemento que se está analizando, generando así una ENUMERACION. El númerogenerado para cada elemento indicará su posición. Los métodos simples son: Inserción (o por insercióndirecta), selección, burbuja y shell, en dónde el último es una extensión almétodo de inserción, siendo más rápido. Los métodos más complejos son elquick-sort (ordenación rápida) y el heap sort. A continuación se mostrarán los métodos de ordenamiento mássimples.
METODO DE INSERCIÓN. Este método toma cada elemento del arreglo para ser ordenadoy lo compara con los que se encuentran en posiciones anteriores a la de éldentro del arreglo. Si resulta que el elemento con el que se está comparando esmayor que el elemento a ordenar, se recorre hacia la siguiente posiciónsuperior. Si por el contrario, resulta que el elemento con el que se estácomparando es menor que el elemento a ordenar, se detiene el proceso decomparación pues se encontró que el elemento ya está ordenado y se coloca ensu posición (que es la siguiente a la del último número con el que se comparó).
Procedimiento Insertion Sort Este procedimiento recibe el arreglo de datos a ordenar a[]y altera las posiciones de sus elementos hasta dejarlos ordenados de menor amayor. N representa el número de elementos que contiene a[]. paso 1: [Para cada pos. del arreglo] For i <- 2 to N do paso 2: [Inicializa v y j] v <- a[i] j <- i. paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1], paso 5: [Decrementa j] set j <- j-1. paso 5: [Inserta v en su posición] Set a[j] <- v. paso 6: [Fin] End. Ejemplo :Si el arreglo a ordenar es a =['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va arecorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' ylo asigna a v y i toma el valor de la posición actual de v. Luego compara esta 's' con lo que hay en la posición j-1, esdecir, 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 menorrecorre a la 's' a la posición de la 'o'; decrementa j, la cual ahoratiene la posición en dónde estaba la 's'; compara a 'o' con a[j-1] , es decir,con 'a'. Como no es menor que la 'a' sale del for y pone la 'o' en la posicióna[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']
MÉTODO DE SELECCIÓN. El método de ordenamiento por selección consiste enencontrar el menor de todos los elementos del arreglo e intercambiarlo con elque está en la primera posición. Luego el segundo mas pequeño, y asísucesivamente hasta ordenar todo el arreglo.
Procedimiento Selection Sort paso 1: [Para cada pos. del arreglo] For i <- 1 to N do paso 2: [Inicializa la pos. del menor] menor <- i paso 3: [Recorre todo el arreglo] For j <- i+1 to N do paso 4: [Si a[j] es menor] If a[j] < a[menor] then paso 5: [Reasigna el apuntador al menor] min = j paso 6: [Intercambia los datos de la pos. min y posición i] Swap(a, min, j). paso 7: [Fin] End. Ejemplo: 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 menorelemento. En este caso el menor elemento es la primera 'a'. De manera que noocurre ningún cambio. Luego se procede a buscar el siguiente elemento y seencuentra la segunda 'a'. Esta se intercambia con el dato que está en la segundaposición, la 's', quedando el arreglo así 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 esla 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 lasiguiente posición hasta ordenar todo el arreglo. El número de comparaciones que realiza este algoritmo es : Para el primer elemento se comparan n-1 datos, en generalpara el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el total decomparaciones es: la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).
MÉTODO BURBUJA. El bubble sort, también conocido como ordenamiento burbuja,funciona de la siguiente manera: Se recorre el arreglo intercambiando loselementos adyacentes que estén desordenados. Se recorre el arreglo tantas veceshasta que ya no haya cambios. Prácticamente lo que hace es tomar el elementomayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar. Procedimiento Bubble Sort
paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] < a[j] then paso 5: [Los intercambia] Swap(a, j-1, j). paso 7: [Fin] End.
Tiempo de ejecución del algoritmo burbuja:
MÉTODO DE SHELL. Ordenamiento de disminución incremental. Nombrado así debido a su inventor Donald Shell. Ordena subgrupos de elementos separados K unidades (respectode su posición en el arreglo) del arreglo original. El valor K es llamadoincremento. Después de que los primeros K subgrupos han sido ordenados(generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K máspequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos.Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevocon un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera queel subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia dedecrecimiento de incrementos; el último valor debe ser 1. "Es como hacer un ordenamiento de burbuja perocomparando e intercambiando elementos." Cuando el incremento toma un valor de 1, todos los elementospasan 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úmerode elementos) y luego se va reduciendo a la mitad en cada repetición hasta queel salto o distancia vale 1. Procedimiento Shell Sort; const MAXINC = _____; incrementos = array[1..MAXINC] of integer; var j,p,num,incre,k:integer; begin for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */ k := inc[incre]; /* k recibe un tipo de incremento */ for p := k+1 to MAXREG do begin /* inserción directa para el grupo que seencuentra cada K posiciones */ num := reg[p]; j := p-k; while (j>0) AND (num < reg[j]) begin reg[j+k] := reg[j]; j := j - k; end; reg[j+k] := num; end end end; Ejemplo: Para el arreglo a = [6, 1, 5, 2, 3, 4, 0] Tenemos el siguiente recorrido:
Autor: Raiger Murillo Moreno Email: rmurillo95@yahoo.comIngeniero de Sistemas
Articulos relacionados:
|
|
Copyright © 2011 ilustrados.com, Monografias, tesis, bibliografias, educacion. Tofos los temas y publicaciones son propiedad de sus respectivos autores ©